Declarative Logic Programming. Michael Kifer

is a leading approach in LP to solving combinatorial problems. The well-founded semantics always yields a single, possibly three-valued, model and is popular with knowledge representation systems that focus on querying. This chapter provides a rigorous yet accessible introduction to both semantics.

      3. “A Survey of Probabilistic Logic Programming” by Fabrizio Riguzzi and Theresa Swift.

      Integration of probabilistic and logic reasoning is of great importance to modern Artificial Intelligence. This chapter provides a uniform introduction, based on what is called distribution semantics, to a number of leading approaches to such integration.

      Part II: Systems

      4. “WAM for Everyone: A Virtual Machine for Logic Programming” by David S. Warren.

      This chapter is an introduction to Warren’s Abstract Machine (WAM), the primary technology underlying modern LP systems. Unlike previous expositions of WAM, this chapter also describes tabling, one of the main breakthroughs that occurred since D.H.D. Warren developed the original WAM in 1970’s.

      5. “Predicate Logic as a Modeling Language: The IDP System” by Broes De Cat, Bart Bogaerts, Maurice Bruynooghe, Gerda Janssens, and Marc Denecker.

      IDP is a language and system that supports classical predicate logic extended with inductive definitions as rules, and with aggregation, functions, and types. It promotes a declarative semantics of logic programs and allows a single logical specification to be used in multiple different reasoning tasks to solve a range of problems. This chapter gives an overview of the IDP language and system.

      6. “SolverBlox: Algebraic Modeling in Datalog” by Conrado Borraz-Sánchez, Diego Klabjan, Emir Pasalic, and Molham Aref.

      LogiQL extends Datalog with aggregation, reactive rules, and constraints to support transactions in a database and software development platform called LogicBlox. This chapter introduces LogiQL and shows how it can be used to specify and solve mixed-integer linear optimization problems by adding simple declarations.

      Part III: Applications

      7. “Exploring Life: Answer Set Programming in Bioinformatics” by Alessandro Dal Palù, Agostino Dovier, Andrea Formisano, and Enrico Pontelli.

      This chapter surveys applications of declarative LP in Bioinformatics, including in Genomics studies, Systems Biology, and Structural studies. The necessary biological background is provided when necessary. The applications selected for this survey all rely on the Answer Set Programming paradigm.

      8. “State-Space Search with Tabled Logic Programs” by C. R. Ramakrishnan.

      Model checking and planning are two important and challenging classes of problems that require extensive search through the possible 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.¹ 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