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.84255e-05
Overall Rank: 3,683 | 74.41%
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,285	Foundations of Semantic Web Databases	2004	PODS	7.2738104e-05
5,275	Annotated XML: Queries and Provenance	2008	PODS	5.5908918e-05
6,505	Representing and Querying XML with Incomplete Information	2001	PODS	5.0282726e-05
9,512	Computing Full Disjunctions	2003	PODS	4.3299485e-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.00064281097
115	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00046301137
276	Regular Path Queries with Constraints	1997	PODS	0.00029365217
438	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00023220283
808	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.000164132
1,034	Outerjoins as Disjunctions	1994	SIGMOD	0.00014532543
1,080	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00014204122
1,163	Extracting Schema from Semistructured Data	1998	SIGMOD	0.00013572993
1,314	Semistructured Data	1997	PODS	0.00012618313
1,601	Formal Models of Web Queries	1997	PODS	0.00011197057
2,210	To Weave the Web	1997	VLDB	9.2875159e-05
2,680	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3203995e-05
2,972	Integrating Information by Outerjoins and Full Disjunctions (Extended Abstract)	1996	PODS	7.7933514e-05
3,262	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3081091e-05
3,663	The ARANEUS Web-Base Management System	1998	SIGMOD	6.8647127e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,415	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	5.5188622e-05
11,837	Semantic Acyclicity Under Constraints	2016	PODS	4.1905499e-05
10,369	Rewriting Consistent Answers on Annotated Data	2025	PODS	4.1905499e-05
3,507	Data Exchange and Incomplete Information	2006	PODS	7.0299158e-05
1,040	Querying Graph Databases	2013	PODS	0.00014483577
4,046	Querying Complex Structured Databases	2007	VLDB	6.5021302e-05
6,271	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	5.1273783e-05
1,873	Flexible Queries over Semistructured Data	2001	PODS	0.00010255165
2,331	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.019917e-05
7,391	Incomplete Information and Certain Answers in General Data Models	2011	PODS	4.7383385e-05