Synonyms
Datalog query processing and optimization; Logical query processing and optimization; Recursive query evaluation
Definition
Most of the research work on deductive databases has concerned the Datalog language, a query language based on the logic programming paradigm which was designed and intensively studied for about a decade. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1978, when Hervé Gallaire and Jack Minker organized a workshop on logic and databases. In this entry, the definition of the typical computation styles of Datalog will be given, the most important optimization types will be summarized, and some developments will be outlined.
Historical Background
The research on deductive databases was concentrated mostly between the mid-1980s and the mid-1990s. In those years, substantial efforts were made to merge Artificial Intelligence technologies with those of the database area, with the aim of building larg...
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Bancilhon F, Maier D, Sagiv Y, Ullman JD. Magic sets and other strange ways to implement logic programs. In: Proceedings of the 5th ACM SIGACT SIGMOD Symposium on Principles of Database Systems; 1986. p. 1–15. Available at: https://pdfs.semanticscholar.org/1289/85b85556c30ad405863f2a34340049957616.pdf
Ceri S, Gottlob G, Tanca L. Logic programming and databases. Berlin: Springer; 1990.
Chandra AK, Harel D. Horn clauses queries and generalizations. J Log Program. 1985;2(1):1–15.
Ullman JD. Principles of database and Knowledge-Base systems. IRockville: Computer Science Press; 1988.
Bocca JB. EDUCE: a marriage of convenience: Prolog and a Relational DBMS. In: Proceedings of the Symposium in Logic Programming; 1986. p. 36–45.
Tsur S, Zaniolo C. LDL: a logic-based data language. In: Proceedings of the 12th International Conference on Very Large Data Bases; 1986. p. 33–41. Available at: https://dl.acm.org/citation.cfm?id=671478.
Abiteboul S, Hull R, Vianu V. Foundations of 510 databases. Reading: Addison-Wesley; 1995.
Lloyd JW. Foundations of logic programming. 2nd ed. Berlin: Springer; 1987. ISBN:3-540-18199-7.
Kowalski RA, Kuehner D. Linear resolution with selection function. Artif Intell. 1971;2(3–4):227–60.
Chakravarthy US, Minker J, Grant J. Semantic query optimization: additional constraints and control strategies. In: Proceedings of the Expert Database Conference; 1986. p. 345–79.
Sacca D, Zaniolo C. Stable models and non-determinism in logic programs with negation. In: Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems; 1990. p. 205–217. Available at: https://dl.acm.org/citation.cfm?id=298572.
Laenens E, Vermeir D. Assumption-free semantics for ordered logic programs: on the relationship between well-founded and stable partial models. J Log Comput. 1992;2(2):133–72.
Behrend A. Soft stratification for magic set based query evaluation in deductive databases. In: Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems; 2003. p. 102–10. Available at: https://dl.acm.org/citation.cfm?id=773164.
Comai S, Tanca L. Termination and confluence by rule prioritization. IEEE Trans Knowl Data Eng. 2003;15(2):257–70.
W3C Member Submission. SWRL: a semantic Web rule language combining OWL and RuleML. 2004. Available at: http://www.w3.org/Submission/SWRL/
Ameloot TJ. Declarative networking: recent theoretical work on coordination, correctness, and declarative semantics. SIGMOD Rec. 2014;43(2):5–16. Available at: http://www.sigmod.org/publications/sigmod-record/1406/pdfs/03.principles.Ameloot.pdf.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2018 Springer Science+Business Media, LLC, part of Springer Nature
About this entry
Cite this entry
Tanca, L. (2018). Query Processing in Deductive Databases. In: Liu, L., Özsu, M.T. (eds) Encyclopedia of Database Systems. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8265-9_859
Download citation
DOI: https://doi.org/10.1007/978-1-4614-8265-9_859
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-8266-6
Online ISBN: 978-1-4614-8265-9
eBook Packages: Computer ScienceReference Module Computer Science and Engineering