A Logic-Based Approach to Data Integration

John Grant and Jack Minker

• DVI
• PostScript

Abstract

An important aspect of data integration involves answering queries using various resources rather than by accessing database relations. The process of transforming a query from the database relations to the resources is often referred to as query folding or answering queries using views, where the views are the resources. We present a uniform approach that includes as special cases much of the previous work on this subject. Our approach is logic-based using resolution. We deal with integrity constraints, negation, and recursion also within this framework.

Bibliography

• [1] K.R. Apt, H.A. Blair, and A. Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89--148. Morgan Kaufmann Pub., Los Altos, California, 1988.
• [2] S. Abiteboul and O.M. Duschka. Complexity of answering queries using materialized views. In {\em Proceedings Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 98)}, pages 254--263, Seattle, Washington, June 1-3 1998. Association for Computing Machinery.
• [3] F. N. Afrati, M. Gergatsoulis, and T. Kavalieros. Answering queries using materialized views with disjunctions. In C. Beeri and P. Buneman, editors, ICDT'99, LNCS 1540, pages 435--452. Springer-Verlag, 1998.
• [4] G.S. Boolos and R.C. Jeffrey. Computability and Logic. Open University Set Book. Cambridge University Press, third edition, 1989.
• [5] F.Bry. Query evaluation in recursive databases: bottom-up and top-down reconciled. Data \& Knowledge Engineering, pages 289--312, 1990.
• [6] U. Chakravarthy, J. Grant, and J. Minker. Logic-based approach to semantic query optimization. ACM Transactions on Database Systems, 15(2):162--207, June 1990.
• [7] S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In Proceedings of the 11th ICDE, pages 190--200, 1995.
• [8] K.L. Clark. Negation as Failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 293--322. Plenum Press, New York, 1978.
• [9] S. Kumar Das. Deductive Databases and Logic Programming. Addison-Wesley, Wokingham, England, 1992.
• [10] O.M. Duschka and M.R. Genesereth. Answering recursive queries using views. In Proceedings Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 97), pages 109--116, Tucson, Arizona, May 12-14 1997. Association for Computing Machinery.
• [11] O.M. Duschka, M. Genesereth, and A.Y. Levy. Recursive query plans for data integration. Journal of Logic Programming, 43(1):49--73, April 2000.
• [12] S. Dawson, J. Gryz, and X. Qian. Query folding with functional dependencies. Technical report, Computer Science Laboratory, SRI International, Menlo Park, CA, 1996.
• [13] A. Deutsch, L. Popa, and V. Tannen. Physical data independence, constraints, and optimization with universal plans. In Proc. VLDB'99, pages 459--470, 1999.
• [14] O. Duschka. Query Planning and Optimization in Information Integration. PhD thesis, Stanford University, Stanford, California, December 1997.
• [15] T. Eiter, G. Gottlob, and H. Mannila. Disjunctive datalog. ACM Transactions on Database Systems, 22(3):364--418, September 1997.
• [16] F. Fages. A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics. New Generation Computing, 9:425--443, 1991.
• [17] S. Flesca and S. Greco. Rewriting queries using views. IEEE TKDE, 2000. To appear.
• [18] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In R.A. Kowalski and K.A. Bowen, editors, Proc. 5th International Conference and Symposium on Logic Programming}, pages 1070--1080, Seattle, Washington, August 15-19 1988.
• [19] A. Van Gelder, K. Ross, and J.S. Schlipf. Unfounded sets and well-founded semantics for general logic programs. In Proceedings of the 7th Symposium on Principles of Database Systems}, pages 221--230, 1988.
• [20] J. Gryz. Query folding with inclusion dependencies. In Proc. of 14th ICDE, Orlando, Florida, 1998.
• [21] A.Y. Levy. Answering queries using views: A survey. http://www.cs.washington.edu/homes/alon/site/CategoryPage_CN1298094391.html, 1999. Submitted for publication, available on the web.
• [22] J.~W. Lloyd. Foundations of Logic Programming. Symbolic Computation---Artificial Intelligence. Springer-Verlag, Berlin, second edition, 1987.
• [23] J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. M.I.T. Press, Cambridge, Massachusetts, 1992.
• [24] A.Y. Levy, A.O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS-95, May 1995.
• [25] A.Y. Levy, A. Rajaraman, and J.J. Ordille. Query-answering algorithms for information agents. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI), 1996.
• [26] A.Y. Levy, A. Rajaraman, and J.J. Ordille. Querying heterogeneous information sources using source-descriptions. In Proceedings of the 22nd International Conference on Very Large Databases, Bombay, India, 1996.
• [27] P.A. Larson and H.Z. Yang. Computing queries from derived relations. In Proc. VLDB'85, pages 259--269, 1985.
• [28] J. Minker. Logic and databases: a 20 year retrospective. In Workshop on Logic in Databases, San Miniato, Italy, July 1996. Invited Keynote Address.
• [29] J. Minker and J-M. Nicolas. On recursive axioms in deductive databases. Information Systems, 7(4):1--15, 1982.
• [30] J. Melton and A.R. Simon. Understanding the New SQL: A Complete Guide. Morgan Kaufmann, San Mateo, California, 1993.
• [31] J.F. Naughton and Y. Sagiv. A decidable class of bounded recursions. Proc. of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 227--236, March 1987.
• [32] L. Popa, A. Deutsch, A. Sahuguet, and V. Tannen. A chase too far? In Proc. ACM SIGMOD 2000, pages 273--284, 2000.
• [33] X. Qian. Query folding. In Proceedings of the 12th International Conference on Data Engineering, pages 48--55, 1996.
• [34] R. Reiter. Deductive question-answering on relational data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 149--177. Plenum Press, New York, 1978.
• [35] R. Reiter. On Closed World Data Bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55--76. Plenum Press, New York, 1978.
• [36] J.A. Robinson. A machine-oriented logic based on the resolution principle. J.ACM, 12(1), January 1965.
• [37] A. Rajaraman, Y. Sagiv, and J.D. Ullman. Answering queries using templates with binding patterns. In Proceedings Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 95). Association for Computing Machinery, 1995.
• [38] O.G. Tsatalos, M.H. Solomon, and Y.E. Ioannidis. The GMAP: a versatile tool for physical data independence. In Proc. VLDB'94367--378, 1994.
• [39] J.D. Ullman. Principles of Database and Knowledge-Base Systems, Volumes I \& II. Principles of Computer Science Series. Computer Science Press, Incorporated, Rockville, Maryland, 1988/1989.
• [40] J.D. Ullman. Information integration using logical views. In Proceedings of the Sixth International Conference on Database Theory (ICDT'97), Delphi, Greece, January 1997.
• [41] A. Van Gelder. Negation as failure using tight derivations for general logic programs. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 149--176. Morgan Kaufmann, 1988.
• [42] H.Z. Yang and P.A. Larson. Query transformation for PSJ-queries. In Proceedings of the Thirteenth International Conference on Very Large Data Bases, pages 245--254, 1987.