Explicit Control of Logic Programs Through Rule Algebra.

Tomasz Imielinski, Shamim A. Naqvi: Explicit Control of Logic Programs Through Rule Algebra. PODS 1988: 103-116
  author    = {Tomasz Imielinski and
               Shamim A. Naqvi},
  title     = {Explicit Control of Logic Programs Through Rule Algebra},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {103-116},
  ee        = {, db/conf/pods/ImielinskiN88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP,}


In this paper we argue with a basic premise in logic programming resarch that the meaning of a program can be inferred from its syntax alone. We show that users may have a variety of intended models for programs and that a single program may give different intended models under different assumptions of semantics. Our conclusion is that it is impossible to infer the intended model from the syntax of the program and no single semantics will capture all the intended models. We propose as a solution an explicit specification of control. Towards this purpose we define a rule algebra. The user formulates a program as an algebraic specification that directs the execution towards the intended model. The interesting question at that point is how to efficiently implement such programs. We show a natural and easy transformation such that it takes as input an algebraic specification and produces as output a program belonging to a subclass of locally stratified programs. Moreover, there is a homomorphic correspondence between the algebraic expression and their translations.

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library


Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 BibTeX
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
Richard A. O'Keefe: Towards an Algebra for Constructing Logic Programs. SLP 1985: 152-160 BibTeX
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX

Referenced by

  1. Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language. ACM Trans. Database Syst. 21(3): 370-426(1996)
  2. H. V. Jagadish, Alberto O. Mendelzon, Inderpal Singh Mumick: Managing Rule Conflicts in an Active Database. PODS 1996: 192-201
  3. Philippe Picouet, Victor Vianu: Semantics and Expressiveness Issues in Active Databases. PODS 1995: 126-138
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  5. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. IEEE Trans. Knowl. Data Eng. 6(4): 501-517(1994)
  6. Rafiul Ahad, Bing Yao: RQL: A Recursive Query Language. IEEE Trans. Knowl. Data Eng. 5(3): 451-461(1993)
  7. Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs, Jaime Castillo, Martha Escobar-Molano, Shih-Hui Lu, Junhui Luo, Chiu Tsang, Gang Zhou: On Implementing a Language for Specifying Active Database Execution Models. VLDB 1993: 441-454
  8. Gösta Grahne, Alberto O. Mendelzon, Peter Z. Revesz: Knowledgebase Transformations. PODS 1992: 246-260
  9. Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187
  10. Filippo Cacace, Stefano Ceri, Letizia Tanca: Consistency and Non-determinism in a Database Programming Language. MFDBS 1991: 325-341
  11. Filippo Cacace, Stefano Ceri, Stefano Crespi-Reghizzi, Letizia Tanca, Roberto Zicari: Integrating Object-Oriented Data Modeling with a Rule-Based Programming Paradigm. SIGMOD Conference 1990: 225-236
  12. Shamim A. Naqvi: Stratification as a Design Principle in Logical Query Langugages. DBPL 1989: 342-356
  13. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  14. Shamim A. Naqvi, Ravi Krishnamurthy: Database Updates in Logic Programming. PODS 1988: 251-262
  15. Serge Abiteboul: Updates, A New Frontier. ICDT 1988: 1-18
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:33:53 2009