TY - GEN
T1 - The complexity of reasoning about pattern-based XML schemas
AU - Kasneci, Gjergji
AU - Schwentick, Thomas
PY - 2007
Y1 - 2007
N2 - In a recent paper, Martens et al. introduced a specification mechanism for XML tree languages, based on rules of the form (r,s), wherer, 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 matchess. It is universally valid if each node matching r also matchess. 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.
AB - In a recent paper, Martens et al. introduced a specification mechanism for XML tree languages, based on rules of the form (r,s), wherer, 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 matchess. It is universally valid if each node matching r also matchess. 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.
KW - Integrity constraints
KW - XML schemas
UR - http://www.scopus.com/inward/record.url?scp=35448937638&partnerID=8YFLogxK
U2 - 10.1145/1265530.1265552
DO - 10.1145/1265530.1265552
M3 - Conference contribution
AN - SCOPUS:35448937638
SN - 1595936858
SN - 9781595936851
T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
SP - 155
EP - 164
BT - Proceedings of the Twenty-sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2007
T2 - 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2007
Y2 - 11 June 2007 through 13 June 2007
ER -