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: 1177
Venue: PODS
Year: 1999
Pagerank: 6.8492288e-05
Overall Rank: 3,681 | 74.40%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,282	Foundations of Semantic Web Databases	2004	PODS	7.2808673e-05
5,270	Annotated XML: Queries and Provenance	2008	PODS	5.5963545e-05
6,509	Representing and Querying XML with Incomplete Information	2001	PODS	5.0331402e-05
9,511	Computing Full Disjunctions	2003	PODS	4.3340927e-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
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064329285
114	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046339735
274	Regular Path Queries with Constraints	1997	PODS	0.00029390022
437	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00023240203
810	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00016428374
1,032	Outerjoins as Disjunctions	1994	SIGMOD	0.00014544529
1,081	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00014216794
1,163	Extracting Schema from Semistructured Data	1998	SIGMOD	0.00013577466
1,314	Semistructured Data	1997	PODS	0.0001263326
1,599	Formal Models of Web Queries	1997	PODS	0.00011202032
2,204	To Weave the Web	1997	VLDB	9.2970809e-05
2,676	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3274001e-05
2,966	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.8002072e-05
3,257	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3151681e-05
3,657	The ARANEUS Web-Base Management System	1998	SIGMOD	6.8713279e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
10,357	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1945683e-05
11,829	Semantic Acyclicity Under Constraints	2016	PODS	4.1945683e-05
3,502	Data Exchange and Incomplete Information	2006	PODS	7.0366655e-05
4,038	Querying Complex Structured Databases	2007	VLDB	6.5082212e-05
1,037	Querying Graph Databases	2013	PODS	0.00014502493
6,273	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1323078e-05
1,870	Flexible Queries over Semistructured Data	2001	PODS	0.00010263799
2,327	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.0276061e-05
7,393	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7428879e-05