|
Title
|
|
|
|
Satisfiability of XPath expressions
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| In this paper, we investigate the complexity of deciding the satisfiability of XPath 2.0 expressions, i.e., whether there is an XML document for which their result is nonempty. Several fragments that allow certain types of expressions are classified as either in PTIME or NP-hard to see which type of expression make this a hard problem. Finally, we establish a link between XPath expressions and partial tree descriptions which are studied in computational linguistics. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Lecture notes in computer science. - Berlin, 1973, currens
| |
|
Source (book)
|
|
|
|
9th International Workshop on Data Bases and Programming Languages, SEP 06-08, 2003, Potsdam, GERMANY
| |
|
Publication
|
|
|
|
Berlin
:
2004
| |
|
ISBN
|
|
|
|
3-540-20896-8
| |
|
Volume/pages
|
|
|
|
2921
(2004)
, p. 21-36
| |
|
ISI
|
|
|
|
000189417500003
| |
|
Full text (publisher's version - intranet only)
|
|
|
|
| |
|