## Containment of Conjunctive Regular Path Queries with
Inverse

**Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and
Moshe Y. Vardi**
*Proc. of the 7th Int. Conf. on the 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 the Principles of Knowledge
Representation and Reasoning (KR 2000)",
pages = "176--185",
}

ps.gz
pdf