Conjunctive Query Containment over Trees.
In: Database Programming Languages (9783540759867); 2007, p66-80, 15p
Buch
Zugriff:
The complexity of containment and satisfiability of conjunctive queries over finite, unranked, labeled trees is studied with respect to the axes Child, nextSibling, their transitive and reflexive closures, and Following. For the containment problem a trichotomy is presented, classifying the problems as in PTIME, coNP-complete, or Π2P-complete. For the satisfiability problem most problems are classified as either in PTIME or NP-complete. [ABSTRACT FROM AUTHOR]
Copyright of Database Programming Languages (9783540759867) is the property of Springer eBooks and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Titel: |
Conjunctive Query Containment over Trees.
|
---|---|
Autor/in / Beteiligte Person: | Hutchison, David ; Kanade, Takeo ; Kittler, Josef ; Kleinberg, Jon M. ; Mattern, Friedemann ; Mitchell, John C. ; Naor, Moni ; Nierstrasz, Oscar ; Pandu Rangan, C. ; Steffen, Bernhard ; Sudan, Madhu ; Terzopoulos, Demetri ; Tygar, Doug ; Vardi, Moshe Y. ; Weikum, Gerhard ; Arenas, Marcelo ; Schwartzbach, Michael I. ; Björklund, Henrik ; Martens, Wim ; Schwentick, Thomas |
Quelle: | Database Programming Languages (9783540759867); 2007, p66-80, 15p |
Veröffentlichung: | 2007 |
Medientyp: | Buch |
ISBN: | 978-3-540-75986-7 (print) |
DOI: | 10.1007/978-3-540-75987-4_5 |
Sonstiges: |
|