Abstract
Declarative languages for deductive and object-oriented databases require some high-level mechanism for specifying semantic control knowledge. This paper proposes user-supplied subsumption information as a paradigm to specify desired, prefered or useful deductions at the meta level. For this purpose we augment logic programming by subsumption relations and succeed to extend the classical theorems for least models, fixpoints and bottom-up evaluation accordingly. Moreover, we provide a differential fixpoint operator for efficient query evaluation in deductive databases. This operator discards subsumed tuples on the fly. We also exemplify the ease of use of this programming methodology. In particular, we demonstrate how heuristic AI search procedures can be integrated into deductive databases in this way.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Hassan Ait-Kaci. Type subsumption as a model of computation. InProc. Int'l. Workshop on Expert Database Systems. Benjamin Cummings Company, 1985.
A. Artale, F. Cesarini, and G. Soda. Introducing knowledge representation techniques in database models. InTrends in Artificial Intelligence, Proc. 2nd Congr. of the Italian Association for Art. Int., pages 375–384, Palermo, Italy, Oct. 1991. Springer-Verlag.
Isaac Balbin and Kotagiri Ramamohanarao. A generalization of the differential approach to recursive query evaluation.Journal of Logic Programming, 4(3):259–262, 1887.
Francois Bancilhon. Naive evaluation of recursively defined relations. In Brodie and Mylopoulos, editors,On Knowledge Base Management Systems — Integrating Database and AI Systems. Springer-Verlag, 1985.
Rudolf Bayer. Query evaluation and recursion in deductive database systems. Technical Report I8503, Technische Universität München, Feb. 1985.
Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, and S. Sudarshan. The valid model semantics for logic programs. InProc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, pages 91–104, San Diego, CA, Jun. 1992. ACM Press.
G. Birkhoff.Lattice Theory, volume 25 ofAmer. Math. Soc. Colloq. Publ. Providence, Rhode Island, USA, 1967.
U. S. Chakravarthy, J. Grant, and J. Minker. Logic-based approach to semantic query optimization.ACM Trans, on Database Systems, 15(2):162–207, 1990.
Sumit Ganguly, Sergio Greco, and Carlo Zaniolo. Minimum and maximum predicates in logic programming. InProc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, pages 154–163, Denver, CO, May 1991. ACM Press.
Allen Van Gelder. The well-founded semantics fo aggregation. InProc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, pages 127–138, San Diego, CA, Jun. 1992.
Allen Van Gelder. Foundations of aggregation in deductive databases. In Stefano Ceri, Katsumi Tanaka, and Shalom Tsur, editors,Proc. 3rd Int'l. Conf. on Deductive and Object-Oriented Databases, volume 760 ofLNCS, pages 13–34, Phoenix, AZ, USA, Dec. 1993.
Ulrich Güntzer, Werner Kießling, and Rudolf Bayer: On the evaluation of recursion in (deductive) database systems by efficient differential fixpoint iteration. InProc. IEEE Conf. on Data Eng., pages 120–129, Los Angeles, CA, Feb. 1987.
Ulrich Güntzer, Werner Kießling, and Helmut Thöne. New directions for uncertainty reasoning in deductive databases. InProc. ACM SIGMOD Conf., pages 178–187, Denver, CO, May 1991.
D. B. Kemp and P. J. Stuckey. Semantics of logic programs with aggregates. InProc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, pages 387–401, Denver, CO, May 1991.
Werner Kießling and Ulrich Güntzer. Database reasoning— a deductive framework for solving large and complex problems by means of subsumption. InProc. 3rd Workshop on Information Systems and Artificial Intelligence, volume 777 ofLNCS, pages 118–138, Hamburg, Germany, Febr. 1994.
Werner Kießling, Gerhard Köstler, and Ulrich Güntzer. Fixpoint evaluation with subsumption for probabilistic uncertainty. InGI-Conference on Datenbanksysteme in Büro, Technik und Wissenschaft (BTW'93), pages 316–333, Braunschweig, Germany, Mar. 1993. Springer-Verlag.
Werner Kießling, Helmut Thöne, and Ulrich Güntzer. Database support for problematic knowledge. InProc. Int'l. Conf. on Extending Database Technology, pages 421–436, Vienna, Austria, 1992.
Michael Kifer and James Wu. A logic for programming with complex objects.Journal of Computer and System Sciences, 47(1):77–120, Aug. 1993.
Byeong Man Kim and Jung Wan Cho. A new subsumption method in the connection graph proof procedure.Theoretical Computer Science, 2:283–309, 1992.
Gerhard Köstler, Werner Kießling, Helmut Thöne, and Ulrich Güntzer. The differential fixpoint operator with subsumption. In Stefano Ceri, Katsumi Tanaka, and Shalom Tsur, editors,Proc. 3rd Int'l. Conf. on Deductive and Object-Oriented Databases, volume 760 ofLNCS, pages 35–48, Phoenix, AZ, USA, Dec. 1993.
James B. H. Kwa. BS*: An admissible bidirectional staged heuristic search algorithm.Artificial Intelligence, 38:95–109, 1989.
J.W. Lloyd.Foundations of Logic Programming. Springer-Verlag, Berlin, second edition, 1987.
Michael J. Maher and Raghu Ramakrishnan. Déjà vu in fixpoints of logic programs. InNorth American Conference on Logic Programming, pages 963–980, Cleveland, OH, 1989.
Nils J. Nilsson.Principles of Artificial Intelligence. Tioga Publishing Company, Palo Alto, CA, 1980.
Peter F. Patel-Schneider. A four-valued semantics for terminological logics.Artificial Intelligence, 38(3):318–352, 1989.
Raghu Ramakrishnan, Divesh Srivastava, and S. Sudarshan. CORAL—Control, Relations and Logic. InProc. Int'l. Conf. on Very Large Data Bases, pages 238–250, Vancouver, BC, Canada, 1992.
Kenneth Ross and Yehoshua Sagiv. Monotonic aggregation in deductive databases. InProc. ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, pages 114–126, San Diego, CA, Jun. 1992. ACM Press.
Helmut Schmidt, Werner Kießling, Ulrich Güntzer, and Rudolf Bayer. Compiling exploratory and goal directed deduction into sloppy delta-iteration. InProceedings of the Symposium on Logic Programming, pages 233–243, San Francisco, CA, Sep. 1987.
Helmut Schmidt, Werner Kießling, Ulrich Güntzer, and Rudolf Bayer. DBA*: Solving combinatorial problems with deductive databases. InProc. GI/SI-Conference on Datenbanksysteme in Büro, Technik und Wissenschaft (BTW'89), pages 196–215, Zürich, Switzerland, 1989.
S. Sudarshan and Raghu Ramakrishnan. Aggregation and relevance in deductive databases. InProc. Int'l. Conf. on Very Large Data Bases, pages 501–511, Barcelona, Spain, Sept. 1991.
A. Tarski. A lattice-theoretical fixpoint theorem and its applications.Pacific J. Math., 5:285–309, 1955.
Carlo Zaniolo, Natraj Arni, and Kayliang Ong. Negation and aggregates in recursive rules: The LDL++ approach. In Stefano Ceri, Katsumi Tanaka, and Shalom Tsur, editors,Proc. 3rd Int'l. Conf. on Deductive and Object-Oriented Databases, volume 760 ofLNCS, pages 204–221, Phoenix, AZ, USA, Dec. 1993.
Author information
Authors and Affiliations
Additional information
This article is a revised and extended version of (Köstler et al., 1993)
Rights and permissions
About this article
Cite this article
Köstler, G., Kiessling, W., Thöne, H. et al. Fixpoint iteration with subsumption in deductive databases. J Intell Inf Syst 4, 123–148 (1995). https://doi.org/10.1007/BF00961871
Issue Date:
DOI: https://doi.org/10.1007/BF00961871