Enhancing DLV instantiator by backjumping techniques. (English) Zbl 1138.68019
Summary: Disjunctive Logic Programming (DLP) is a powerful formalism for knowledge representation and reasoning. The high expressiveness of DLP language, together with the recent availability of some efficient DLP system, has favoured the application of DLP in emerging areas like Knowledge Management and Information Integration. These applications have often to deal with huge input data, and have evidenced the need to improve the efficiency of DLP instantiators. Program instantiation is the first phase of a DLP computation; in this phase, variables are replaced by constants to generate a ground program which is then evaluated by propositional algorithms in the second phase of the computation. The instantiation process may be computationally expensive, and in fact its efficiency has been recognized to be a key issue for solving real-world problems by using disjunctive logic programming. Given a program \(P\), a good instantiation for \(P\) is a ground program \(P '\) having precisely the same answer sets as \(P\) and such that: \((1) P'\) can be computed efficiently from \(P\), and \((2) P'\) does not contain “useless” rules, (\(P'\) is as small as possible) and can thus be evaluated efficiently. In this paper, we present a structure-based backjumping algorithm for the instantiation of disjunctive logic programs, that meets the above requirements.
In particular, given a rule \(r\) to be grounded, our algorithm exploits both the semantical and the structural information about \(r\) for computing efficiently the ground instances of \(r\), avoiding the generation of “useless” rules. That is, from each general rule \(r\), we compute only a relevant subset of its ground instances, avoiding the generation of “useless” instances, while fully preserving the semantic of the program. We have implemented this algorithm in DLV – the state-of-the-art implementation of DLP – and we have carried out an experimentation activity on an ample collection of benchmark problems. The experimental results are very positive: the new technique improves sensibly the efficiency of the DLV system on many program classes.
In particular, given a rule \(r\) to be grounded, our algorithm exploits both the semantical and the structural information about \(r\) for computing efficiently the ground instances of \(r\), avoiding the generation of “useless” rules. That is, from each general rule \(r\), we compute only a relevant subset of its ground instances, avoiding the generation of “useless” instances, while fully preserving the semantic of the program. We have implemented this algorithm in DLV – the state-of-the-art implementation of DLP – and we have carried out an experimentation activity on an ample collection of benchmark problems. The experimental results are very positive: the new technique improves sensibly the efficiency of the DLV system on many program classes.
Keywords:
Artificial intelligence; Logic programming; Nonmonotonic reasoning; Disjunctive logic programming; Answer set programming; Deductive databases; Stable model semanticsReferences:
| [1] | Anger, C., Konczak, K., Linke, T.: NoMoRe: A system for non-monotonic reasoning. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’01), Vienna, Austria. Lecture Notes in Computer Science, vol. 2173, pp. 406–410. Springer Verlag, Vienna, Austria (2001) · Zbl 1007.68718 |
| [2] | Anger, C., Gebser, M., Linke, T., Neumann, A., Schaub, T.: The nomore++ approach to answer set solving. In: Sutcliffe, G., Voronkov, A. (eds.) Proceedings of the 12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR ’05). Lecture Notes in Computer Science, vol 3835, pp. 95–109. Springer Verlag (2005) · Zbl 1143.68584 |
| [3] | Apt, K.R., Blair, H.A., Walker, A.: Towards a theory of declarative knowledge. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufmann Publishers, Inc., Washington, DC (1988) |
| [4] | Arieli, O., Denecker, M., Van Nuffelen, B., Bruynooghe, M.: Database repair by signed formulae. In: Seipel, D., Turull Torres, J.M. (eds.) Foundations of Information and Knowledge Systems, Third International Symposium (FoIKS 2004). Lecture Notes in Computer Science, vol. 2942, pp. 14–30. Springer (2004) · Zbl 1202.68132 |
| [5] | Babovich, Y.: Cmodels homepage. http://www.cs.utexas.edu/users/tag/cmodels.html (since 2002) |
| [6] | Bruynooghe, M., Pereira, L.: Deduction revision by intelligent backtracking. In: Horwood, E. (ed.) Implementations of Prolog, pp. 194–215 (1984) |
| [7] | Cadoli, M., Eiter, T., Gottlob, G.: Default logic as a query language. IEEE Trans. Knowl. Data Eng. 9(3), 448–463 (1997) · doi:10.1109/69.599933 |
| [8] | Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pp. 77–90 (1977) |
| [9] | Chen, X., van Beek, P.: Conflict-directed backjumping revisited. J. Artif. Intell. Res. 14, 53–81 (2001) · Zbl 0970.68192 |
| [10] | Dechter, R.: Enhancement schemes fo constraint processing: backjumping, learning and cutset decomposition. Artif. Intell. 41(3), 273–312 (1990) · doi:10.1016/0004-3702(90)90046-3 |
| [11] | Dix, J., Eiter, T., Fink, M., Polleres, A., Zhang, Y.: Monitoring agents using declarative planning. In: Günter, A., Kruse, R., Neumann, B. (eds.) Proceedings of the 26th German Conference on Artificial Intelligence (KI ’03). Lecture Notes in Computer Science, no. 2821, pp. 646–660. Springer (2003) · Zbl 1274.68578 |
| [12] | Downey, R., Fellows, M.: Parameterized Complexity. Springer (1999) |
| [13] | Eiter, T., Leone, N., Mateis, C., Pfeifer, G., Scarcello, F.: A deductive system for nonmonotonic reasoning. In: Dix, J., Furbach, U., Nerode, A. (eds.) Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’97). Lecture Notes in AI (LNAI), no. 1265, pp. 363–374. Springer, Dagstuhl, Germany (1997) |
| [14] | Faber, W., Leone, N., Mateis, C., Pfeifer, G.: Using database optimization techniques for nonmonotonic reasoning. In: INAP Organizing Committee (ed.) Proceedings of the 7th International Workshop on Deductive Databases and Logic Programming (DDLP’99). Prolog Association of Japan, pp. 135–139 (1999) |
| [15] | Faber, W., Leone, N., Pfeifer, G.: Recursive aggregates in disjunctive logic programs: semantics and complexity. In: Alferes, J.J., Leite, J. (eds.) Proceedings of the 9th European Conference on Artificial Intelligence (JELIA 2004). Lecture Notes in AI (LNAI), no. 3229, pp. 200–212. Springer Verlag (2004) · Zbl 1111.68380 |
| [16] | Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set solving. In: Veloso, M.M. (ed.) Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI ’07), pp. 386–392. Morgan Kaufmann Publishers (2007) · Zbl 1149.68332 |
| [17] | Gebser, M., Schaub, T., Thiele, S.: Gringo : a new grounder for answer set programming. In: Baral, C., Brewka, G., Schlipf, J.S. (eds.) Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR ’07), vol. 4483, pp. 266–271. Tempe, AZ, USA (2007) |
| [18] | Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3/4), 365–385 (1991) · Zbl 0735.68012 · doi:10.1007/BF03037169 |
| [19] | Janhunen, T., Niemelä, I., Seipel, D., Simons, P., You, J.H.: Unfolding partiality and disjunctions in stable model semantics. ACM Trans. Comput. Log. 7(1), 1–37 (2006) · doi:10.1145/1119439.1119440 |
| [20] | Knuth, D.E.: The Stanford GraphBase : A Platform for Combinatorial Computing. ACM Press, New York (1994) · Zbl 0824.68040 |
| [21] | Leone, N., Perri, S., Scarcello, F.: Improving ASP instantiators by join-ordering methods. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR ’01). Lecture Notes in AI (LNAI), no. 2173, pp. 280–294. Springer Verlag, Vienna, Austria (2001) · Zbl 1007.68712 |
| [22] | Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S., Scarcello, F.: The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log. 7(3), 499–562 (2006) · doi:10.1145/1149114.1149117 |
| [23] | Lierler, Y.: Cmodels–SAT-based disjunctive answer set solver. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) Proceedings of 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR ’05). Lecture Notes in Computer Science, vol. 3662, pp. 447–451. Springer, Diamante, Italy (2005) |
| [24] | Lierler, Y., Maratea, M.: Cmodels-2: SAT-based Answer Set Solver Enhanced to Non-tight Programs. In: Lifschitz, V., Niemelä, I. (eds.) Proceedings of the 7th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR ’07). Lecture Notes in Computer Science, pp. 346–350. Springer (2004) · Zbl 1122.68377 |
| [25] | Lin, F., Zhao, Y.: ASSAT: Computing answer sets of a logic program by SAT solvers. In: Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-2002), AAAI Press, Edmonton, Alberta, Canada (2002) · Zbl 1085.68544 |
| [26] | Lin, F., Zhao, Y.: ASSAT: computing answer sets of a logic program by SAT solvers. Artif. Intell. 157(1-2), 115–137 (2004) · Zbl 1085.68544 · doi:10.1016/j.artint.2004.04.004 |
| [27] | Minker, J.: On indefinite data bases and the closed world assumption. In: Loveland, D. (ed.) Proceedings of the 6th Conference on Automated Deduction (CADE ’82). Lecture Notes in Computer Science, vol. 138, pp. 292–308. Springer, New York, USA (1982) · Zbl 0481.68087 |
| [28] | Minker, J.: Overview of disjunctive logic programming. Ann. Math. Artif. Intell. 12(1–2), 1–24 (1994) · doi:10.1007/BF01530759 |
| [29] | Niemelä, I., Simons, P.: Smodels–an implementation of the stable model and well-founded semantics for normal logic programs. In: Dix, J., Furbach, U., Nerode, A. (eds.) Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’97). Lecture Notes in AI (LNAI), vol. 1265, pp. 420–429. Springer Verlag, Dagstuhl, Germany (1997) |
| [30] | Prosser, P.: Hybrid algorithms for the constraint satisfaction problem. Comput. Intell. 9(3), 268–299 (1993) · doi:10.1111/j.1467-8640.1993.tb00310.x |
| [31] | Przymusinski, T.C.: Stable semantics for disjunctive programs. New Gener. Comput. 9, 401–424 (1991) · Zbl 0796.68053 · doi:10.1007/BF03037171 |
| [32] | Radziszowski, S.P.: Small Ramsey numbers. Electron. J. Comb. 1, revision 11: August 1, 2006 (1994) |
| [33] | Shen, K.: Overview of DASWAM: exploitation of dependent and-parallelism. J. Log. Program. 29(1–3), 245–293 (1996) · Zbl 0877.68018 · doi:10.1016/S0743-1066(96)00079-9 |
| [34] | Simons, P., Niemelä, I., Soininen, T.: Extending and implementing the stable model semantics. Artif. Intell. 138(1–2), 181–234 (2002) · Zbl 0995.68021 · doi:10.1016/S0004-3702(02)00187-X |
| [35] | Syrjänen, T.: Lparse 1.0 User’s Manual. http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz (2002) |
| [36] | Tsang, E.: Foundations of Constraint Satisfaction. Academic Press (1993) |
| [37] | Ullman, J.D.: Principles of Database and Knowledge Base Systems. Computer Science Press (1989) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
