Certain Answers for XML Queries

Summary: Model-theoretic extension of certain-answer semantics to XML tree-producing queries with general computability and complexity results. Introduces a basis-of-trees method to compute certain answers for pattern queries over nulls and data-exchange documents, and pinpoints a natural class of XML mappings that admit efficient query answering and static analysis. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1518
Venue: PODS
Year: 2010
Pagerank: 5.093636e-05
Overall Rank: 12,410 | 14.86%
DOI: 10.1145/1807085.1807112

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Claire David (University of Edinburgh)
2. Leonid Libkin (University of Edinburgh)
3. Filip Murlak (University of Warsaw)

BibTeX Citation

@inproceedings{david_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Certain Answers for XML Queries}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807112},
        doi = {10.1145/1807085.1807112},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {David, Claire and Libkin, Leonid and Murlak, Filip},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,271	Incomplete Data: What Went Wrong, and How to Fix It	2014	PODS	6.2907571e-05
7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS	5.61159e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
416	Translating Web Data	2002	VLDB	0.00018877803
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
685	Composing Schema Mappings: Second-Order Dependencies to the Rescue	2004	PODS	0.00014979915
762	Model Management 2.0: Manipulating Richer Mappings	2007	SIGMOD	0.00014231163
874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013481551
879	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD	0.00013456577
1,564	Conjunctive Queries over Trees	2004	PODS	0.00010349456
3,075	Matching Twigs in Probabilistic XML	2007	VLDB	7.7839831e-05
4,139	Foundations of Semantic Web Databases	2004	PODS	6.8776612e-05
8,417	XML Schema Mappings	2009	PODS	5.4288691e-05
12,493	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,934	Data Exchange and Incomplete Information	2006	PODS
2	3,180	Approximate XML Query Answers	2004	SIGMOD
3	4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
4	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
5	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
6	3,679	XML with Data Values: Typechecking Revisited	2001	PODS
7	12,325	Answering Queries using Views over Probabilistic XML: Complexity and Tractability	2012	VLDB
8	2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS
9	12,493	XML with Incomplete Information: Models, Properties, and Query Answering	2009	PODS
10	7,462	Incomplete Information and Certain Answers in General Data Models	2011	PODS