DBScholar

Back to papers

On XML Integrity Constraints in the Presence of DTDs

Summary: Shows that DTDs interact with XML integrity constraints in intricate ways: general consistency (existence of a document satisfying both) is undecidable, while for unary keys and foreign keys consistency is NP-complete via encoding to linear integer constraints. Analyzes variants to identify tractable fragments and additional NP-complete cases, and proves that implication with constraint negation is coNP-complete for unary keys/foreign keys. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h997e71ca45c1f091
Venue
PODS
Year
2001
Pagerank
8.2910005e-05
Overall Rank
2,565 | 82.76%
DOI
10.1145/375551.375568

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{fan_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{On XML Integrity Constraints in the Presence of DTDs}},
        url = {https://dl.acm.org/doi/10.1145/375551.375568},
        doi = {10.1145/375551.375568},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fan, Wenfei and Libkin, Leonid},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
500 Dependencies Revisited for Improving Data Quality 2008 PODS 0.00017280722
2,364 Dependencies for Graphs 2017 PODS 8.5665938e-05
3,503 On the Decidability and Finite Controllability of Query Processing in Databases with Incomplete Information 2006 PODS 7.2520222e-05
4,266 A Web Odyssey: from Codd to XML 2001 PODS 6.6972871e-05
4,459 Semantic Query Optimization in the Presence of Types 2010 PODS 6.590177e-05
4,717 DTD-Directed Publishing with Attribute Translation Grammars 2002 VLDB 6.4552474e-05
5,474 Running Tree Automata on Probabilistic XML 2009 PODS 6.1176063e-05
5,739 Capturing Missing Tuples and Missing Values 2010 PODS 6.011429e-05
6,312 Putting Context into Schema Matching 2006 VLDB 5.8171904e-05
6,910 Efficient Discovery of XML Data Redundancies 2006 VLDB 5.6486607e-05
7,503 Static Analysis of Active XML Systems 2008 PODS 5.5076551e-05
8,591 XML Schema Mappings 2009 PODS 5.3070609e-05
8,647 Discovering XSD Keys from XML Data 2013 SIGMOD 5.2952465e-05
8,923 Incorporating Constraints in Probabilistic XML 2008 PODS 5.2559789e-05
11,106 Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases 2025 SIGMOD 4.9793485e-05
12,918 Reasoning about XML Update Constraints 2007 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank Cited Paper Year Venue Pagerank
356 Regular Path Queries with Constraints 1997 PODS 0.00020103855
2,317 Type Inference for Queries on Semistructured Data (Extended Abstract) 1999 PODS 8.6477878e-05
2,917 XML-Based Information Mediation with MIX 1999 SIGMOD 7.8578946e-05
3,365 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3728818e-05
4,248 Integrity Constraints for XML 2000 PODS 6.704016e-05
4,582 Reasoning about Nested Functional Dependencies 1999 PODS 6.5191203e-05
10,067 Interaction between Path and Type Constraints 1999 PODS 5.0873692e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,067 Interaction between Path and Type Constraints 1999 PODS
2 1,315 DTD Inference for Views of XML Data 2000 PODS
3 2,934 Typing and Querying XML Documents: Some Complexity Bounds 2003 PODS
4 6,060 Capturing both Types and Constraints in Data Integration 2003 SIGMOD
5 3,756 XML with Data Values: Typechecking Revisited 2001 PODS
6 2,100 XML Data Exchange: Consistency and Query Answering 2005 PODS
7 1,976 XPath Satisfiability in the Presence of DTDs 2005 PODS
8 12,918 Reasoning about XML Update Constraints 2007 PODS
9 4,248 Integrity Constraints for XML 2000 PODS
10 6,410 On Verifying Consistency of XML Specifications 2002 PODS