Result: Conjunctive queries over trees

Title:
Conjunctive queries over trees
Authors:
GOTTLOB, Georg, KOCH, Christoph, SCHULZ, Klaus U
Source:
PODS 2004: ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, Paris, France - June 14-16, 2004Journal of the Association for Computing Machinery. 53(2):238-272
Publisher Information:
New York, NY: Association for Computing Machinery, 2006.
Publication Year:
2006
Physical Description:
print, 1 p.1/2
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Logiciel, Software, Organisation des mémoires. Traitement des données, Memory organisation. Data processing, Systèmes d'information. Bases de données, Information systems. Data bases, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Dichotomie, Dichotomy, Dicotomía, Interrogation base donnée, Database query, Interrogación base datos, Langage XML, XML language, Lenguaje XML, Méthode arborescente, Tree structured method, Método arborescente, Problème NP complet, NP complete problem, Problema NP completo, Requête conjonctive, Conjunctive query, Requerimiento conjuntivo, Temps polynomial, Polynomial time, Tiempo polinomial, Algorithms Complexity, Languages, Theory, XML, conjunctive queries, expressiveness, succinctness, trees
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Oxford University, Oxford, United Kingdom
Universität des Saarlandes, Saarbrücken, Germany
Ludwig-Maximilians-Universität München, Munich, Germany
ISSN:
0004-5411
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17846034
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17846034
Database:
PASCAL Archive

Further Information

We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as child, descendant, and following as well as unary relations for node labels. We establish a framework for characterizing structures representing trees for which conjunctive queries can be evaluated efficiently. Then we completely chart the tractability frontier of the problem and establish a dichotomy theorem for our axis relations, that is, we find all subset-maximal sets of axes for which query evaluation is in polynomial time and show that for all other cases, query evaluation is NP-complete. All polynomial-time results are obtained immediately using the proof techniques from our framework. Finally, we study the expressiveness of conjunctive queries over trees and show that for each conjunctive query, there is an equivalent acyclic positive query (i.e., a set of acyclic conjunctive queries), but that in general this query is not of polynomial size.