Cited By
View all- Khamis MNgo HPichler RSuciu DRemy Wang Y(2022)Datalog in WonderlandACM SIGMOD Record10.1145/3552490.355249251:2(6-17)Online publication date: 29-Jul-2022
Recursive Rules with Aggregation: A Simple Unified Semantics
Pages 156 - 179
Abstract
Complex reasoning problems are most clearly and easily specified using logical rules, but require recursive rules with aggregation such as counts and sums for practical applications. Unfortunately, the meaning of such rules has been a significant challenge, leading to many disagreeing semantics.
This paper describes a unified semantics for recursive rules with aggregation, extending the unified founded semantics and constraint semantics for recursive rules with negation. The key idea is to support simple expression of the different assumptions underlying different semantics, and orthogonally interpret aggregation operations using their simple usual meaning. We present formal definition of the semantics, prove important properties of the semantics, and compare with prior semantics. In particular, we present an efficient inference over aggregation that gives precise answers to all examples we have studied from the literature. We also applied our semantics to a wide range of challenging examples, and performed experiments on the most challenging ones, all confirming our analyzed results.
References
[1]
Alviano M Evaluating answer set programming with non-convex recursive aggregates Fundamenta Informaticae 2016 149 1–2 1-34
[2]
Alviano M et al. Balduccini M, Janhunen T, et al. The ASP system DLV2 Logic Programming and Nonmonotonic Reasoning 2017 Cham Springer 215-221
[3]
Alviano M, Dodaro C, and Maratea M Shared aggregate sets in answer set programming Theory Pract. Logic Program. 2018 18 3–4 301-318
[4]
Alviano M, Faber W, and Gebser M Rewriting recursive aggregates in answer set programming: back to monotonicity Theory Pract. Logic Program. 2015 15 4–5 559-573
[5]
Alviano, M., Faber, W., Gebser, M.: From non-convex aggregates to monotone aggregates in ASP. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 4100–4104 (2016)
[6]
Alviano M and Leone N Complexity and compilation of GZ-aggregates in answer set programming Theory Pract. Logic Program. 2015 15 4–5 574-587
[7]
Apt, K.R., Blair, H.A., Walker, A.: Towards a theory of declarative knowledge. In: Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufmann (1988)
[8]
Apt KR and Bol RN Logic programming and negation: a survey J. Logic Program. 1994 19 9-71
[9]
Beeri, C., Ramakrishnan, R., Srivastava, D., Sudarshan, S.: The valid model semantics for logic programs. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 91–104 (1992)
[10]
Bruynooghe M, Denecker M, and Truszczynski M First order logic with inductive definitions for model-based problem solving AI Mag. 2016 37 3 69-80
[11]
Cabalar P, Fandinno J, Del Cerro LF, and Pearce D Functional ASP with intensional sets: application to Gelfond-Zhang aggregates Theory Pract. Logic Program. 2018 18 3–4 390-405
[12]
Cabalar P, Fandinno J, Schaub T, and Schellhorn S Gelfond-zhang aggregates as propositional formulas Artif. Intell. 2019 274 26-43
[13]
Ceri S, Gottlob G, and Tanca L Logic Programming and Databases 1990 Heidelberg Springer
[14]
Clark KL Gallaire H and Minker J Negation as failure Logic and Databases 1978 New York Plenum Press 293-322
[15]
Consens MP and Mendelzon AO Low-complexity aggregation in GraphLog and Datalog Theor. Comput. Sci. 1993 116 1 95-116
[16]
Das, A., Li, Y., Wang, J., Li, M., Zaniolo, C.: Bigdata applications from graph analytics to machine learning by aggregates in recursion. In: Proceedings of the 35th International Conference on Logic Programming (Technical Communications), pp. 273–279 (2019)
[17]
Denecker M and Ternovska E A logic of nonmonotone inductive definitions ACM Trans. Comput. Logic 2008 9 2 14
[18]
Dung PM On the relations between stable and well-founded semantics of logic programs Theor. Comput. Sci. 1992 105 1 7-25
[19]
Faber W, Pfeifer G, and Leone N Semantics and complexity of recursive aggregates in answer set programming Artif. Intell 2011 175 1 278-298
[20]
Faber W, Pfeifer G, Leone N, Dell’Armi T, and Ielpa G Design and implementation of aggregate functions in the DLV system Theory Pract. Logic Program. 2008 8 5–6 545-580
[21]
Ferraris P Logic programs with propositional connectives and aggregates ACM Trans. Comput. Logic 2011 12 4 1-40
[22]
Fitting M A Kripke-Kleene semantics for logic programs J. Logic Program. 1985 2 4 295-312
[23]
Fitting M Fixpoint semantics for logic programming: a survey Theor. Comput. Sci. 2002 278 1 25-51
[24]
Ganguly, S., Greco, S., Zaniolo, C.: Minimum and maximum predicates in logic programming. In: Proceedings of the 10th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 154–163 (1991)
[25]
Gelfond M Kakas AC and Sadri F Representing knowledge in A-prolog Computational Logic: Logic Programming and Beyond 2002 Heidelberg Springer 413-451
[26]
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Proceedings of the 5th International Conference and Symposium on Logic Programming, pp. 1070–1080. MIT Press (1988)
[27]
Gelfond M and Zhang Y Vicious circle principle and logic programs with aggregates Theory Pract. Logic Program. 2014 14 4–5 587-601
[28]
Gelfond M and Zhang Y Balduccini M and Janhunen T Vicious circle principle and formation of sets in ASP based languages Logic Programming and Nonmonotonic Reasoning 2017 Cham Springer 146-159
[29]
Gelfond, M., Zhang, Y.: Vicious circle principle and logic programs with aggregates. Computing Research Repository (2018). cs.AI arXiv:1808.07050
[30]
Gelfond M and Zhang Y Vicious circle principle, aggregates, and formation of sets in ASP based languages Artif. Intell. 2019 275 28-77
[31]
Gu, J., et al.: RaSQL: Greater power and performance for big data analytics with recursive-aggregate-SQL on Spark. In: Proceedings of the 2019 International Conference on Management of Data, pp. 467–484 (2019)
[32]
Hella, L., Libkin, L., Nurmonen, J., Wong, L.: Logics with aggregate operators. In: Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, p. 35. IEEE Computer Society (1999)
[33]
Hella L, Libkin L, Nurmonen J, and Wong L Logics with aggregate operators J. ACM 2001 48 4 880-907
[34]
Hou P, De Cat B, and Denecker M FO(FD): extending classical logic with rule-based fixpoint definitions Theory Pract. Logic Program. 2010 10 4–6 581-596
[35]
Irvine, A.D., Deutsch, H.: Russell’s paradox. Stanford Encyclopedia of Philosophy (2020). https://plato.stanford.edu/entries/russell-paradox/, First published Fri Dec 8, 1995; substantive revision Mon Oct 12, 2020, Accessed 3 Jan 2021
[36]
Kemp, D.B., Stuckey, P.J.: Semantics of logic programs with aggregates. In: Proceedings of the International Symposium on Logic Programming, pp. 387–401 (1991)
[37]
Lin F and Zhao Y ASSAT: computing answer sets of a logic program by SAT solvers Artif. Intell. 2004 157 1–2 115-137
[38]
Liu L, Pontelli E, Son TC, and Truszczynski M Logic programs with abstract constraint atoms: The role of computations Artif. Intell. 2010 174 3 295-315
[39]
Liu, Y.A.: Logic programming applications: what are the abstractions and implementations? In: Kifer, M., Liu, Y.A. (eds.) Declarative Logic Programming: Theory, Systems, and Applications, chap. 10, pp. 519–557. ACM and Morgan & Claypool (2018)
[40]
Liu YA and Stoller SD From datalog rules to efficient programs with time and space guarantees ACM Trans. Program. Lang. Syst. 2009 31 6 1-38
[41]
Liu YA and Stoller SD Artemov S and Nerode A Founded semantics and constraint semantics of logic rules Logical Foundations of Computer Science 2018 Cham Springer 221-241
[42]
Liu, Y.A., Stoller, S.D.: Founded semantics and constraint semantics of logic rules. J. Logic Comput. 30(8), 1609–1638 (2020). http://arxiv.org/abs/1606.06269
[43]
Liu YA and Stoller SD Artemov S and Nerode A Knowledge of uncertain worlds: programming with logical constraints Logical Foundations of Computer Science 2020 Cham Springer 111-127
[44]
Liu, Y.A., Stoller, S.D.: Recursive rules with aggregation: a simple unified semantics. Computing Research Repository (2020). cs.DB arXiv:2007.13053
[45]
Liu, Y.A., Stoller, S.D.: Knowledge of uncertain worlds: programming with logical constraints. J. Logic Comput. 31(1), 193–212 (2021). https://arxiv.org/abs/1910.10346
[46]
Liu, Y.A., Stoller, S.D., Lin, B.: From clarity to efficiency for distributed algorithms. ACM Trans. Program. Lang. Syst. 39(3), 12:1–12:41 (2017)
[47]
Marek VW and Remmel JB Lifschitz V and Niemelä I Set constraints in logic programming Logic Programming and Nonmonotonic Reasoning 2003 Heidelberg Springer 167-179
[48]
Marek, V.W., Truszczynski, M.: Logic programs with abstract constraint atoms. In: Proceedings of the 19th National Conference on Artificial Intelligence, 16th Conference on Innovative Applications of Artificial Intelligence, pp. 86–91. AAAI Press/The MIT Press (2004)
[49]
Mumick, I.S., Pirahesh, H., Ramakrishnan, R.: The magic of duplicates and aggregates. In: Proceedings of the 16th International Conference on Very Large Databases, pp. 264–277. Morgan Kaufmann (1990)
[50]
Pelov N, Denecker M, and Bruynooghe M Well-founded and stable semantics of logic programs with aggregates Theory Pract. Logic Program. 2007 7 3 301-353
[51]
Przymusinski TC Well-founded and stationary models of logic programs Ann. Math. Artif. Intell 1994 12 3 141-187
[52]
Ramakrishnan R and Ullman JD A survey of deductive database systems J. Logic Program. 1995 23 2 125-149
[53]
Ross, K.A., Sagiv, Y.: Monotonic aggregation in deductive databases. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 114–126 (1992)
[54]
Ross KA and Sagiv Y Monotonic aggregation in deductive databases J. Comput. Syst. Sci. 1997 54 1 79-97
[55]
Schlipf JS The expressive powers of the logic programming semantics J. Comput. Syst. Sci. 1995 51 1 64-86
[56]
Shkapsky, A., Yang, M., Zaniolo, C.: Optimizing recursive queries with monotonic aggregates in DeALS. In: Proceedings of the 2015 IEEE 31st International Conference on Data Engineering, pp. 867–878 (2015)
[57]
Simons P, Niemelä I, and Soininen T Extending and implementing the stable model semantics Artif. Intell 2002 138 1–2 181-234
[58]
Son TC, Pontelli E, and Tu PH Answer sets for logic programs with arbitrary abstract constraint atoms J. Artif. Intell. Res. 2007 29 353-389
[59]
Sudarshan, S., Srivastava, D., Ramakrishnan, R., Beeri, C.: Extending the well-founded and valid semantics for aggregation. In: Proceedings of the 1993 International Symposium on Logic programming, pp. 590–608 (1993)
[60]
Swift, T., et al.: The XSB System Version 3.8, x (2017). http://xsb.sourceforge.net
[61]
Truszczynski, M.: An introduction to the stable and well-founded semantics of logic programs. In: Kifer, M., Liu, Y.A. (eds.) Declarative Logic Programming: Theory, Systems, and Applications, pp. 121–177. ACM and Morgan & Claypool (2018)
[62]
Van Gelder, A.: Negation as failure using tight derivations for general logic programs. In: Proceedings of the 3rd IEEE-CS Symposium on Logic Programming, pp. 127–138 (1986)
[63]
Van Gelder, A.: The well-founded semantics of aggregation. In: Proceedings of the 11th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, San Diego, California, 2–4 June 1992, pp. 127–138 (1992)
[64]
Van Gelder A The alternating fixpoint of logic programs with negation J. Comput. Syst. Sci. 1993 47 1 185-221
[65]
Van Gelder, A., Ross, K., Schlipf, J.S.: Unfounded sets and well-founded semantics for general logic programs. In: Proceedings of the 7th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 221–230 (1988)
[66]
Van Gelder A, Ross K, and Schlipf JS The well-founded semantics for general logic programs J. ACM 1991 38 3 620-650
[67]
Vanbesien, L., Bruynooghe, M., Denecker, M.: Analyzing semantics of aggregate answer set programming using approximation fixpoint theory. Computing Research Repository (2021). cs.AI arXiv:2104.14789
[68]
Wang, Q., et al.: Automating incremental and asynchronous evaluation for recursive aggregate data processing. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 2439–2454 (2020)
[69]
Wielemaker J, Schrijvers T, Triska M, and Lager T SWI-Prolog Theory Pract. Logic Program. 2012 12 1–2 67-96
[70]
Zaniolo C, Arni N, and Ong K Ceri S, Tanaka K, and Tsur S Negation and aggregates in recursive rules: the LDL++ approach Deductive and Object-Oriented Databases 1993 Heidelberg Springer 204-221
[71]
Zaniolo, C., Das, A., Gu, J., Li, Y., Li, M., Wang, J.: Monotonic properties of completed aggregates in recursive queries. Computing Research Repository (2019). cs.DB arXiv:1910.08888
[72]
Zaniolo C, Yang M, Das A, Shkapsky A, Condie T, and Interlandi M Fixpoint semantics and optimization of recursive datalog programs with aggregates Theory Pract. Logic Program. 2017 17 5–6 1048-1065
[73]
Zhang, Y., Rayatidamavandi, M.: A characterization of the semantics of logic programs with aggregates. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1338–1344 (2016)
Index Terms
- Recursive Rules with Aggregation: A Simple Unified Semantics
Index terms have been assigned to the content through auto-classification.
Recommendations
Syntax and semantics for business rules
KES'10: Proceedings of the 14th international conference on Knowledge-based and intelligent information and engineering systems: Part IVBusiness processes are increasingly being expressed in declarative terms, as business rules which express obligations concerning conduct, action, practice or procedure regarding a particular business activity or sphere of operation. However, the leading ...
Deriving Pretty-Big-Step Semantics from Small-Step Semantics
Proceedings of the 23rd European Symposium on Programming Languages and Systems - Volume 8410Big-step semantics for languages with abrupt termination and/or divergence suffer from a serious duplication problem, addressed by the novel 'pretty-big-step' style presented by Charguéraud at ESOP'13. Such rules are less concise than corresponding ...
A unified semantics for constraint handling rules in transaction logic
LPNMR'07: Proceedings of the 9th international conference on Logic programming and nonmonotonic reasoningReasoning on Constraint Handling Rules (CHR) programs and their executional behaviour is often ad-hoc and outside of a formal system. This is a pity, because CHR subsumes a wide range of important automated reasoning services. Mapping CHR to Transaction ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jan 2022
385 pages
© Springer Nature Switzerland AG 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 10 January 2022
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
Cited By
View all- Khamis MNgo HPichler RSuciu DRemy Wang Y(2022)Datalog in WonderlandACM SIGMOD Record10.1145/3552490.355249251:2(6-17)Online publication date: 29-Jul-2022
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in