Abstract
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 re sult of another query. Query containment is crucial in several contexts, such as query opti mization, knowledge base verification, infor mation integration, database integrity check ing, and cooperative answering. In this paper we address the problem of query containment in the context of semistructured knowledge bases, where the basic query ing mechanism, namely regular path queries, asks for all pairs of objects that are connected by a path conforming to a regular expres sion. 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 conjunc tions of atoms, where each atom specifies 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 finite automata. The technique shows the power of two-way automata in dealing with the in verse operator and with the variables in the queries. We also characterize the computa tional complexity of both the proposed algo rithm and the problem.