The Complexity of Reasoning about Pattern-based XML Schemas

Summary: Analyzes rule-based XML schemas of r→s rules (r: root-path regex, s: children-sequence regex) under existential vs universal node semantics. Proves satisfiability/implication are ExpTime-complete in general and isolates two natural fragments in PSPACE and PTime. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1424
Venue: PODS
Year: 2007
Pagerank: 5.093636e-05
Overall Rank: 12,625 | 13.39%
DOI: 10.1145/1265530.1265552

Incoming Non-self Citations Over Time

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

Authors

1. Gjergji Kasneci (Max Planck Institute)
2. Thomas Schwentick (University of Dortmund)

BibTeX Citation

@inproceedings{kasneci_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{The Complexity of Reasoning about Pattern-based XML Schemas}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265552},
        doi = {10.1145/1265530.1265552},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kasneci, Gjergji and Schwentick, Thomas},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,928	BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema	2015	PODS	5.5181056e-05
12,343	Developing and Analyzing XSDs through BonXai	2012	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,671	A Normal Form for XML Documents	2002	PODS	0.00010043595
2,049	XML Data Exchange: Consistency and Query Answering	2005	PODS	9.255274e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,440	On XPath with Transitive Axes and Data Tests	2013	PODS
2	12,628	Reasoning about XML Update Constraints	2007	PODS
3	3,274	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS
4	8,417	XML Schema Mappings	2009	PODS
5	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
6	4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB
7	2,864	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS
8	12,410	Certain Answers for XML Queries	2010	PODS
9	4,071	Two-Variable Logic on Data Trees and XML Reasoning	2006	PODS
10	12,412	Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages	2010	PODS