states of systems. This chapter gives an overview of both types of problems as applications of LP. It focuses on tabling as an effective technique for improving the performance of state space search.
9. “Natural Language Processing with (Tabled and Constraint) Logic Programming” by Henning Christiansen and Verónica Dahl.
Natural language processing (NLP) was the original motivation for the development of Prolog, the most popular logic-based language. This chapter is an overview of the applications of LP to NLP, primarily based on definite clause grammars.
10. “Logic Programming Applications: What Are the Abstractions and Implementations?” by Yanhong A. Liu.
LP is used in many areas and contexts but the applicability of LP needs to be understood in more fundamental ways. This chapter gives an overview of LP applications, classifying them based on three key abstractions and their corresponding implementations. The abstractions are join, recursion, and constraint. The corresponding implementations are for-loops, fixed points, and backtracking.
Acknowledgments
Congratulations to the chapter authors for the well-thought-out surveys—all written specifically for this book. Each contribution was carefully reviewed, with at least four reviews per chapter. We are deeply grateful to the reviewers for the time and effort dedicated to perfecting the book material. Many thanks to the Editor-in-Chief of ACM Books series, M. Tamer Özsu, for his support, and to Diane Cerra of Morgan & Claypool for her help, guidance, and patience throughout the process. We were lucky to have an expert production team: Paul Anagnostopoulos of Windfall Software, who masterfully typeset this book; Sara Kreisman of Rambling Rose Press, who copyedited the pesky typos out of existence; Brent Beckley of Morgan & Claypool, who designed the beautiful and artsy cover; and Christine Kiilerich, also of Morgan & Claypool, who helped with many publication tasks.
We also acknowledge the support of NSF under grants CCF-0964196, CCF-1248184, CCF-1414078, and IIS-1447549; and of ONR under grant N000141512208.
PART I
THEORY
1
Datalog: Concepts, History, and Outlook
David Maier, K. Tuncay Tekle, Michael Kifer, David S. Warren
This chapter is a survey of the history and the main concepts of Datalog. We begin with an introduction to the language and its use for database definition and querying. We then look back at the threads from logic languages, databases, artificial intelligence, and expert systems that led to the emergence of Datalog and reminiscence about the origin of the name. We consider the interaction of recursion with other common data language features, such as negation and aggregation, and look at other extensions, such as constraints, updates, and object-oriented features. We provide an overview of the main approaches to Datalog evaluation and their variants, then recount some early implementations of Datalog and of similar deductive database systems. We speculate on the reasons for the decline in the interest in the language in the 1990s and the causes for its later resurgence in a number of application areas. We conclude with several examples of current systems based on or supporting Datalog and briefly examine the performance of some of them.
1.1 Introduction
Datalog has had a tumultuous history during which interest in it waxed and waned and waxed again. The name was originally coined to designate a simplified Hornlogic language akin to Prolog, but has since come to identify research on deductive databases and recursive query processing. Given the more than three decades since the introduction of Datalog, the time is right to explore its roots, recount early work on it, try to understand its declining fortunes in the 1990s, and examine the recent resurgence of interest in the language. This chapter is not intended to be a tutorial on Datalog nor a comprehensive research survey; rather, it is a recounting of developments in the history of Datalog, with some personal interpretation here and there.
Before examining the roots of Datalog, we review the basics of the language. We begin with a sample database that we employ throughout, followed by some examples of a Datalog program and queries that use that database. The database contains information about doctoral theses and advisors.1 We use a schema with four relations to represent academic-descendant information:
The person relation provides an identifier for each person involved, along with the person’s name. The relation area provides areas and long descriptions of the different areas for theses. The thesis relation gives details on a person’s thesis, while advised captures the information about the advisor(s) for a person. (One can have multiple advisors if they jointly advised that person or if the person obtained multiple Ph.D. degrees.)
A Datalog program typically consists of facts and rules. A fact asserts that a particular tuple belongs to a relation. From a logical viewpoint, it represents a predicate being true for a particular combination of values. Below are some Datalog facts corresponding to the thesis schema. An alphanumeric value starting with a lowercase letter is a unique symbol, not equal to any other value. If a symbol starts with a capital letter or if it contains non-alphanumeric characters (e.g., a space) then it is enclosed in single quotes. The year is represented here as an integer. From the data below we see that David Warren completed his Ph.D. thesis on Montague grammars at Michigan in 1979, under the direction of Joyce Friedman and William Rounds.
A Datalog rule is similar to a view definition in relational database systems. It states that if certain tuples exist in specific relations, then an additional tuple is assumed to exist in a “virtual” or derived relation. It can also be considered an inference rule for deducing new facts from existing ones. A rule has a head followed by a body, separated by the symbol :–, which is intended to resemble a left-pointing implication arrow. The head indicates the tuple being defined, and the body is a comma-separated list of facts, in which the commas are interpreted as “and”. A rule generally contains one or more logical variables, which begin with uppercase letters.2 Note that, under these conventions, First would be a variable, while 'First' a constant symbol. The rule asserts that the implication holds for all possible substitutions of the logical variables. For example, suppose we want to define a relation with certain information about people who received a Ph.D. in the area of Computer Science. We could use the following Datalog rule:
One way to understand a Datalog rule is as standing for all ground instances of the rule obtained by consistently substituting constants for the logical variables. Two such instances of the rule above are
The effect of a rule is to extend the database by the fact in the head for every such ground instance whenever all the facts in the body have been previously established—either because they are given explicitly as facts or because they were obtained from an instance of some rule using the same reasoning. Considering the two instances above, the first establishes the fact
as
