Containment of Conjunctive Queries under Access Limitations

Proc. of the 14th Italian Symp. on Advanced Database Systems (SEBD 2006). 2006.

Relational data may have access limitations, i.e., relations may require certain attributes to be selected when they are accessed; this happens, for instance, while querying web data sources (wrapped in relational form) or legacy databases. It is known that the evaluation of a conjunctive query under access limitations requires a recursive algorithm that is encoded into a Datalog program. In this paper we address the problem of containment of conjunctive queries under access limitations, which is highly relevant in query optimization. Checking containment in this case would amount to check containment of recursive Datalog programs, which is undecidable in general. We show however, that due to the specific form of the Datalog programs resulting from encoding access limitations, the containment problem is in fact decidable. We provide a decision procedure based on chase techniques, and study its computational complexity.

@inproceedings{SEBD-2006,
   title = "Containment of Conjunctive Queries under Access Limitations",
   year = "2006",
   author = "Andrea Calì and Diego Calvanese",
   booktitle = "Proc. of the 14th Italian Symp. on Advanced Database Systems
(SEBD 2006)",
}