Containment of Conjunctive Regular Path Queries with Inverse

Proc. of the 7th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2000). 2000.

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 verification, 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 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 inverse operator and with the variables in the queries. We also characterize the computational complexity of both the proposed algorithm and the problem.

@inproceedings{KR-2000,
   title = "Containment of Conjunctive Regular Path Queries with Inverse",
   year = "2000",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   booktitle = "Proc. of the 7th Int. Conf. on Principles of Knowledge
Representation and Reasoning (KR 2000)",
   pages = "176--185",
}