An implementation model for reasoning with complex objects

ABSTRACT

In this paper, we first propose a natural syntactical extension of DATALOG called NESTED_DATALOG for dealing with complex objects represented as nested predicates. Then, we introduce the token object model which is a simple extension of the relational model with tokens to represent complex objects and support referential information sharing. An implementation model of a NESTED_DATALOG program is defined by mapping it to the token object model which remains a straightforward extension of classical logical databases. Through this work, we can accommodate two basic requirements. The availability of a rule language for reasoning with complex objects, and the mechanism for mapping a complex object rule program to a relational DBMS offering a pure DATALOG rule language. In summary, the main contributions of the paper are the definition of a rule language for complex objects and the development of a technique to compile this complex object rule language to classical DATALOG.

REFERENCES

• Abiteboul 87: S Ablteboul, S Grumbach, "Une Approche Loglque de la Mampulatlon d'objets Complexes", 3e Joum~es BD3, Port Camargue, Mal 1987
• Al-Amoudi87: Al-Amoudl S, Harper D, "On Compiling Loglc Programming Languages into Conventional Relational Algebra Operations", Internal Report, Umverslty of Glasgow, UK, 1987
• Apt86: Apt K R-, Blatr H, Walker A ,"Towards a Theory of Declarative Knowledge". IBM Research Report RC 11681, Aprtl 1986, xn Proc Workshop on Foundattons of Deducuve Databases and Logic Programming, Washington D C, pp 546,629, 1986
• Bancilhon 86: F Bancflhon and S Khoshafian, "Objects Calculus", Proc PODS, 1986
• Beeri 86: C Been et al, "Sets and Negation m a Logic Database Language LDLI", MCC Tec Rep, 1986
• Chen 86: Qiming Chen, A rule-based object/task modelling approach, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.281-292, May 28-30, 1986, Washington, D.C., United States
• Chen 87: Q Chen, "An Extended Object-Onented Database approach", Approach", Proc of COMPSAC 87. Japan, 1987
• Gardarin 87a: Georges Gardarin, Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs, Proceedings of the 13th International Conference on Very Large Data Bases, p.21-30, September 01-04, 1987
• Gardarin 87b: G Gardarm, E Simon, "Les Syst~mes de Bases de Donn?,es D&tuctlves", TSI, Dunod Ed, March 1988, m French
• Gardarin88: G Gardarm, P Valdunez, "Prmclples and Algorithms of Relauonal Database Systems", Book, Addison-Wesley, 1988
• Gallaire84: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• Khoshafian 86: Setrag N. Khoshafian , George P. Copeland, Object identity, Conference proceedings on Object-oriented programming systems, languages and applications, p.406-416, September 29-October 02, 1986, Portland, Oregon, United States
• Kiernan87: KJernan G, Monze i, "Braiding an Object~ oriented Interface Over an Extended Relational Backend", Progress Report. ISIDE ESPRIT Project. N 221, Oct 1987
• Kuper 87: G. M. Kuper, Logic programming with sets, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-20, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28661]
• Maier 83: Andreas Meier , Raymond A. Lorie, A Surrogate Concept for Engineering Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.30-32, October 31-November 02, 1983
• Reiter84: Retter R "Towards a Logxcal Reconstruction of Relational Database Theor3,", m On Conceptual Modelhng, Book, Pp 191-234, Sprmger-Verlag Ed. 1984
• Tsur 86: Shalom Tsur , Carlo Zaniolo, LDL: A Logic-Based Data Language, Proceedings of the 12th International Conference on Very Large Data Bases, p.33-41, August 25-28, 1986
• Woelk 86: Darrell Woelk , Won Kim , Willis Luther, An object-oriented approach to multimedia databases, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.311-325, May 28-30, 1986, Washington, D.C., United States
• Zaniolo 85: C Zaniolo, "The Representation and Deductive Retrieval of Complex Objects", Proc VLDB 11, Stockolm, 1985

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing

          Nouns: DATALOG

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Languages, Theory, Verification