Queries with Incomplete Answers over Semistructured Data

Summary: Formalizes query evaluation with partial (maximal) answers over semistructured (labeled graph) data via a two‑phase model: a search phase with three matching semantics and a filter phase distinguishing weak vs. strong constraints. Provides algorithms, complexity and containment analyses for each semantics and a polynomial-time evaluation result for a restricted class of filter queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1176
Venue: PODS
Year: 1999
Pagerank: 6.6623097e-05
Overall Rank: 4,495 | 69.17%
DOI: 10.1145/303976.303999

Incoming Non-self Citations Over Time

Authors

1. Yaron Kanza (Hebrew University)
2. Werner Nutt (German National Research Center for Information Technology)
3. Yehoshua Sagiv (Hebrew University)

BibTeX Citation

@inproceedings{kanza_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Queries with Incomplete Answers over Semistructured Data}},
        url = {https://dl.acm.org/doi/10.1145/303976.303999},
        doi = {10.1145/303976.303999},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kanza, Yaron and Nutt, Werner and Sagiv, Yehoshua},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,139	Foundations of Semantic Web Databases	2004	PODS	6.8776612e-05
5,502	Annotated XML: Queries and Provenance	2008	PODS	6.1961339e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05
9,646	Computing Full Disjunctions	2003	PODS	5.243371e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
573	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00016290377
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
1,176	Outerjoins as Disjunctions	1994	SIGMOD	0.00011809075
1,233	Semistructured Data	1997	PODS	0.00011562468
1,253	Extracting Schema from Semistructured Data	1998	SIGMOD	0.00011475793
1,302	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00011238375
1,869	Formal Models of Web Queries	1997	PODS	9.5891634e-05
2,603	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3535371e-05
2,727	To Weave the Web	1997	VLDB	8.200085e-05
2,791	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	8.119781e-05
3,308	Path Constraints on Semistructured and Structured Data	1998	PODS	7.5381026e-05
4,802	The ARANEUS Web-Base Management System	1998	SIGMOD	6.5018655e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
2	9,933	Semantic Acyclicity Under Constraints	2016	PODS
3	10,650	Rewriting Consistent Answers on Annotated Data	2025	PODS
4	2,934	Data Exchange and Incomplete Information	2006	PODS
5	747	Querying Graph Databases	2013	PODS
6	4,131	Querying Complex Structured Databases	2007	VLDB
7	6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD
8	2,138	Flexible Queries over Semistructured Data	2001	PODS
9	2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB
10	7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS