Stanford InfoLab Publication Server

Testing Query Containment in the Presence of Binding Restrictions

Li, Chen and Chang, Edward (1999) Testing Query Containment in the Presence of Binding Restrictions. Technical Report. Stanford.




In information-integration systems, sources have diverse and limited query capabilities. In a recent paper \cite{Li99-1}, we showed that sources not mentioned in a query can contribute to the query result by providing useful bindings. We studied {\em connection queries}, where each connection query is a natural join of distinct source views with the necessary selection and projection. Some optimization problems are left open, including whether the answer computed by one connection is contained in that computed by another connection. In this paper we study this connection-containment problem. Since \cite{Li99-1} often produces a recursive Datalog program to answer a connection query optimally, containment seems undecidable. However, because the Datalog programs of \cite{Li99-1} have a special form, their containment can be reduced to containment of monadic programs, which is known to be decidable. Further, the decidability of monadic Datalog programs involves a complex algorithm. We therefore introduce the question of boundedness for the programs of \cite{Li99-1}, and show that boundedness is decidable in polynomial time. We then show in addition that when the contained program is bounded, we have a much simpler algorithm for performing the containment test

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:information-integration systems, binding restrictions, query containment, query equivalence, Datalog programs.
Subjects:Computer Science > Data Integration and Mediation
Related URLs:Project Homepage
ID Code:365
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 09:32

Download statistics

Repository Staff Only: item control page