View-Based Query Answering and Query Containment over Semistructured Data

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi

Revised papers of the 8th Int. Workshop on Database Programming Languages (DBPL 2001). Volume 2397 of Lecture Notes in Computer Science. 2002.

The basic querying mechanism over semistructured data, namely regular path queries, asks for all pairs of objects that are connected by a path conforming to a regular expression. We consider conjunctive two-way regular path queries (C2RPQc s), which extend regular path queries with two features. First, they add the inverse operator, which allows for expressing navigations in the database that traverse the edges both backward and forward. Second, they allow for using conjunctions of atoms, where each atom specifies that a regular path query with inverse holds between two terms, where each term is either a variable or a constant. For such queries we address the problem of view-based query answering, which amounts to computing the result of a query only on the basis of a set of views. More specifically, we present the following results: (1) We exhibit a mutual reduction between query containment and the recognition problem for view-based query answering for C2RPQc s, i.e., checking whether a given tuple is in the certain answer to a query. Based on such a result, we can show that the problem of view-based query answering for C2RPQc s is EXPSPACE-complete. (2) By exploiting techniques based on alternating two-way automata we show that for the restricted class of tree two-way regular path queries (in which the links between variables form a tree), query containment and view-based query answering are, rather surprisingly, in PSPACE (and hence, PSPACE-complete). (3) We present a technique to obtain view-based query answering algorithms that compute the whole set of tuples in the certain answer, instead of requiring to check each tuple separately. The technique is parametric wrt the query language, and can be applied both to C2RPQc s and to tree-queries.


@inproceedings{DBPL-2002,
   title = "View-Based Query Answering and Query Containment over
Semistructured Data",
   year = "2002",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   editor = "Giorgio Ghelli and Gösta Grahne",
   booktitle = "Revised papers of the 8th Int. Workshop on Database
Programming Languages (DBPL 2001)",
   pages = "40--61",
   volume = "2397",
   publisher = "Springer",
   series = "Lecture Notes in Computer Science",
   doi = "10.1007/3-540-46093-4_3",
}
pdf url