Search
1989 Volume 4
Article Contents
RESEARCH ARTICLE   Open Access    

Deductive database theories*

More Information
  • Abstract: This paper surveys a variety of deductive database theories. Such theories differ from one another in the set of axioms and metarules that they allow and use. The following theories are discussed: relational, Horn, and stratified in the text; protected, disjunctive, typed, extended Horn, and normal in the appendix. Connections with programming in terms of the declarative, fixpoint, and procedural semantics are explained. Negation is treated in several different ways: closed world, completed database, and negation as failure. For each theory examples are given and implementation issues are considered.
  • 加载中
  • Gallaire H and Minker J, Eds, 1978. Logic and Databases, New York: Plenum.

    Google Scholar

    Gallaire H, Minker J and Nicolas J, 1984. “Logic and databases: A deductive approach” ACM Computing Surveys16153–185.

    Google Scholar

    Minker J, 1987. “Deductive databases: An overview of some alternative theories” In Ras ZW and Zemankova M, Eds, Methodologies for Intelligent Systems, Amsterdam: Elsevier, pp. 148–158.

    Google Scholar

    Minker J, Ed., 1988. Foundations of Deductive Databases and Logic Programming, California: Morgan Kaufmann.

    Google Scholar

    Minker J, 1988a. “Perspectives in deductive databases” The Journal of Logic Programming533–60.

    Google Scholar

    Ullman JD, 1988. Principles of Database and Knowledge-Base Systems, Volumes I and II, Maryland: Computer Science Press.

    Google Scholar

    Chang CL and Lee RTC, 1973. Symbolic Logic and Mechanical Theorem Proving, New York: Academic Press.

    Google Scholar

    Enderton HB, 1972. A Mathematical Introduction to Logic, New York: Academic Press.

    Google Scholar

    Lloyd JW, 1987. Foundations of Logic Programming, Second Extended Edition, New York: Springer-Verlag.

    Google Scholar

    Loveland D, 1978. Automated Theorem Proving: A Logical Basis, Amsterdam: Elsevier North-Holland.

    Google Scholar

    Mendelson E, 1978. Introduction to Mathematical Logic, 2nd Ed., New York: van Nostrand-Reinhold.

    Google Scholar

    Grant J and Minker J, 1990. “Integrity constraints in knowledge based Systems”, In Adeli H, Ed., Knowledge Engineering, Vol. II, Applications, New York: McGraw-Hill, pp. 1–25.

    Google Scholar

    Nicolas J and Gallaire H, 1978. “Data base: Theory vs interpretation” In Gallaire H and Minker J, Eds, Logic and Databases, New York: Plenum, pp. 33–54.

    Google Scholar

    van Emden MH and Kowalski R, 1976. “The semantics of predicate logic as a programming language” Journal of the ACM23733–742.

    Google Scholar

    Chan C, 1988. “Constructive negation based on the completed database”, In Kowalski, RA and Bowen, KA, Eds, Logic Programming Proceedings of the Fifth International Conference and Symposium,Massachusetts:The MIT Press, pp. 111–125.

    Google Scholar

    Clark KL, 1978. “Negation as failure” In Gallaire H and Minker J, Eds, Logic and Databases, New York: Plenum, pp. 293–322.

    Google Scholar

    Reiter R, 1978. “On closed world databases” In Gallaire H and Minker J, Eds, Logic and Databases, New York: Plenum, pp. 149–178.

    Google Scholar

    Shepherdson JC, 1988. “Negation in logic programming” In Minker J, Ed., Foundations of Deductive Databases and Logic Programming, California: Morgan Kaufmann, pp. 19–88.

    Google Scholar

    Apt KR, Blair HA and Walker A, 1988. “Towards a theory of declarative knowledge” In Minker J, Ed., Foundations of Deductive Databases and Logic Programming, California: Morgan Kaufmann, pp. 89–148.

    Google Scholar

    Chandra A and Harel D, 1985. “Horn clause queries and generalizations” The Journal of Logic Programming21–15.

    Google Scholar

    Gelfond M, Przymusinska H and Przymusinski T, 1989. “On the relationship between circumscription and negation as failure” Artificial Intelligence3875–94.

    Google Scholar

    Naqvi SA, 1986. “A logic for negation in database Systems” In Minker J, Ed., Proceedings of the Workshop on Foundations of Deductive Databases and Logic ProgrammingWashington, D.C., pp. 378–387.

    Google Scholar

    Naqvi SA and Tsur S, 1989. A Logical Language for Data and Knowledge Bases, Maryland: Computer Science Press.

    Google Scholar

    Przymusinski TC, 1988a. “On the declarative semantics of deductive databases and logic programs”, In Minker J, Ed., Foundations of Deductive Databases and Logic Programming, California: Morgan Kaufmann, pp. 193–216.

    Google Scholar

    Przymusinski TC, 1988b. “On the declarative and procedural semantics of logic programs” Journal of Automated Reasoning4.

    Google Scholar

    Van Gelder A, 1988. “Negation as failure using tight derivations for general logic programs” In Minker J, Ed., Foundations of Deductive Databases and Logic Programming, New York: Morgan Kaufmann, pp. 149–176.

    Google Scholar

    Minker J and Perlis D, 1985. “Computing protected circumscription” The Journal of Logic Programming4 pp. 235–249.

    Google Scholar

    Bossu G and Siegel P, 1985. “Saturation, non-monotonic reasoning and the closed-world assumption” Artificial Intelligence25 13–63.

    Google Scholar

    Grant J and Minker J, 1986. “Answering queries in indefinite databases and the null value problem” In Kanellakis P, Ed., Advances in Computing Theory, Vol. 3, The Theory of of Databases, JAI Press, pp. 247–267.

    Google Scholar

    Henschen LJ and Park H-S, 1988. “Compiling the GCWA in indefinite deductive databases”, In Minker J, Ed., Foundations of Deductive Databases and Logic Programming, California: Morgan Kaufmann, pp. 295–438.

    Google Scholar

    Lobo J, Minker J and Rajasekar A, 1988. “Weak completion theory for non-Horn programs”, In Kowalski RA and Bowen KA, Eds, Logic Programming Proceedings of the Fifth International Conference and Symposium, Massachusetts: MIT Press, pp. 828–842.

    Google Scholar

    Minker J, 1982. “On indefinite databases and the closed world assumption”, In Proc. of the 6th Conference on Automated Deduction, Springer-Verlag Lecture Notes in Computer Science No. 138,New York:Springer-Verlag, pp. 292–308.

    Google Scholar

    Minker J and Rajasekar A, 1989. “A fixpoint semantics for non-Horn logic programs” The Journal of Logic Programming.

    Google Scholar

    Minker J and Zanon G, 1982. “An extension to linear resolution with selection function” Information Processing Letters14 pp. 191–194.

    Google Scholar

    Rajasekar A, Lobo J and Minker J, 1989. “Weak generalized closed world assumption”, Journal of Automated Reasoning5293–307.

    Google Scholar

    Ross KA and Topor RW, 1988. “Inferring negative information from disjunctive databases” Journal of Automated Reasoning4397–424.

    Google Scholar

    Yahya A and Henschen LJ, 1985. “Deduction in non-Horn databases” Journal of Automated Reasoning1141–160.

    Google Scholar

    Reiter R, 1984. “Towards a logical reconstruction of relational database theory”, In Brodie ML, Mylopoulos J and Schmidt JW, Eds, On Conceptual Modelling, New York: Springer-Verlag, pp. 191–233.

    Google Scholar

    Lloyd JW and Topor RW, 1984. “Making Prolog more expressive” Journal of Logic Programming1225–240.

    Google Scholar

    Lloyd JW and Topor RW, 1985. “A basis for deductive database Systems” Journal of Logic Programming293–109.

    Google Scholar

    Lloyd JW and Topor RW, 1986. “A basis for deductive database Systems II” Journal of Logic Programming3 pp. 55–67.

    Google Scholar

    Przymusinski TC, 1989. “Every logic program has a natural stratification and an iterated least fixed point model” In Proc. of ACM PODS11–21.

    Google Scholar

    Van Gelder A, Ross KA and Schlipf JS, 1988. “Unfounded sets and well-founded semantics for general logic programs” In Proc. of ACM PODS221–230.

    Google Scholar

  • Cite this article

    John Grant, Jack Minker. 1989. Deductive database theories*. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900005129
    John Grant, Jack Minker. 1989. Deductive database theories*. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900005129

Article Metrics

Article views(24) PDF downloads(992)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Deductive database theories*

The Knowledge Engineering Review  4 Article number: 10.1017/S0269888900005129  (1989)  |  Cite this article

Abstract: Abstract: This paper surveys a variety of deductive database theories. Such theories differ from one another in the set of axioms and metarules that they allow and use. The following theories are discussed: relational, Horn, and stratified in the text; protected, disjunctive, typed, extended Horn, and normal in the appendix. Connections with programming in terms of the declarative, fixpoint, and procedural semantics are explained. Negation is treated in several different ways: closed world, completed database, and negation as failure. For each theory examples are given and implementation issues are considered.

    • Copyright © Cambridge University Press 19891989Cambridge University Press
References (43)
  • About this article
    Cite this article
    John Grant, Jack Minker. 1989. Deductive database theories*. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900005129
    John Grant, Jack Minker. 1989. Deductive database theories*. The Knowledge Engineering Review. 4: doi: 10.1017/S0269888900005129
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return