Database Paper Browser

Back to papers

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
1425
Venue
PODS
Year
2007
Pagerank
4.1905499e-05
Overall Rank
12,440 | 13.55%
DOI
-

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
7,505 BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema 2015 PODS 4.7135369e-05
12,155 Developing and Analyzing XSDs through BonXai 2012 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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,820 A Normal Form for XML Documents 2002 PODS 0.00010410152
2,217 XML Data Exchange: Consistency and Query Answering 2005 PODS 9.2682054e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,199 On XPath with Transitive Axes and Data Tests 2013 PODS 4.5558541e-05
12,443 Reasoning about XML Update Constraints 2007 PODS 4.1905499e-05
2,155 Frontiers of Tractability for Typechecking Simple XML Transformations 2004 PODS 9.4164126e-05
8,190 XML Schema Mappings 2009 PODS 4.5598146e-05
5,301 Running Tree Automata on Probabilistic XML 2009 PODS 5.5749031e-05
4,624 On Testing Satisfiability of Tree Pattern Queries 2004 VLDB 6.034764e-05
1,854 Typing and Querying XML Documents: Some Complexity Bounds 2003 PODS 0.00010320817
12,223 Certain Answers for XML Queries 2010 PODS 4.1905499e-05
4,076 Two-Variable Logic on Data Trees and XML Reasoning 2006 PODS 6.4657154e-05
12,225 Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages 2010 PODS 4.1905499e-05