Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

The Complexity of Reasoning about Pattern-based XML Schemas


Kasneci,  Gjergji
Databases and Information Systems, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Kasneci, G., & Schwentick, T. (2007). The Complexity of Reasoning about Pattern-based XML Schemas. In L. Libkin (Ed.), Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems: PODS 2007 (pp. 155-164). New York, NY, USA: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-20F7-6
In a recent paper, Martens et al. introduced a specification mechanism for {XML} tree languages, based on rules of the form r ! s, where r, s are regular expressions. Sets of such rules can be interpreted in an existential or a universal fashion. An {XML} tree is existentially valid with respect to a rule set, if for each node there is a rule such that the root path of the node matches r and the children sequence of the node matches s. It is universally valid if each node matching r also matches s. This paper investigates the complexity of reasoning about such rule sets, in particular the satisfiability and the implication problem. Whereas, in general these reasoning problems are complete for ExpTime, two important fragments are identified with PSpace and PTime complexity, respectively.