Incremental evaluation of Datalog queries | SpringerLink
Skip to main content
Springer Nature Link
Log in

Incremental evaluation of Datalog queries

  • 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:

  • 274 Accesses

Abstract

We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We call this process “incremental query evaluation.”

The main contribution of this paper is an algorithm that constructs, for each regular chain query, a nonrecursive program to compute the difference between the answer after an update and the answer before the update. Using this algorithm the standard transitive closure query can be computed incrementally by a nonrecursive program. We also consider irredundancy and the incremental evaluation of general Datalog queries.

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. F. Afrati and S.S. Cosmadakis. Expressiveness of restricted recursive queries. In Proc. ACM SIGACT Symp. on the Theory of Computing, pages 113–126, 1989.

    Google Scholar 

  2. K. R. Apt, H. A. Blair, and A. Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89–148. Morgan Kaufmann, 1988.

    Google Scholar 

  3. K. R. Apt and J.-M. Pugin. Maintenance of stratified databases viewed as a belief revision system. In Proc. Sixth ACM Symp. on Principles of Database Systems, pages 136–145, 1987.

    Google Scholar 

  4. F. Bancilhon. Naive evaluation of recursively defined relations. In M. L. Brodie and J. Mylopoulos, editors, On Knowledge Base Management Systems: Integrating Artificial Intelligence and Database Technologies. Springer-Verlag, 1985.

    Google Scholar 

  5. F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman. Magic sets and other strange ways to implement logic programs. In Proc. Fifth ACM Symp. on Principles of Database Systems, pages 1–15, 1986.

    Google Scholar 

  6. F. Bry, H. Decker and R. Manthey. A uniform approach to constraint satisfaction and constraint satisfiability in deductive databases. In Proc. First Int. Conf. on Extending Database Technology, pages 488–505, 1988.

    Google Scholar 

  7. A.L. Buchsbaum, P.C. Kanellakis and J.S. Vitter. A data structure for arc insertion and regular path finding. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 1990.

    Google Scholar 

  8. G. Dong. On datalog linearization of chain queries. In J.D. Ullman, editor, Theoretical Studies in Computer Science, pages 181-206. Academic Press, 1991.

    Google Scholar 

  9. G. Dong. Datalog expressiveness of chain queries: Grammar tools and characterizations. In Proc. Eleventh ACM Symp. on Principles of Database Systems, pages 81–90, 1992.

    Google Scholar 

  10. G. G. Hillerbrand, P. C. Kanellakis, H, G. Mairson, and M. Y. Vardi. Tools for Datalog boundedness. In Proc. Tenth ACM Symp. on Principles of Database Systems, pages 1–12, 1991.

    Google Scholar 

  11. T. Ibaraki and N. Katoh. On-line computation of transitive closure of graphs. Information Processing Letters, 16:95–97, 1983.

    Article  Google Scholar 

  12. G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48:273–281, 1986.

    Google Scholar 

  13. V. Küchenhoff. On the efficient computation of the difference between consecutive database states. In C. Delobel, M. Kifer, and Y. Masunaga, editors, Proc. Second Int. Conf. on Deductive Object-Oriented Databases, Lecture Notes in Computer Science 566, pages 478–502. Springer-Verlag, 1991.

    Google Scholar 

  14. J. W. Lloyd and J. C. Shepherdson. Partial evaluation in logic programming. Journal of Logic Programming, 11:217–242, 1991.

    Google Scholar 

  15. J. W. Lloyd, E. A. Sonenberg, and R. W. Topor. Integrity constraint checking in stratified databases. Journal of Logic Programming, 4(4):331–343, 1987.

    Google Scholar 

  16. J-M. Nicolas. Logic for improving integrity checking in relational data bases. Acta Informatica, 18(3):227–253, 1982.

    Article  Google Scholar 

  17. M. H. van Emden and R. A. Kowalski. The semantics of predicate logic as a programming language. Journal of the ACM, 23(4):733–742, 1976.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, The University of Melbourne, 3052, Parkville, Vic., Australia

    Guozhu Dong

  2. School of Computing and Information Technology, Griffith University, 4111, Nathan, Qld, Australia

    Rodney Topor

Authors
  1. Guozhu Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rodney Topor
    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

Dong, G., Topor, R. (1992). Incremental evaluation of Datalog queries. 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_48

Download citation

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

  • 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