• The complexity of XPath query...

Result: The complexity of XPath query evaluation and XML typing

Title:
The complexity of XPath query evaluation and XML typing
Authors:
GOTTLOB, Georg, KOCH, Christoph, PICHLER, Reinhard, SEGOUFIN, L. U. C
Source:
Journal of the Association for Computing Machinery. 52(2):284-335
Publisher Information:
New York, NY: Association for Computing Machinery, 2005.
Publication Year:
2005
Physical Description:
print, 1 p.3/4
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, 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, Automate arbre, Tree automaton, Autómata árbol, Classe complexité, Complexity class, Clase complejidad, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Définition type document, Document type definition, Definición tipo documento, Interrogation base donnée, Database query, Interrogación base datos, Langage XML, XML language, Lenguaje XML, Langage formel, Formal language, Lenguaje formal, Logique mathématique, Mathematical logic, Lógica matemática, Traitement requête, Query processing, Tratamiento pregunta, Typage, Typing, Tipificación, Algorithms Complexity, DTD, LOGCFL, Languages, Theory, XML, XPath
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Technische Universität Wien, Wien, Austria
INRIA, France
ISSN:
0004-5411
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=16770568
Rights:
Copyright 2005 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.16770568
Database:
PASCAL Archive

Further Information

We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTIME in previous work. We prove that both the data complexity and the query complexity of XPath 1.0 fall into lower (highly parallelizable) complexity classes, while the combined complexity is PTIME-hard. Subsequently, we study the sources of this hardness and identify a large and practically important fragment of XPath 1.0 for which the combined complexity is LOGCFL-complete and, therefore, in the highly parallelizable complexity class NC2. The second problem is the complexity of validating XML documents against various typing schemes like Document Type Definitions (DTDs), XML Schema Definitions (XSDs), and tree automata, both with respect to data and to combined complexity. For data complexity, we prove that validation is in LOGSPACE and depends crucially on how XML data is represented. For the combined complexity, we show that the complexity ranges from LOGSPACE to LOGCFL, depending on the typing scheme.