Optimizing incremental computation of datalog programs with non-deterministic semantics | SpringerLink
Skip to main content
Springer Nature Link
Log in

Optimizing incremental computation of datalog programs with non-deterministic semantics

  • Conference paper
  • First Online:
Database Theory — ICDT '92 (ICDT 1992)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 646))

Included in the following conference series:

Abstract

We address the problem of efficient evaluation of non-deterministic logic programs in a database context using incremental evaluation algorithms. We consider a representative non-deterministic Datalog extension which gives a formal basis to various production rule languages. We point out a clear space-time tradeoff in the choice made by some algorithms to materialize and incrementally maintain some data in order to compute the meaning of a rule program. We advocate that the data maintained by an incremental evaluation algorithm should be chosen according to some particular properties of a rule program. We identify such properties and provide means to determine them statically based on a syntactic analysis of the bodies and heads of rules. We show that using these properties, one can improve the performance of the two best known incremental evaluation algorithms TREAT and RETE.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Abiteboul and E. Simon. Fundamental properties of deterministic and non deterministic extensions of Datalog, Theoretical Computer Science, 78, (1991), pp. 137–158.

    Google Scholar 

  2. S. Abiteboul, E. Simon, and V. Vianu. Non-Deterministic Languages to Express Deteiministic Transformations. In Proc. of 9-th ACM Symposium on Principles of Database Systems, Nashville, April 1990.

    Google Scholar 

  3. S. Abiteboul and A. van Gelder. Optimizing Active Databases Using the Split Technique. In Proc. Int. Conf. on Database Theory, Berlin, Oct. 1992.

    Google Scholar 

  4. S. Abiteboul and V. Vianu. Fixpoint extensions of first order logic and datalog like languages. In Proc. of IEEE Int. Conf. on Logic in Computer Sciences, Asilomar, Ca, USA.

    Google Scholar 

  5. Jose A. Blakeley, Neil Coburn, and Per-Ake Larson. Updating derived relations: Detecting irrelevant and autonomously computable updates. ACM Trans. on Database Systems, 14(3):369–400, 1989.

    Google Scholar 

  6. L. Brownston, R. Farrel, E. Kant, and N. Martin. Programming Expert Systems in OPSS: An Introduction to rule Based Programming. Addison-Wesley, 1985.

    Google Scholar 

  7. J. Earley. High level iterators and a method for automatically designing data structures representation. J. of Computer Languages, 1, 1976.

    Google Scholar 

  8. F. Fabret, M. Régnier and E. Simon. Optimising Incremental Computation of Datalog Programs with Non-deterministic Semantics. INRIA Research Report, June 1992.

    Google Scholar 

  9. A. Fong. Inductively computable constructs in very high level languages. In Proc. of 6-th ACM Symposium on Principles of Programming Languages, San Antonio, 1976.

    Google Scholar 

  10. C. Fotgy. Rete, a fast algorithm for the many patterns many objects match problem. Artificial Intelligence, 19:17–37, 1982.

    Article  Google Scholar 

  11. A. Fong and J. Ullman. Induction variables in very high level languages. In Proc. of 3-rd ACM Symposium on Principles of Programming Languages, Atlanta, 1976.

    Google Scholar 

  12. E.N. Hanson Rule Condition Testing and Action Execution in Ariel, in Proc. of the 1992 ACM SIGMOD Int. Conf., San-Diego, June 1992.

    Google Scholar 

  13. D.P. Miranker. Treat: A better match algorithm for AI production systems. In Proc. of the 1987 National Conference on Artificial Intelligence. Seattle, Washington, 1987.

    Google Scholar 

  14. R. Paige and S. Koenig. Finite differencing of computable expressions. ACM Transactions on Programming Languages and Systems, 4(3), 1982.

    Google Scholar 

  15. T. Sellis, C. Lin, and L. Raschid. Implementing large production systems in a DBMS environment: Concepts and algorithms. In Proc. 1988 ACM SIGMOD Int. Conf., Chicago, May 1988.

    Google Scholar 

  16. J. Ullman. Principles of Database and Knowledge Systems, volume 1. Computer Science Press, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA, 78153, Le Chesnay, France

    Françoise Fabret, Mireille Régnier & Eric Simon

Authors
  1. Françoise Fabret
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mireille Régnier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eric Simon
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Joachim Biskup Richard Hull

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fabret, F., Régnier, M., Simon, E. (1992). Optimizing incremental computation of datalog programs with non-deterministic semantics. In: Biskup, J., Hull, R. (eds) Database Theory — ICDT '92. ICDT 1992. Lecture Notes in Computer Science, vol 646. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56039-4_39

Download citation

  • DOI: https://doi.org/10.1007/3-540-56039-4_39

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56039-5

  • Online ISBN: 978-3-540-47360-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation