English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

The Complexity of Reasoning about Pattern-based XML Schemas

MPS-Authors
/persons/resource/persons44738

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
Citation

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
Abstract
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.