DBScholar

Back to papers

Two-Variable Logic on Data Trees and XML Reasoning

Summary: Decidability of FO^2 satisfiability over data trees when navigation is restricted to child and next-sibling and data comparisons are equality-only. Implies decidability of satisfiability/containment for a data-aware XPath fragment and of implication for unary key/inclusion constraints. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1371
Venue
PODS
Year
2006
Pagerank
6.927159e-05
Overall Rank
4,071 | 72.08%
DOI
10.1145/1142351.1142354

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bojanczyk_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Two-Variable Logic on Data Trees and XML Reasoning}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142354},
        doi = {10.1145/1142351.1142354},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bojańczyk, Mikołaj and David, Claire and Muscholl, Anca and Schwentick, Thomas and Segoufin, Luc},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
5,425 GPC: A Pattern Calculus for Property Graphs 2023 PODS 6.223218e-05
8,417 XML Schema Mappings 2009 PODS 5.4288691e-05
12,487 The Finite Model Theory Toolbox of a Database Theoretician 2009 PODS 5.093636e-05
12,491 Satisfiability of Downward XPath with Data Equality Tests 2009 PODS 5.093636e-05
12,628 Reasoning about XML Update Constraints 2007 PODS 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank Cited Paper Year Venue Pagerank
666 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00015166582
1,916 XPath Satisfiability in the Presence of DTDs 2005 PODS 9.4878711e-05
3,679 XML with Data Values: Typechecking Revisited 2001 PODS 7.2045472e-05
Previous Page 1 / 1 Next

Semantically Similar Papers