Abstract
We consider the problem of answering datalog queries using materialized views. More specifically, queries are rewritten to refer to views instead of the base relations over which the queries were originally written. Much work has been done on program rewriting that produces an equivalent query. In the context of information integration, though, the importance of using views to infer as many answers as possible has been pointed out. Formally, the problem is: Given a datalog program P is there a datalog program P v which uses only views as EDB predicates and (i) produces a subset of the answers that P produces and (ii) any other program P′ v over the views with property (i) is contained in P v ? In this paper we investigate the problem in the case of disjunctive view definitions.
This work has been partially supported by the Greek General Secretariat of Research and Technology under the project “Logic Programming Systems and Environments for developing Logic Programs” of ΠENEΔ′95, contract no 952.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul and O. Duschka. Complexity of answering queries using materialized views. In Proc. ACM Symposium on Principles of Database Systems, 1998.
Serge Abiteboul. Querying semi-structured data. In Proceedings of the Sixth International Conference on Database Theory, pages 1–18. Springer-Verlag, 1997.
F. Afrati, S. Cosmadakis, and M. Yannakakis. On datalog vs. polynomial time. J. Computer and Systems Sciences, 51(2):117–196, 1995.
Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, and Kyuseak Shim. Optimizing queries with materialized views. In Proceedings of the 11th International Conference on Data Engineering, Los Alamitos, CA, pages 190–200. IEEE Comput. Soc. Press, 1995.
Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. In Proceedings of the Sixth International Conference on Database Theory, pages 56–70. Springer-Verlag, 1997.
Oliver M. Duschka. Query Planning and Optimization in Information Integration. PhD thesis, Stanford University, December 1997.
Oliver M. Duschka and Michael R. Genesereth. Answering recursive queries using views. In Proc. 16th ACM SIGACT-SIGMOD-GIGART Symposium on Principles of Database Systems, pages 109–116, 1997.
Oliver M. Duschka and Michael R. Genesereth. Query planning with disjunctive sources. In Proc. of the AAAI-98 Workshop on AI and Information Integration, 1998.
M. Gergatsoulis. Correctness-preserving transformations for disjunctive logic programs. Demo 97/2, Institute of Informatics & Telecom. NCSR ‘Demokritos’, 1997.
Manolis Gergatsoulis. Unfold/fold transformations for disjunctive logic programs. Information Processing Letters, 62(1):23–29, April 1997.
M. A. Harrison. Introduction to formal language theory. Addison-Wesley, 1978.
Nam Huyn. A more aggressive use of views to extract information. Technical Report STAN-CS-TR-96-1577, Stanford University, Computer Science Department, 1996.
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering queries using views. In Proc. 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 95–104, 1995.
Alon Y. Levy, Divest Srivastava, and Thomas Kirk. Data model and query evaluation in global information systems. Journal of Intelligent Information Systems, 1995. Special Issue on Networked Information Discovery and Retrieval.
J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, 1992.
Anand Rajaraman, Yehoshua Sagiv, and Jeffrey D. Ullman. Answering queries using templates with binding patterns. In Proc. 14th ACM SIGACT-SIGMOD-GIGART Symposium on Principles of Database Systems, San Jose, CA, 1995.
Oded Shmueli. Decidability and expressiveness aspects of logic queries. In Proc. 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 237–249, 1987.
Jeffrey D. Ullman. Principles of Database and Knowledge-Base Systems, volume I & II. Computer Science Press, 1989.
Jeffrey D. Ullman. Information integration using logical views. In Proceedings of the Sixth International Conference on Database Theory, pages 19–40. Springer-Verlag, 1997.
Jeffrey D. Ullman and Allen Van Gelder. Parallel complexity of logical query programs. In Proc. 27th IEEE Symp. on Foundations of Comp. Sci., pages 438–454, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Afrati, F.N., Gergatsoulis, M., Kavalieros, T. (1999). Answering Queries Using Materialized Views with Disjunctions. In: Beeri, C., Buneman, P. (eds) Database Theory — ICDT’99. ICDT 1999. Lecture Notes in Computer Science, vol 1540. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49257-7_27
Download citation
DOI: https://doi.org/10.1007/3-540-49257-7_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65452-0
Online ISBN: 978-3-540-49257-3
eBook Packages: Springer Book Archive