Paper Info
Title
Optimizing Conjunctive Queries over Trees Using Schema Information
Abstract
We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME-complete w.r.t. a schema (DTD or Relax NG). Furthermore, we show that satisfiability for conjunctive queries w.r.t. a schema can be decided in NP. The problem is NP-hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment w.r.t. a schema becomes decidable again if the "larger" query is not allowed to use both equalities and inequalities.
Year
DOI
Venue
2008
10.1007/978-3-540-85238-4_10
MFCS
Keywords
Field
DocType
optimizing conjunctive queries,containment w,schema information,conjunctive query containment,validity problem,relax ng,conjunctive queries w,conjunctive query,data value,satisfiability,conjunctive queries
Discrete mathematics,Conjunctive query,Computer science,Satisfiability,Decidability,RELAX NG,Tree automaton,Schema (psychology),Boolean conjunctive query,Undecidable problem
Conference
Volume
ISSN
Citations 
5162
0302-9743
36
PageRank 
References 
Authors
1.22
18
3
Name
Order
Citations
PageRank
Henrik Björklund131120.41
wim martens260929.78
Thomas Schwentick32373155.10