Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-24T08:24:53.464Z Has data issue: false hasContentIssue false
  • English
  • Français

Design and implementation of aggregate functions in the DLV system*

Published online by Cambridge University Press:  01 November 2008

WOLFGANG FABER ,
GERALD PFEIFER ,
NICOLA LEONE ,
TINA DELL'ARMI  and
GIUSEPPE IELPA
WOLFGANG FABER
Affiliation:
Department of Mathematics, University of Calabria87036 Rende (CS), Italy (e-mail: faber@mat.unical.it, gerald@mat.unical.it, leone@mat.unical.it, dellarmi@mat.unical.it, ielpa@mat.unical.it)
GERALD PFEIFER
Affiliation:
Department of Mathematics, University of Calabria87036 Rende (CS), Italy (e-mail: faber@mat.unical.it, gerald@mat.unical.it, leone@mat.unical.it, dellarmi@mat.unical.it, ielpa@mat.unical.it)
NICOLA LEONE
Affiliation:
Department of Mathematics, University of Calabria87036 Rende (CS), Italy (e-mail: faber@mat.unical.it, gerald@mat.unical.it, leone@mat.unical.it, dellarmi@mat.unical.it, ielpa@mat.unical.it)
TINA DELL'ARMI
Affiliation:
Department of Mathematics, University of Calabria87036 Rende (CS), Italy (e-mail: faber@mat.unical.it, gerald@mat.unical.it, leone@mat.unical.it, dellarmi@mat.unical.it, ielpa@mat.unical.it)
GIUSEPPE IELPA
Affiliation:
Department of Mathematics, University of Calabria87036 Rende (CS), Italy (e-mail: faber@mat.unical.it, gerald@mat.unical.it, leone@mat.unical.it, dellarmi@mat.unical.it, ielpa@mat.unical.it)
Get access Rights & Permissions [Opens in a new window]

Abstract

Disjunctive logic programming (DLP) is a very expressive formalism. It allows for expressing every property of finite structures that is decidable in the complexity class ΣP2(=NPNP). Despite this high expressiveness, there are some simple properties, often arising in real-world applications, which cannot be encoded in a simple and natural manner. Especially properties that require the use of arithmetic operators (like sum, times, or count) on a set or multiset of elements, which satisfy some conditions, cannot be naturally expressed in classic DLP. To overcome this deficiency, we extend DLP by aggregate functions in a conservative way. In particular, we avoid the introduction of constructs with disputed semantics, by requiring aggregates to be stratified. We formally define the semantics of the extended language (called ), and illustrate how it can be profitably used for representing knowledge. Furthermore, we analyze the computational complexity of , showing that the addition of aggregates does not bring a higher cost in that respect. Finally, we provide an implementation of in DLV—a state-of-the-art DLP system—and report on experiments which confirm the usefulness of the proposed extension also for the efficiency of computation.

Keywords

disjunctive logic programminganswer set programmingaggregatesknowledge representationimplementation
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 8 , Issue 5-6 , November 2008 , pp. 545 - 580
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Apt, K. R., Blair, H. A. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann Publishers, Inc., Washington, DC, 89–148.CrossRefGoogle Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge, UK.CrossRefGoogle Scholar
Ben-Eliyahu, R. and Dechter, R. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence 12, 53–87.Google Scholar
Buccafurri, F., Leone, N. and Rullo, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Transactions on Knowledge and Data Engineering 12,5, 845–860.Google Scholar
Calimeri, F., Faber, W., Leone, N. and Perri, S. 2005. Declarative and computational properties of logic programs with aggregates. In Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05). 406–411.Google Scholar
Chimenti, D., Gamboa, R., Krishnamurthy, R., Naqvi, S. A., Tsur, S. and Zaniolo, C. 1990. The LDL system prototype. IEEE Transactions on Knowledge and Data Engineering 2, 1, 76–90.CrossRefGoogle Scholar
Dell'Armi, T., Faber, W., Ielpa, G., Leone, N. and Pfeifer, G. 2003. Aggregate functions in DLV. In Proceedings ASP03—Answer Set Programming: Advances in Theory and Implementation, M. de Vos and A. Provetti, Eds. Messina, Italy, 274–288. Online at http://CEUR-WS.org/Vol-78/Google Scholar
Dowling, W. F. and Gallier, J. H. 1984. Linear-time algorithms for testing the satisfability of propositional horn formulae. Journal of Logic Programming 3, 267–284.Google Scholar
Eiter, T., Faber, W., Leone, N. and Pfeifer, G. 2000. Declarative problem-solving using the DLV system. In Logic-Based Artificial Intelligence, Minker, J., Ed. Kluwer Academic Publishers, Norwell, MA, USA, 79–103.Google Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: prepositional case. Annals of Mathematics and Artificial Intelligence 15, 3/4, 289–323.CrossRefGoogle Scholar
Eiter, T., Gottlob, G. and Mannila, H. 1997a. Disjunctive datalog. ACM Transactions on Database Systems 22, 3 (Sept.), 364–418.CrossRefGoogle Scholar
Eiter, T., Gottlob, G. and Veith, H. 1997b. Modular logic programming and generalized quantifiers. In Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-97), Dix, J., Furbach, U., and Nerode, A., Eds. Lecture Notes in Computer Science, vol. 1265. Springer, Berlin, Germany, 290–309.Google Scholar
Elkabani, I., Pontelli, E. and Son, T. C. 2005. SmodelsA—a system for computing answer sets of logic programs. In Logic Programming and Nonmonotonic Reasoning — 8th International Conference, LPNMR'05, Diamante, Italy, September 2005, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Lecture Notes in Computer Science, vol. 3662. Springer-Verlag, Berlin, Germany, 427–431.Google Scholar
Faber, W. 2002. Enhancing Efficiency and Expressiveness in Answer Set Programming Systems. Ph.D. thesis, Institut für Informationssysteme, Technische Universität Wien.Google Scholar
Faber, W. 2005. Unfounded sets for disjunctive logic programs with arbitrary aggregates. In Logic Programming and Nonmonotonic Reasoning—8th International Conference, LPNMR'05, Diamante, Italy, September 2005, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Lecture Notes in Computer Science, vol. 3662. Springer-Verlag, Berlin, Germany, 40–52.Google Scholar
Faber, W., Leone, N., Mateis, C. and Pfeifer, G. 1999. Using database optimization techniques for nonmonotonic reasoning. In Proceedings of the 7th International Workshop on Deductive Databases and Logic Programming (DDLP'99), INAP Organizing Committee, Ed. Prolog Association of Japan, 135–139.Google Scholar
Faber, W., Leone, N. and Pfeifer, G. 1999. Pushing goal derivation in DLP computations. In Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99), Gelfond, M., Leone, N., and Pfeifer, G., Eds. Lecture Notes in AI (LNAI), vol. 1730. Springer Verlag, El Paso, TX, 177–191.CrossRefGoogle Scholar
Faber, W., Leone, N. and Pfeifer, G. 2001. Experimenting with heuristics for answer set programming. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI) 2001. Morgan Kaufmann Publishers, Seattle, WA, USA, 635–640.Google Scholar
Faber, W., Leone, N. and Pfeifer, G. 2004. Recursive aggregates in disjunctive logic programs: Semantics and complexity. In Proceedings of the 9th European Conference on Artificial Intelligence (JELIA 2004), Alferes, J. J. and Leite, J., Eds. Lecture Notes in AI (LNAI), vol. 3229. Springer-Verlag, Berlin, Germany, 200–212.Google Scholar
Ferraris, P. 2005. Answer sets for prepositional theories. In Logic Programming and Nonmonotonic Reasoning—8th International Conference, LPNMR'05, Diamante, Italy, September 2005, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Lecture Notes in Computer Science, vol. 3662. Springer-Verlag, Berlin, Germany, 119–131.Google Scholar
Ferraris, P. and Lifschitz, V. 2005. Weight constraints as nested expressions. Theory and Practice of Logic Programming 5, 1/2, 45–74.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. Conflict-driven answer set solving. In Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07). Morgan Kaufmann Publishers, San Francisco, CA, USA, 386–392.Google Scholar
Gebser, M., Liu, L., Namasivayam, G., Neumann, A., Schaub, T. and Truszczyński, M. 2007. The first answer set programming system competition. In Logic Programming and Nonmonotonic Reasoning—9th International Conference, LPNMR'07, C. Baral, G. Brewka, and J. Schlipf, Eds. Lecture Notes in Computer Science, vol. 4483. Springer-Verlag, Tempe, AZ, 3–17.Google Scholar
Gelfond, M. 2002. Representing knowledge in A-prolog. In Computational Logic. Logic Programming and Beyond, Kakas, A. C. and Sadri, F., Eds. Lecture Notes in Computer Science, vol. 2408. Springer, Berlin, Germany, 413–451.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.Google Scholar
Gottlob, G., Leone, N. and Veith, H. 1999. Succinctness as a source of expression complexity. Annals of Pure and Applied Logic 97, 1–3, 231–260.Google Scholar
Hella, L., Libkin, L., Nurmonen, J. and Wong, L. 2001. Logics with aggregate operators. Journal of the ACM 48, 4, 880–907.Google Scholar
Kemp, D. B. and Ramamohanarao, K. 1998. Efficient recursive aggregation and negation in deductive databases. IEEE Transactions on Knowledge and Data Engineering 10, 727–745.Google Scholar
Leone, N., Perri, S. and Scarcello, F. 2001. Improving ASP instantiators by join-ordering methods. In Logic Programming and Nonmonotonic Reasoning—6th International Conference, LPNMR'01, Vienna, Austria, Eiter, T., Faber, W., and Truszczyński, M., Eds. Lecture Notes in AI (LNAI), vol. 2173. Springer-Verlag, Berlin, Germany, 280–294.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3 (July), 499–562.CrossRefGoogle Scholar
Leone, N., Rullo, P. and Scarcello, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics and computation. Information and Computation 135, 2 (June), 69–112.Google Scholar
Lierler, Y. 2005. Cmodels for tight disjunctive logic programs. In W(C)LP 19th Workshop on (Constraint) Logic Programming, Ulm, Germany. Ulmer Informatik-Berichte. Universität Ulm, Germany, 163–166.Google Scholar
Liu, L. and Truszczyński, M. 2005. Properties of programs with monotone and convex constraints. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05), Veloso, M. M. and Kambhampati, S., Eds. The MIT Press, Cambridge, MA, USA, 701–706.Google Scholar
Marek, V. W., Niemelä, I. and Truszczyński, M. 2004. Logic programming with monotone cardinality atom. In Proceedings of the 7th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR-7), Lifschitz, V. and Niemelä, I., Eds. Lecture Notes in AI(LNAI), vol. 2923. Springer, Berlin, Germany, 154–166.Google Scholar
Marek, V. W. and Remmel, J. B. 2002. On logic programs with cardinality constraints. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR'2002), Ben-ferhat, S. and Giunchiglia, E., Eds. Toulouse, France, 219–228.Google Scholar
Marek, V. W. and Truszczyński, M. 1991. Autoepistemic logic. Journal of the ACM 38, 3, 588–619.Google Scholar
Minker, J. 1982. On indefinite data bases and the closed world assumption. In Proceedings 6th Conference on Automated Deduction (CADE '82), Loveland, D. W., Ed. Lecture Notes in Computer Science, vol. 138. Springer, New York, 292–308.Google Scholar
Minoux, M. 1988. LTUR: A simplified linear-time unit resolution algorithm for horn formulae and computer implementation. Information Processing Letters 29, 1–12.CrossRefGoogle Scholar
Niemelä, I., Simons, P. and Soininen, T. 1999. Stable model semantics of weight constraint rules. In Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99), Gelfond, M., Leone, N., and Pfeifer, G., Eds. Lecture Notes in AI (LNAI), vol. 1730. Springer Verlag, El Paso, TX, 107–116.Google Scholar
Pelov, N. 2004. Semantics of Logic Programs with Aggregates. Ph.D. thesis, Katholieke Univer-siteit Leuven, Leuven, Belgium.Google Scholar
Pelov, N., Denecker, M. and Bruynooghe, M. 2004. Partial stable models for logic programs with aggregates. In Proceedings of the 7th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR-7). Lecture Notes in AI (LNAI), vol. 2923. Springer, Berlin, Germany, 207–219.Google Scholar
Przymusinski, T. C. 1988. On the declarative semantics of deductive databases and logic programs. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann Publishers, San Francisco, CA, USA, 193–216.Google Scholar
Ross, K. A. and Sagiv, Y. 1997. Monotonic aggregation in deductive databases. Journal of Computer and System Sciences 54, 1 (February), 79–97.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 181–234.CrossRefGoogle Scholar
Son, T. C. and Pontelli, E. 2007. A constructive semantic characterization of aggregates in ASP. Theory and Practice of Logic Programming 7, 355–375.Google Scholar
Son, T. C., Pontelli, E. and Elkabani, I. 2005. On logic programming with aggregates. Technical Report NMSU-CS-2005-006, New Mexico State University.Google Scholar
Syrjänen, T. 2002. Lparse 1.0 User's Manual. http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz.Google Scholar
Ullman, J. D. 1989. Principles of Database and Knowledge Base Systems. Computer Science Press. New York, NY, USA.Google Scholar