Name
Abstract | ||
|---|---|---|
We prove that various containment and validity problems for tree pattern queries with respect to a schema are EXPTIME-complete. When one does not require the root of a tree pattern query to match the root of a tree, validity of a non-branching tree pattern query with respect to a Relax NG schema or W3C XML Schema is already EXPTIME-hard when the query does not branch and uses only child axes. These hardness results already hold when the alphabet size is fixed. Validity with respect to a DTD is proved to be EXPTIME-hard already when the query only uses child axes and is allowed to branch only once. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40313-2_17 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
computer science | Regular expression,Conjunctive query,Computer science,Theoretical computer science,RELAX NG,XML schema,Tree automaton,Schema (psychology),Tree pattern,Alphabet | Conference |
Volume | ISSN | Citations |
8087 | 0302-9743 | 9 |
PageRank | References | Authors |
0.50 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henrik Björklund | 1 | 311 | 20.41 |
| wim martens | 2 | 609 | 29.78 |
| Thomas Schwentick | 3 | 2373 | 155.10 |