Skip to main content
SpringerLink
Log in

Key Constraints and Monotonic Aggregates in Deductive Databases

  • Chapter
  • First Online:
Computational Logic: Logic Programming and Beyond

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2408))

Abstract

We extend the fixpoint and model-theoretic semantics of logic programs to include unique key constraints in derived relations. This extension increases the expressive power of Datalog programs, while preserving their declarative semantics and efficient implementation. The greater expressive power yields a simple characterization for the notion of set aggregates, including the identification of aggregates that are monotonic with respect to set containment and can thus be used in recursive logic programs. These new constructs are critical in many applications, and produce simple logic-based formulations for complex algorithms that were previously believed to be beyond the realm of declarative logic.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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, R. Hull, and V. Vianu: Foundations of Databases. Addison-Wesley, 1995.

    Google Scholar 

  2. N. Bidoit and C. Froidevaux: General logical Databases and Programs: Default Logic Semantics and Stratification. Information and Computation, 91, pp. 15–54, 1991.

    Article  MATH  MathSciNet  Google Scholar 

  3. W. Chen, D. S. Warren: Tabled Evaluation With Delaying for General Logic Programs. JACM, 43(1): 20–74 (1996).

    Article  MATH  MathSciNet  Google Scholar 

  4. D. Chimenti, R. Gamboa, R. Krishnamurthy, S. Naqvi, S. Tsur and C. Zaniolo: The LDL System Prototype. IEEE Transactions on Knowledge and Data Engineering, 2(1), pp. 76–90, 1990.

    Article  Google Scholar 

  5. S. Ceri, G. Gottlob and L. Tanca: Logic Programming and Databases. Springer, 1990.

    Google Scholar 

  6. S. W. Dietrich: Shortest Path by Approximation in Logic Programs. ACM Letters on Programming Languages and Systems, 1(2), pp. 119–137, 1992.

    Article  Google Scholar 

  7. S. J. Finkelstein, N. Mattos, I.S. Mumick, and H. Pirahesh: Expressing Recursive Queries in SQL, ISO WG3 report X3H2-96-075, March 1996.

    Google Scholar 

  8. J. M. Hellerstein, P. J. Haas, H. J. Wang.: Online Aggregation. SIGMOD 1997: Proc. ACM SIGMOD Int. Conference on Management of Data, pp. 171–182, ACM, 1997.

    Google Scholar 

  9. S. Ganguly, S. Greco, and C. Zaniolo: Extrema Predicates in Deductive Databases. JCSS 51(2), pp. 244–259, 1995.

    MATH  MathSciNet  Google Scholar 

  10. M. Gelfond and V. Lifschitz: The Stable Model Semantics for Logic Programming. Proc. Joint International Conference and Symposium on Logic Programming, R. A. Kowalski and K. A. Bowen (eds.), pp. 1070–1080, MIT Press, 1988.

    Google Scholar 

  11. F. Giannotti, D. Pedreschi, D. Saccà, C. Zaniolo: Non-Determinism in Deductive Databases. In DOOD’91, C. Delobel, M. Kifer, Y. Masunaga (eds.), pp. 129–146, Springer, 1991.

    Google Scholar 

  12. F. Giannotti, G. Manco, M. Nanni, D. Pedreschi: On the Effective Semantics of Nondeterministic, Nonmonotonic, Temporal Logic Databases. Proceedings of 12th Int. Workshop, Computer Science Logic, pp. 58–72, LNCS Vol. 1584, Springer, 1999.

    Google Scholar 

  13. F. Giannotti, D. Pedreschi, and C. Zaniolo: Semantics and Expressive Power of Non-Deterministic Constructs in Deductive Databases. JCSS 62, pp. 15–42, 2001.

    MathSciNet  Google Scholar 

  14. Sergio Greco, Domenico Saccà: NP Optimization Problems in Datalog. ILPS 1997: Proc. Int. Logic Programming Symposium, pp. 181–195, MIT Press, 1997.

    Google Scholar 

  15. S. Greco and C. Zaniolo: Greedy Algorithms in Datalog with Choice and Negation, Proc. 1998 Joint Int. Conference & Symposium on Logic Programming, JCSLP’98, pp. 294–309, MIT Press, 1998.

    Google Scholar 

  16. R. Krishnamurthy, S. Naqvi: Non-Deterministic Choice in Datalog. In Proc. 3rd Int. Conf. on Data and Knowledge Bases, pp. 416–424, Morgan Kaufmann, 1988.

    Google Scholar 

  17. V. W. Marek and M. Truszczynski: Nonmonotonic Logic. Springer-Verlag, New York, 1995.

    MATH  Google Scholar 

  18. J. Minker: Logic and Databases: A 20 Year Retrospective. In D. Pedreschi and C. Zaniolo (eds.), Proceedings International Workshop on Logic in Databases (LID’96), Springer-Verlag, pp. 5–52, 1996.

    Google Scholar 

  19. I. Niemelä, P. Simons and T. Syrjanen: Smodels: A System for Answer Set Programming Proceedings of the 8th International Workshop on Non-Monotonic Reasoning, April 9–11, 2000, Breckenridge, Colorado, 4 pages. (Also see: http://www.tcs.hut.fi/Software/smodels/)

  20. I. Niemelta and P. Simons: Extending the Smodels System with Cardinality and Weight Constraints. In Jack Minker (ed.): Logic-Based Artificial Intelligence, pp. 491–521. Kluwer Academic Publishers, 2001.

    Google Scholar 

  21. M.A. Orgun and W.W. Wadge, Towards an Unified Theory of Intensional Logic Programming. The Journal of Logic and Computation, 4(6), pp. 877–903, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  22. T. C. Przymusinski: On the Declarative and Procedural Semantics of Stratified Deductive Databases: In J. Minker (ed.), Foundations of Deductive Databases and Logic Programming, pp. 193–216, Morgan Kaufmann, 1988.

    Google Scholar 

  23. R. Ramakrishnan, D. Srivastava, S. Sudanshan, and P. Seshadri: Implementation of the CORAL Deductive Database System. SIGMOD’93: Proc. Int. ACM SIGMOD Conference on Management of Data, pp. 167–176, ACM, 1993.

    Google Scholar 

  24. K. A. Ross and Yehoshua Sagiv: Monotonic Aggregation in Deductive Database, JCSS 54(1), pp. 79–97, 1997.

    MATH  MathSciNet  Google Scholar 

  25. D. Saccà and C. Zaniolo: Deterministic and Non-deterministic Stable Models, Journal of Logic and Computation, 7(5), pp. 555–579, 1997.

    Article  MATH  MathSciNet  Google Scholar 

  26. J. S. Schlipf: Complexity and Undecidability Results in Logic Programming, Annals of Mathematics and Artificial Intelligence, 15, pp. 257–288, 1995.

    Article  MATH  MathSciNet  Google Scholar 

  27. S. Sudarshan and R. Ramakrishnan: Aggregation and relevance in deductive databases. VLDB’91: Proceedings of 17th Conference on Very Large Data Bases, pp. 501–511, Morgan Kaufmann, 1991.

    Google Scholar 

  28. J. D. Ullman: Principles of Data and Knowledge-Based Systems, Computer Science Press, New York, 1988.

    Google Scholar 

  29. M.H. Van Emden and R. Kowalski: The Semantics of Predicate Logic as a Programming Language. JACM 23(4), pp. 733–742, 1976.

    Article  MATH  Google Scholar 

  30. A. Van Gelder, K. A. Ross, and J. S. Schlipf: The Well-Founded Semantics for General Logic Programs. JACM 38, pp. 620–650, 1991.

    Article  MATH  Google Scholar 

  31. A. Van Gelder: Foundations of Aggregations in Deductive Databases. In DOOD’ 93, S. Ceri, K. Tanaka, S. Tsur (Eds.), pp. 13–34, Springer, 1993.

    Google Scholar 

  32. H. Wang and C. Zaniolo: User-Defined Aggregates in Object-Relational Database Systems. ICDE 2000: International Conference on Database Engineering. pp. 111–121, IEEE Press, 2000.

    Google Scholar 

  33. H. Wang and C. Zaniolo: Using SQL to Build New Aggregates and Extenders for Object-Relational Systems. VLDB 2000: Proceedings of 26th Conference on Very Large Data Bases, pp. 166–175, Morgan Kaufmann, 2000.

    Google Scholar 

  34. C. Zaniolo and H. Wang: Logic-Based User-Defined Aggregates for the Next Generation of Database Systems. In K.R. Apt, V. Marek, M. Truszczynski, D.S. Warren (eds.): The Logic Programming Paradigm: Current Trends and Future Directions. Springer Verlag, pp. 121–140, 1999.

    Google Scholar 

  35. C. Zaniolo, S. Ceri, C. Faloutzos, R. Snodgrass, V.S. Subrahmanian, and R. Zicari: Advanced Database Systems, Morgan Kaufmann, 1997.

    Google Scholar 

  36. C. Zaniolo: The Nonmonotonic Semantics of Active Rules in Deductive Databases. In DOOD 1997, F. Bry, R. Ramakrishnan, K. Ramamohanarao (eds.), pp. 265–282, Springer, 1997.

    Google Scholar 

  37. C. Zaniolo et al.: \( \mathcal{L}\mathcal{D}\mathcal{L} + + \) Documentation and Web Demo, 1988: http://www.cs.ucla.edu/ldl

  38. C. Zaniolo: Key Constraints and Monotonic Aggregates in Deductive Databases. UCLA technical report, June 2001.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of California at Los Angeles, Los Angeles, CA, 90095

    Carlo Zaniolo

Authors
  1. Carlo Zaniolo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Cyprus, 75 Kallipoleos St., 1678, Nicosia, Cyprus

    Antonis C. Kakas

  2. Department of Computing, Imperial College of Science, Technology and Medicine, 180 Queen’s Gate, London, SW7 2BZ, UK

    Fariba Sadri

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Zaniolo, C. (2002). Key Constraints and Monotonic Aggregates in Deductive Databases. In: Kakas, A.C., Sadri, F. (eds) Computational Logic: Logic Programming and Beyond. Lecture Notes in Computer Science(), vol 2408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45632-5_5

Download citation

  • DOI: https://doi.org/10.1007/3-540-45632-5_5

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-43960-8

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation