DTD Inference for Views of XML Data

Summary: Infers tight DTDs for selection views over ordered XML (queries with vertical/horizontal navigation) and pinpoints limits of standard DTD expressiveness. Proposes extending DTDs with subtyping and context-free specifications to guarantee exact view DTDs, identifies special cases where regular DTDs suffice, and studies conformance checking. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1192
Venue: PODS
Year: 2000
Pagerank: 0.00011312135
Overall Rank: 1,290 | 91.16%
DOI: 10.1145/335168.335173

Incoming Non-self Citations Over Time

Authors

1. Yannis Papakonstantinou (University of California San Diego)
2. Victor Vianu (University of California San Diego)

BibTeX Citation

@inproceedings{papakonstantinou_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{DTD Inference for Views of XML Data}},
        url = {https://dl.acm.org/doi/10.1145/335168.335173},
        doi = {10.1145/335168.335173},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Papakonstantinou, Yannis and Vianu, Victor},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,082	A Transducer-Based XML Query Processor	2002	VLDB	0.00012257574
1,758	Validating Streaming XML Documents	2002	PODS	9.8162828e-05
2,680	Efficient Algorithms for Minimizing Tree Pattern Queries	2002	SIGMOD	8.267202e-05
2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	8.0195639e-05
3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	7.5749332e-05
3,679	XML with Data Values: Typechecking Revisited	2001	PODS	7.2045472e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
5,386	Distributed XML Design	2009	PODS	6.2369533e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05
12,343	Developing and Analyzing XSDs through BonXai	2012	VLDB	5.093636e-05
12,411	Schema Design for XML Repositories: Complexity and Tractability	2010	PODS	5.093636e-05
12,412	Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages	2010	PODS	5.093636e-05
12,575	Type Inference and Type Checking for Queries on Execution Traces	2008	VLDB	5.093636e-05
12,628	Reasoning about XML Update Constraints	2007	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
454	Using Schema Matching to Simplify Heterogeneous Data Translation	1998	VLDB	0.00018133578
573	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00016290377
645	Your Mediators Need Data Conversion!	1998	SIGMOD	0.00015338713
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
1,167	Object Fusion in Mediator Systems	1996	VLDB	0.00011845214
1,253	Extracting Schema from Semistructured Data	1998	SIGMOD	0.00011475793
1,302	Catching the Boat with Strudel: Experiences with a Web-Site Management System	1998	SIGMOD	0.00011238375
1,372	Typechecking for XML Transformers	2000	PODS	0.00010994864
2,114	Query Rewriting for Semistructured Data	1999	SIGMOD	9.1481121e-05
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
2,859	XML-Based Information Mediation with MIX	1999	SIGMOD	8.0283136e-05
6,318	Query Automata (extended abstract)	1999	PODS	5.9150511e-05
6,319	Expressiveness of Structured Document Query Languages Based on Attribute Grammars (extended abstract)	1998	PODS	5.9150511e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,881	On Views and XML	1999	PODS
2	2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS
3	4,167	Integrity Constraints for XML	2000	PODS
4	137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB
5	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
6	4,619	DTD-Directed Publishing with Attribute Translation Grammars	2002	VLDB
7	2,757	Secure XML Querying with Security Views	2004	SIGMOD
8	1,142	XTRACT: A System for Extracting Document Type Descriptors from XML Documents	2000	SIGMOD
9	2,795	Inferring XML Schema Definitions from XML Data	2007	VLDB
10	3,679	XML with Data Values: Typechecking Revisited	2001	PODS