Reasoning on queries is a basic problem both in knowledge representation and databases. A fundamental form of reasoning on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another query. Query containment is crucial in several contexts, such as query optimization, knowledge base veriflcation, information integration, database integrity checking, and cooperative answering. In this paper we address the problem of query containment in the context of semistructured knowledge bases, where the basic querying mechanism, namely regular path queries, asks for all pairs of objects that are connected by a path conforming to a regular expression. We consider conjunctive regular path queries with inverse, which extend regular path queries with the possibility of using both the inverse of binary relations, and conjunctions of atoms, where each atom specifles that one regular path query with inverse holds between two variables. We present a novel technique to check containment of queries in this class, based on the use of two-way flnite automata. The technique shows the power of two-way automata in dealing with the inverse operator and with the variables in the queries. We also characterize the computational complexity of both the proposed algorithm and the problem.
['Diego Calvanese', 'Giuseppe De Giacomo', 'Maurizio Lenzerini', 'Moshe Y. Vardi']
Containment of Conjunctive Regular Path Queries with Inverse.