Advertisement

Nonmonotonic Reasoning in LDL++

  • Haixun Wang
  • Carlo Zaniolo
Chapter
Part of the The Springer International Series in Engineering and Computer Science book series (SECS, volume 597)

Abstract

Deductive database systems have made major advances on efficient support for nonmonotonic reasoning. A first generation of deductive database systems supported the notion of stratification for programs with negation and set aggregates. Stratification is simple to understand and efficient to implement but it is too restrictive; therefore, a second generation of systems seeks efficient support for more powerful semantics based on notions such as well-founded models and stable models. In this respect, a particularly powerful set of constructs is provided by the recently enhanced LDL++ system that supports (i) monotonie user-defined aggregates, (ii) XY-stratified programs, and (iii) the nondeterministic choice constructs under stable model semantics. This integrated set of primitives supports a terse formulation and efficient implementation for complex computations, such as greedy algorithms and data mining functions, yielding levels of expressive power unmatched by other deductive database systems.

Keywords

Deductive Databases Nonmonotonic Reasoning Stratification Monotonic Aggregation 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Abiteboul, S., Hull, R. and Vianu, V. (1995). Foundations of Databases. Addison-Wesley, Reading, MA, 1995.zbMATHGoogle Scholar
  2. Baudinet, M., Chomicki, J., and Wolper, P. (1994). Temporal Deductive Databases, Chapter 13 of Temporal Databases: Theory, Design, and Implementation, A. Tansel et al. (eds), pp. 294–320, Benjamin/Cummings, 1994.Google Scholar
  3. Brogi, A, Subrahmanian, V. S. and Zaniolo, C. (1997). The Logic of Totally and Partially Ordered Plans: A Deductive Database Approach, Annals of Mathematics and Artificial Intelligence 19(1–2): 27–58 (1997).MathSciNetzbMATHCrossRefGoogle Scholar
  4. Eiter, T. et al. (2000). Declarative Problem-Solving Using the DLV System, In Minker, J., editor, Logic-Based Artificial Intelligence, pages 79–103,  Kluwer Academic Publishers, Norwell, Massachusetts, 02061.CrossRefGoogle Scholar
  5. Bonchi, F. et al. (1999). “Applications of LDL++ to Datamining: A Classification-Based Methodology for Planning Audit Strategies in Fraud Detection”, Proc. Fifth ACM SIGKDD Int. Conference on Knowledge Discovery and Data Mining, KDD’99 175–184, ACM, 1999.Google Scholar
  6. Chimenti, D. et al. (1990). The LDL System Prototype. IEEE Transactions on Knowledge and Data Engineering, 2(1), 76–90 (1990).CrossRefGoogle Scholar
  7. Finkelstein, S. J., et al.(1996) Expressing Recursive Queries in SQL, ISO WG3 report X3H2-96-075, March 1966.Google Scholar
  8. Hellerstein, J. M., Haas, P.J. and Wang, H.J. (1997). “Online Aggregation”. Proc. ACM SIGMOD Int. Conference on Management of Data, 171–182, ACM, 1997.Google Scholar
  9. Ganguly, S., Greco, S. and Zaniolo, C. (1995). “Extrema Predicates in Deductive Databases,” JCSS 51(2): 244–259 (1995)MathSciNetGoogle Scholar
  10. Gelfond, M. and Lifschitz, V. (1988). 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. Giannotti, F. et al. (1981). Non-Determinism in Deductive Databases. DOOD’91, C. Delobel, M. Kifer, Y. Masunaga (Eds.), pp. 129–146, Springer, 1991.Google Scholar
  12. Giannotti, F., et al. (1999). On the Effective Semantics of Nondeterministic, Nonmonotonic, Temporal Logic Databases, Proc. 12th Int. Workshop, Computer Science Logic, pp. 58–72, LNCS Vol. 1584, Springer, 1999.Google Scholar
  13. Giannotti, F., Pedreschi, D. and Zaniolo, C. (2000). “Semantics and Expressive Power of Non-Deterministic Constructs in Deductive Databases,” Journal of Computer and System Sciences, to appear.Google Scholar
  14. Greco, S. and Zaniolo, C. (1998). 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
  15. Kemp, D., Ramamohanarao, K., and Stuckey, P. (1995). ELS Programs and the Efficient Evaluation of Non-Stratified Programs by Transformation to ELS. In Proc. Int. Conf on Deductive and Object-Oriented Databases: DOOD’95, T. W. Ling, A. O. Mendelzon, L. Vieille (Eds.): pp. 91–108, Springer, 1995.Google Scholar
  16. Kemp, D. and Ramamohanarao, K. (1998). Efficient Recursive Aggregation and Negation in Deductive Databases. TKDE 10(5): 727–745 (1998).Google Scholar
  17. Krishnamurthy, R., Naqvi, S. (1988) Non-Deterministic Choice in Datalog. Proc. 3nd Int. Conf. on Data and Knowledge Bases, pp. 416–424, Morgan Kaufmann, Los Altos (1988).Google Scholar
  18. Minker, J. (1996). Logic and Databases: A 20 Year Retrospective. Proc. International Workshop on Logic in Databases (LID’96), D. Pedreschi and C. Zaniolo (eds.), pp. 5–52, Springer-Verlag, 1966.Google Scholar
  19. Przymusinski, T.C. (1998). 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 Kaufman, San Francisco, CA, 1988.Google Scholar
  20. Lausen, G., Ludaescher, B. and May, W. (1998). On Logical Foundations of Active Databases, In Logics for Databases and Information Systems, J. Chomicki and G. Saake (Eds.), pp. 389–422 Kluwer Academic Publishers, pp. 375–398, 1998.Google Scholar
  21. Rao, P., et al. (1997). XSB: A System for Efficiently Computing WFS. Proc. Fourth Int. Conference on Logic Programming and Non-Monotonic Reasoning, LPNMR’97, J. Dix, U. Furbach, A. Nerode (Eds.), pp. 431–441, Springer 1997Google Scholar
  22. Ramakrishnan, R., et al. (1993). Implementation of the CORAL Deductive Database System. Proc. International ACM SIGMOD Conference on Management of Data, pp. 167–176, 1993.Google Scholar
  23. Ramakrishnan, R., and Ullman J.D. (1995). A survey of deductive database systems. LLP, 23(2): 125–149 (1995)MathSciNetGoogle Scholar
  24. Ross, K.A. (1994). Modular Stratification and Magic Sets for Datalog Programs with Negation. Journal of ACM 41(6):1216–1266, 1994.zbMATHCrossRefGoogle Scholar
  25. Ross, K.A. and Sagiv, Y. (1997). “Monotonie Aggregation in Deductive Database”, JCSS, 54(1), 79–97 (1997).MathSciNetzbMATHGoogle Scholar
  26. Shen, W., et al. (1996). Metaqueries for Data Mining, Chapter 15 of Advances in Knowledge Discovery and Data Mining, U. M. Fayyad et al (eds.), pp. 201–217, MIT Press, 1996.Google Scholar
  27. Schlipf, J.S. (1992). A Survey of Complexity and Undecidability Results in Logic Programming, Proc. Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, 1993, pp. 143–164Google Scholar
  28. Vaghani, J., et al. (1994) The Aditi Deductive Database System. The VLDB Journal, 3(2), pp. 245–288 (1994).CrossRefGoogle Scholar
  29. Van Gelder, A., Ross, K.A. and Schlipf, J.S. (1990). The Well-Founded Semantics for General Logic Programs. Journal of ACM 38:620–650, 1991.Google Scholar
  30. Van Gelder, A. (1990). Foundations of Aggregations in Deductive Databases Proc. of Int. Conf. On Deductive and Object-Oriented databases, DOOD’93, S. Ceri, K. Tanaka, S. Tsur (Eds.), pp. 13–34, Springer, 1993.Google Scholar
  31. Tsur, S. (1991). Deductive Databases in Action, Proc. ACM SIGACT- SIGMOD-SIGART Symposium on Principles of Programming Languages, pp. 142–154, 1991.Google Scholar
  32. Zaniolo, C, Arni, N. Ong, K. (1993). Negation and Aggregates in Recursive Rules: the LDL++ Approach. DOOD’93, S. Ceri, K. Tanaka, S. Tsur (Eds.), pp. 204–221, Springer, 1993.Google Scholar
  33. Wang, H. and Zaniolo, C. (2000). User-Defined Aggregates in Object-Relational Database Systems. International Conference on Database Engineering, pp. 111–121, IEEE Press, 2000.Google Scholar
  34. Zaniolo, C. and Wang, H. (1999). Logic-Based User-Defined Aggregates for the Next Generation of Database Systems. In The Logic Programming Paradigm: Current Trends and Future Directions. K.R. Apt, V. Marek, M. Truszczynski, D.S. Warren (eds.), Springer Verlag, pp. 401–424, 1999.Google Scholar
  35. Zaniolo, et al. (1997) Advanced Database Systems, Morgan Kaufmann Publishers, 1997.Google Scholar
  36. Zaniolo, C. (1997). The Nonmonotonic Semantics of Active Rules in Deductive Databases. DOOD 1997, F. Bry, R. Ramakrishnan, K. Ramamohanarao (Eds.) pp. 265–282, Springer, 1997.Google Scholar
  37. Zaniolo, C. et al. (1998) LDL++ Documentation and Web Demo, 1988: http://www.cs.ucla.edu/ldl Google Scholar

Copyright information

© Springer Science+Business Media New York 2000

Authors and Affiliations

  • Haixun Wang
    • 1
  • Carlo Zaniolo
    • 1
  1. 1.Computer Science DepartmentUniversity of California at Los AngelesUSA

Personalised recommendations