IDLOG: extending the expressive power of deductive database languages

ABSTRACT

The expressive power of pure deductive database languages, such as DATALOG and stratified DATALOGS, is limited in a sense that some useful queries such as functions involving aggregation are not definable in these languages. Our concern in this paper is to provide a uniform logic framework for deductive databases with greater expressive power. It has been shown that with a linear ordering on the domain of the database, the expressive power of some database languages can be enhanced so that some functions involving aggregation can be defined. Yet, a direct implementation of the linear ordering in deductive database languages may seem unintuitive, and may not be very efficient to use in practice. We propose a logic for deductive databases which employs the notion of “identifying each tuple in a relation”. Through the use of these tuple-identifications, different linear orderings are defined as a result. This intuitively explains the reason why our logic has greater expressive power. The proposed logic language is non-deterministu in nature. However, non-determinism is not the real reason for the enhanced expressive power. A deterministic subset of the programs in this language is computational complete in the sense that it defines all the computable deterministic queries. Although the problem of deciding whether a program is in this subset is in general undecidable, we do provide a rather general sufficient test for identifying such programs. Also discussed in this paper is an extended notion of queries which allows both the input and the output of a query to contain interpreted constants of an infinite domain. We show that extended queries involving aggregation can also be defined in the language.

REFERENCES

• AB88: S Ablteboul and C Been On the power of languages for the mampulatlon of complex objects Manuscmpt, 1988
• ABW88: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• AV87: S. Abiteboul , V. Vianu, A translation language complete for database update and specification, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.260-268, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28688]
• AV88: Serge Abiteboul , Victor Vianu, Procedural and declarative database update languages, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.240-250, March 1988, Austin, Texas, United States [doi>10.1145/308386.308448]
• BR86: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• Ce76: D D Chamberhn and et al Sequel 2 a umfied approach to data definition, mampulatlon, and control IBM Journal of ReseaT ch, 20(6) 560-575, November 1976
• CH80: A K Chandra and D Harel Computable queries for relatmnal databases Journal of Computer and b~lstem Sciences, 21(2) 156-178, October 1980
• CH82: A K Chandra and D Harel Structure and complexity of relational queries Journal of Computer and System Sczences, 25(1) 99-128, August 1982
• CH85: A K Chandra and Harel Horn clause queries and generahzatlons Journal of Log,c ProgTammzng, 1 1-15, 1985
• Cha81: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• Cha88: Ashok K. Chandra, Theory of database queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-9, March 1988, Austin, Texas, United States [doi>10.1145/308386.308396]
• Che88: L Chen Extenmon of datalog with aggregate functions IV 3ournees bases de Donnees Avancees, 1988
• Dah87: Elias Dahlhaus, Skolem normal forms concerning the least fixpoint, Computation theory and logic, Springer-Verlag, London, 1987
• GL88: M Gelfond and V Lffschltz The stable model semantics for logic programnung Proceedzngs of the F,fth Logzc Programmmg Symposzum, 1070-1080, 1988
• HS89: R. Hull , J. Su, Untyped sets, invention, and computable queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.347-359, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73755]
• Imm86: Neil Immerman, Languages which capture complexity classes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.347-354, December 1983 [doi>10.1145/800061.808765]
• KL85: M Klfer and E L Lozmskl Query optzmzzatzon ,n deduct,re databases Technical Report 85/16, Computer Science, SUNY at Stony Brook, Stony Brook, NY 11794, 1985
• KL86: M Klfer and E L Lomnskl A framework for an efficzent zmplementatzon of deductwe databases Techmcal Report 86/4, Computer Science, SUNY at Stony Brook, Stony Brook, NY 11794, February 1986
• Klu82: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• KP88: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
• OOM87: G. Özsoyoğlu , Z. M. Özsoyoğlu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987 [doi>10.1145/32204.32219]
• Prz88a: T. C. Przymusinski, On the declarative and procedual semantics of logic programs, Journal of Automated Reasoning, v.5 n.2, p.167-205, June 1989
• Prz88b: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• RBK88: R Ramaknshnan, C Been, and R Knshnamurthy Optimizing exlstentml Datalog queries 1988 Draft
• Rei83: R Relter Towards a logical reconstructmn of relatmnal database theory In M L Brodle, J Mylopoulos, and J Schnudt, editors, On Conceptual Modelhng Perspectzves from Artzfic,al Intelhgence, Databases and ProgTamm~ng Languages, Spnnger-Verlag, 1983
• Saz80: V Sazonov Polynomml computability and recursxvlt:v m fimte dommns Elektromsche Informat,onverarbe~tung und Kybernetzk, 16 319-323, 1980
• She90: Y Sheng The expressive power of deduchve database languages with tuplexdentlficatmns 1990 m preparation
• Ull82: J D Ullman Pmnczples of Database Systems Computer Scmnce Press, second edltmn, 1982
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• VG88: A. V. Gelder, Negation as failure using tight derivations for general logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• VGRS88: A Van Gelder, K A Ross, and ~I S Schhpf Well-founded semantzcs for general logic progTams Techmcal Report UCSC-CRL-88-16, Umverslty of Calfforma, Santa Cruz, Umversity of Cahforma, Santa Cruz, CA 95064, March 1988
• Zan86: C Zamolo Safety and compflatmn ofnonrecurslve horn clauses Proceedings of o} the 1st Ezpert Database Conf , 1986

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory; Logic and constraint programming

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages