C. Zaniolo and H. Wang. 1999. Logic-based user-defined aggregates for the next generation of database systems. In The Logic Programming Paradigm: A 25-Year Perspective, pp. 401–426. Springer Berlin Heidelberg, Berlin, Heidelberg. DOI: 10.1007/978-3-642-60085-2_18. 25
C. Zaniolo, N. Arni, and K. Ong. Dec. 1993. Negation and aggregates in recursive rules: The LDL++ approach. In Proc. of the Third International Conference on Deductive and Object-Oriented Databases (DOOD), pp. 204–221. Springer-Verlag, Lecture Notes in Computer Science 760. 24
C. Zaniolo, S. Ceri, C. Faloutsos, R. T. Snodgrass, V. S. Subrahmanian, and R. Zicari. 1997. Advanced Database Systems. Morgan Kaufmann, San Francisco, CA. 42
C. Zaniolo, M. Yang, A. Das, A. Shkapsky, T. Condie, and M. Interlandi. 2017. Fixpoint semantics and optimization of recursive Datalog programs with aggregates. TPLP, 17(5-6):1048–1065. DOI: 10.1017/S1471068417000436. 83
N. Zhou, Y. Shen, L. Yuan, and J. You. 2001. Implementation of a linear tabling mechanism. Journal of Functional and Logic Programming, 2001(10). DOI: 10.1007/3-540-46584-7_8. 59
D. Zook, E. Pasalic, and B. Sarna-Starosta. 2009. Typed Datalog. In Proc. of the 11th International Symposium on Practical Aspects of Declarative Languages, PADL ’09, pp. 168–182. Springer-Verlag, Berlin, Heidelberg. 31
1. This example is inspired by the Mathematics Genealogy Project, http://genealogy.math.ndsu.nodak.edu/, which is also the source of most of the data used.
2. Another popular convention in Datalog systems is to prefix variables with the question mark, e.g., ?First, ?Area, ?Year.
3. We assume in this chapter a basic knowledge of relational database systems, such as relational algebra and the SQL query language. The necessary background would be included in any introductory database text, such as Garcia-Molina et al. [2009].
4. SQL:1999 introduced support for the comparatively limited form of linear recursion.
5. A Horn clause is a logical implication among positive literals with at most one literal in the consequent.
6. A list of these workshops can be found in http://dblp.uni-trier.de/db/conf/xp/index.html
7. The use of negation requires an additional syntactic condition to ensure safety, namely that every variable in a rule appear in at least one non-negated goal in the rule body. Thus, for example, a rule unrelated (P1, P2) :- not related (P1, P2) would not be safe.
8. Minimality in this context means there is no other satisfying truth assignment that makes a proper subset of the propositions true. Note that there can be multiple, incomparable such assignments.
9. The notation pred/N indicates that the predicate pred takes N arguments.
10. Beeri and Vardi [1981] viewed the above rules as constraints—or dependencies—and used a different, but equivalent, tableaux representation for them.
11. http://bitbucket.org/giorsi/nyaya
12. Another convention is to use a right-pointing arrow for rules that should be interpreted as integrity constraints [Aref et al. 2015].
14. F-logic frames can be viewed as a formalization of the concept of frames introduced by Minsky [1975].
15. In F-logic, classes are also objects and they can have information about themselves, which is not inherited by instances of these classes. In Java terms, this information corresponds to static methods.
16. LPS [Kowalski and Sadri 2012] is an exception, as it has some of the characteristics of Transaction Logic, described in the next subsection.
17. http://flora.sourceforge.net/tr-interpreter-suite.tar.gz
18. Syntactically, G subsumes F if F can be derived from G by substituting 0 or more variables with constants or other variables. So, for example, influenced(X, Y) subsumes influenced(dm, Y), influenced(X, X), influenced(X, Y), and influenced(dm, tjg).
19. Prolog pedagogues, when teaching data recursion, wisely choose graphs, for example, the advises relation, that can have no cycles.
20. http://docs.microsoft.com/en-us/sql/odbc/microsoft-open-database-connectivity-odbc
21. Another was WebLog [Lakshmanan et al. 1996], which deals with semi-structured data using a language very similar to F-logic.
22. http://www.w3.org/TR/2008/WD-owl2-profiles-20081008/#OWL_2_RL
23. http://ontotext.com/products/graphdb/
24. http://franz.com/agraph/allegrograph/
25. http://jena.apache.org/documentation/inference/
2
An Introduction to the Stable and Well-Founded Semantics of Logic Programs
Miroslaw Truszczynski
This chapter provides a brief introduction to two main semantics of logic programs with negation, the stable-model semantics of Gelfond and Lifschitz, and the well-founded semantics of Van Gelder, Ross, and Schlipf. We present definitions, introduce basic results, and relate the two semantics to each other. We restrict attention to the syntax of normal logic programs and focus on classical results. However, throughout the chapter and in concluding remarks we briefly discuss generalizations of the syntax and extensions of the semantics, and mention several recent developments.
2.1 Introduction
The roots of logic programming can be traced back to efforts to build resolutionbased automated theorem provers in the mid-1960s [Robinson 1965]. A realization that resolution can turn Horn theories into programs came about in the early 1970s and rested on the foundational work of Kowalski and Kuehner [1971] and Kowalski [1974], as well as the implementation effort of Colmerauer and his research group, in which the Prolog programming language was developed [Colmerauer et al. 1973].
Negation was present in Prolog from the very beginning. Its meaning was specified operationally through its implementation. However, for almost two decades, finding a satisfactory declarative account of negation was elusive. The first significant progress was obtained by Clark, who proposed reading programs as definitions and formalized that reading by means of the program completion [Clark 1978]. A different plan of attack was developed a few years later by Apt, Blair, and Walker [1988] and, independently, by Przymusinski [1988a, 1988b]. They introduced a large and natural class of programs with negation, called stratified programs, and showed that the meaning of a stratified program is captured by a certain well-motivated Herbrand model. Przymusinski [1988a] called this model perfect. Soon thereafter, Gelfond and Lifschitz [1988] proposed the stable-model semantics and Van Gelder et al. [1988, 1991] the well-founded semantics. The stable-model semantics was strongly influenced by research in knowledge representation concerned with the notion of nonmonotonic reasoning, and built on the semantics of default logic by Reiter [1980] and autoepistemic logic by Moore [1985]. The well-founded semantics followed the query-evaluation paradigm of Prolog but framed it in a three-valued setting.