Data Constructors: On the Integration of Rules and Relations.

@inproceedings{DBLP:conf/vldb/JarkeLS85,
  author    = {Matthias Jarke and
               Volker Linnemann and
               Joachim W. Schmidt},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {Data Constructors: On the Integration of Rules and Relations},
  booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
               Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
  publisher = {Morgan Kaufmann},
  year      = {1985},
  pages     = {227-240},
  ee        = {db/conf/vldb/JarkeLS85.html},
  crossref  = {DBLP:conf/vldb/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Although the goals and means of rule-based and data-based systems are too different to be fully integrated at the present time, it seems appropriate to investigate a closer integration of language constructs and a better cooperation of execution models for both kinds of approaches.

In this paper we propose a new language construct called constructor that allows the definition of new relations from existing ones by means of recursion. The constructor is semantically defined by the least fixed point of a set expression and blends well both with a strongly typed modular programming language and with a relational calculus query formalism. Moreover, it is shown to provide expressive power at least equivalent to the declarative semantics of PROLOG while avoiding some disadvantages of it, for example, poor modularity and infinite loops. Furthermore, the constructor is set-oriented thus allowing more efficient implementation techniques than those available through proof-theoretic methods typical of a rule-based approach.

Copyright © 1985 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[AhUl 79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[Baye 85]

...

[BrLe 84]

Ronald J. Brachman, Hector J. Levesque: What Makes a Knowledge Base Knowledgeable? A View of Databases from the Knowledge Level. Expert Database Workshop 1984: 69-78 BibTeX

[BrMySc 84]

...

[ChHa 82]

Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 BibTeX

[ClMe 81]

...

[Codd 72]

E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX

[Covi 85]

...

[Deut81]

...

[EmEmDo 84]

...

[Fron 84]

...

[GaMN 84]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX

[Gries 81]

David Gries: The Science of Programming. Springer 1981
BibTeX

[Hehn 84]

...

[HeNa 84]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[IoShWo 84]

...

[Jark 84]

Matthias Jarke: External Semantic Query Simplification: A Graph-Theoretic Approach and its Implementation in Prolog. Expert Database Workshop 1984: 675-692 BibTeX

[JaKo 83]

Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206 BibTeX

[JaVa 84]

...

[Kers 84]

...

[Krie 84]

...

[Kung 84]

Ru-Mei Kung, Eric N. Hanson, Yannis E. Ioannidis, Timos K. Sellis, Leonard D. Shapiro, Michael Stonebraker: Heuristic Search in Data Base Systems. Expert Database Workshop 1984: 537-548 BibTeX

[Lame 84]

Winfried Lamersdorf: Recursive Data Models for Non-Conventional Database Applications. ICDE 1984: 143-150 BibTeX

[LaMuSc 84]

Winfried Lamersdorf, G. Müller, Joachim W. Schmidt: Language Support for Office Modelling. VLDB 1984: 280-288 BibTeX

[LiScJa 85]

...

[MaReSc 84]

...

[MaMAJo 84]

G. Marque-Pucheu, J. Martin-Gallausiaux, Geneviève Jomier: Interfacing Prolog and Relational Data Base Management Systems. ICOD-2 Workshop on New Applications of Data Bases 1983: 225-244 BibTeX

[McSh 81]

...

[MiNi 83]

Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983) BibTeX

[Morg 84]

Matthew Morgenstern: Constraint Equations: Declarative Expression of Constraints With Automatic Enforcement. VLDB 1984: 291-300 BibTeX

[MyBr 85]

...

[Naqv 84]

...

[Reit 78]

Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX

[Schm 77]

Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977) BibTeX

[Schn 78]

Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) BibTeX

[ScLi 85]

Joachim W. Schmidt, Volker Linnemann: Higher Level relational Objects. BNCOD 1985: 1-23 BibTeX

[ScMa 83]

...

[ScWa 84]

Edward Sciore, David Scott Warren: Towards an Integrated Database-Prolog System. Expert Database Workshop 1984: 293-305 BibTeX

[ShTZ 84]

Oded Shmueli, Shalom Tsur, Hana Zfira: Rule Support in Prolog. Expert Database Workshop 1984: 247-269 BibTeX

[Sick76]

...

[Smith 81]

...

[Smith 84]

John Miles Smith: Expert Database Systems: A Database Perspective. Expert Database Workshop 1984: 3-15 BibTeX

[Ston 75]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[Tars 55]

...

[Ullm 82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Ullm 84]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases (Abstract). SIGMOD Conference 1985: 444 BibTeX

[Venk 84]

...

[Wirth 83]

...

[Zani 84]

Carlo Zaniolo: Prolog: A Database Query Language for All Seasons. Expert Database Workshop 1984: 219-232 BibTeX

[Zloof 77]

...

Referenced by

1. Joachim W. Schmidt, Florian Matthes: The Rational behind DBPL. MFDBS 1991: 389-395
2. Kyung-Chang Kim, Won Kim, Alfred G. Dale: Cyclic Query Processing in Object-Oriented Databases. ICDE 1989: 564-571
3. Florian Matthes, Joachim W. Schmidt: The Type System of DBPL. DBPL 1989: 219-225
4. Towards KBMS for Software Development: An Overview of the DAIDA Project. EDBT 1988: 572-577
5. Volker Linnemann: Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach. ICDE 1987: 591-598
6. Ulrich Güntzer, Werner Kießling, Rudolf Bayer: On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. ICDE 1987: 120-129
7. Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355
8. Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176
9. Volker Linnemann: Constructorset's Database Support for Knowledge Based Systems. ICDE 1986: 244-251
10. Kazimierz Subieta, Marek Missala: Semantics of Query Languages for the Entity-Relationship Model. ER 1986: 197-216