Optimizing Query Planning with Limited Source Capabilities in the Presence of Inclusion and Functional Dependencies

Proc. of the 9th Italian Symp. on Advanced Database Systems (SEBD 2001). 2001.

Information Integration is the problem of providing a uniform access to multiple and heterogeneous data sources. The most common approach to this problem, called "Global-as-View", consists in providing a global schema of data in which each relation of such a schema is defined as a view over a set of data sources. Recent works deal with this problem in the case of limited source capabilities, where in general sources can only be accessed respecting certain binding patterns for their attributes. In this case, computing the answer to a query over the global schema cannot be done by simply unfolding the global relations with their definitions. Instead, it may require the evaluation of a suitable recursive datalog program. In this paper we study query evaluation in the Global-as-View approach with limited source capabilities in the presence of full inclusion and functional dependencies between sources. We present a polynomial time algorithm for implication of such kind of dependencies and we study how the presence of such dependencies enables one to minimize the number of accesses to the sources. We provide necessary and sufficient conditions for determining whether, during query evaluation, a given source has to be accessed or not.

@inproceedings{SEBD-2001,
   title = "Optimizing Query Planning with Limited Source Capabilities in the
Presence of Inclusion and Functional Dependencies",
   year = "2001",
   author = "Andrea Calì and Diego Calvanese",
   booktitle = "Proc. of the 9th Italian Symp. on Advanced Database Systems
(SEBD 2001)",
   pages = "33--44",
}