ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Incremental Evaluation of Rules and its Relationship to Parallelism.

Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini: Incremental Evaluation of Rules and its Relationship to Parallelism. SIGMOD Conference 1991: 78-87
@inproceedings{DBLP:conf/sigmod/WolfsonDSY91,
  author    = {Ouri Wolfson and
               Hasanat M. Dewan and
               Salvatore J. Stolfo and
               Yechiam Yemini},
  editor    = {James Clifford and
               Roger King},
  title     = {Incremental Evaluation of Rules and its Relationship to Parallelism},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {78-87},
  ee        = {http://doi.acm.org/10.1145/115790.115799, db/conf/sigmod/WolfsonDSY91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Rule interpreters usually start with an initial database and perform the inference procedure in cycles, ending with a final database. In a real time environment it is possible to receive updates to the initial database after the inference procedure has started or even after it has ended. We present an algorithm for incremental maintenance of the deductive database in the presence of such updates. Interestingly, the same algorithm is useful for parallel and distributed rule processing in the following sense. When the processors evaluating a program operate asynchronously, then they may have different views of the database. The incremental maintenance procedure we present can be used to synchronize these views.

Copyright © 1991 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 BibTeX , SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 993 KB]

References

[1]
David Maier, David Scott Warren: Computing with Logic: Logic Programming with Prolog. Benjamin/Cummings 1988, ISBN 0-8053-6681-4
BibTeX
[2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[3]
Serge Abiteboul, Eric Simon: Fundamental Properties of Deterministic and Nondeterministic Extensions of Datalog. Theor. Comput. Sci. 78(1): 137-158(1991) BibTeX
[4]
...
[5]
...
[6]
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142 BibTeX
[7]
...
[8]
...
[9]
Raymond Reiter, Johan de Kleer: Foundations of Assumption-based Truth Maintenance Systems: Preliminary Report. AAAI 1987: 183-189 BibTeX
[10]
...
[11]
Eric N. Hanson, Moez Chaabouni, Chang-Ho Kim, Yu-Wang Wang: A Predicate Matching Algorithm for Database Rule Systems. SIGMOD Conference 1990: 271-280 BibTeX
[12]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[13]
Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152 BibTeX
[14]
...
[15]
Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy Is Not Enough in Knowledge Bases. J. Comput. Syst. Sci. 47(1): 2-44(1993) BibTeX
[16]
Bruce G. Lindsay, Laura M. Haas, C. Mohan, Hamid Pirahesh, Paul F. Wilms: A Snapshot Differential Refresh Algorithm. SIGMOD Conference 1986: 53-60 BibTeX
[17]
...
[18]
Nissim Francez: Distributed Termination. ACM Trans. Program. Lang. Syst. 2(1): 42-55(1980) BibTeX
[19]
Krzysztof R. Apt, Jean-Marc Pugin: Maintenance of Stratified Databases Viewed as a Belief Revision System. PODS 1987: 136-145 BibTeX
[20]
Ouri Wolfson, Abraham Silberschatz: Decomposability and its Role in Parallel Logic Program Evaluation. J. Log. Program. 11(3&4): 345-358(1991) BibTeX
[21]
Ouri Wolfson: Parallel Evaluation of Datalog Programs by Load Sharing. J. Log. Program. 12(3&4): 369-393(1992) BibTeX
[22]
Ouri Wolfson, Aya Ozeri: Parallel and Distributed Processing of Rules by Data Reduction. IEEE Trans. Knowl. Data Eng. 5(3): 523-530(1993) BibTeX
[23]
Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336 BibTeX
[24]
Ouri Wolfson: Sharing the Load of Logic-Program Evaluation. IEEE Data Eng. Bull. 12(1): 58-64(1989) BibTeX
[25]
...
[26]
Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346 BibTeX
[27]
Maurice A. W. Houtsma, Filippo Cacace, Stefano Ceri: Parallel Hierarchical Evaluation of Tranitive Closure Queries. PDIS 1991: 130-137 BibTeX
[28]
Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35 BibTeX

Referenced by

  1. Guozhu Dong, Jianwen Su: Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44-51(2000)
  2. Lars Bækgaard, Leo Mark: Incremental Computation of Set Difference Views. IEEE Trans. Knowl. Data Eng. 9(2): 251-261(1997)
  3. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  4. Lars Bækgaard, Leo Mark: Incremental Computation of Time-Varying Query Expressions. IEEE Trans. Knowl. Data Eng. 7(4): 583-590(1995)
  5. Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995)
  6. Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150
  7. Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
  8. Thomas A. Mück: The DiNG - A Parallel Multiattribute File System for Deductive Database Machines. DASFAA 1993: 115-122
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:05 2009