Invited Talks:

• Thomas Eiter (TU Wien)
• Yuri Gurevich (Microsoft Research)
• Phokion Kolaitis (UC Santa Cruz and IBM Research - Almaden)
• Robert Kowalski (Imperial College)
• Oege de Moor (Oxford U.)
• Marie-Laure Mugnier (U. of Montpellier)

Invited Tutorials:

• Todd J. Green (UC Davis and LogicBlox)
• Axel Polleres (Siemens AG Austria)

Monday September 10th

Tuesday September 11th

Wednesday September 12th

Thursday September 13th

The workshop will take place in Hörsaal 6 (HS6) / Lecture Hall 6 (see venue for details). The only exception will be the Keynote of Robert Kowalski (Tuesday, 16:30 - 17:30) that will take place in Hörsaal 8 (HS8) / Lecture Hall 8, which is located next to HS6 (if you leave HS6, turn right and go straight ahead until you bump into HS8).

Paraconsistent Modular Answer Set Programming

Thomas Eiter (Vienna University of Technology)

Paraconsistent reasoning is a well-studied approach to deal with inconsistencyin logical theories in a way such that inference does not explode. It has specifically been considered in the area of knowledge representation and reasoning for a range of different formalisms, including also non-monotonic formalisms such as logic programming. In the last years, there has been increasing interest in datalog-based formalisms, including traditional Answer Set Programming, and extensions of the formalisms to encompass modularity, possibly in a distributed environment, have been conceived. In this talk, we shall address the issue of paraconsistency for modular logic programs in a datalog setting, under the answer set semantics for logic programs. The two orthogonal aspects of modularity and paraconsistency for this semantics, which is subsumed by Equilibrium Logic, may be approached on different grounds. We shall consider developments on these aspects, including proposals for modularity and paraconsistency of answer set programs developed at TU Wien. For the latter particular emphasis is given to the issue of incoherence, i.e., non-existence of answer sets due to the lack of stability caused by cyclic dependencies of an atom from its default negation. We shall then consider possible combinations of the two aspects in a single formalism. In the course of this, we shall discuss issues and challenges regarding semantics and evaluation, both in theory and for practical concerns.

Datalog: A perspective and the potential

Yuri Gurevich (Microsoft Research)

Our main goal is to put Datalog into a proper logic perspective. It may be too early to put Datalog into a proper perspective from the point of view of applications; nevertheless we discuss why Datalog pops up so often in applications.

A Retrospective on Datalog 1.0

Phokion Kolaitis (UC Santa Cruz and IBM Research - Almaden)

Datalog was introduced in the early 1980s as a database query language that embodies a recursion mechanism on relational databases and, thus, overcomes some of the inherent limitations in the expressive power of relational algebra and relational calculus. In the ensuing decade, Datalog became the subject of an in-depth investigation by researchers in database theory. This study spanned a wide spectrum of topics, including query processing and optimization of Datalog programs, the delineation of the expressive power and computational complexity of Datalog queries, and the exploration of the semantics and the expressive power of extensions of Datalog with comparison operators and negation. The investigation of these topics entailed extensive interaction of database theory with finite model theory and, in particular, with finite-variable logics and pebble games suitable for analyzing the expressive power of Datalog and its variants. From the early 1990s on, there has been a fruitful and far-reaching interaction between Datalog and constraint satisfaction; this interaction, which continues today, has contributed to the understanding of tractable cases of the constraint satisfaction problem, but has also given rise to new results about the expressive power and the computational complexity of Datalog queries.

Towards a Logic-based, Unifying Framework for Computing

Robert Kowalski (Imperial College)

Computing, as a scientific discipline, lacks a unifying framework. It consists, instead, of diverse techniques in such various areas as programming, databases, and artificial intelligence.
Logic programming was an early attempt to provide a unifying framework for computing, based on the use of logic for knowledge representation and problem- solving. This attempt had only limited success, arguably because it failed to address adequately the fundamental role of state transition systems in computing.
In this talk, I sketch a logic-based framework for state transition systems, in which states can variously represent sets of shared variables, relational databases, Herbrand models, or mental representations of the real world. Given an initial set of goals, the computational task is to solve the goals by generating an appropriate sequence of actions and associated state transitions. Logically, the task is to make the goals true by generating a model of the goals with an explicit representation of time. Operationally, the task is solved by maintaining only the current state and updating it destructively. Frame axioms, which express that any facts not affected by an action persist from one state to the next state, are true in the model, but are not used operationally to generate it.
Joint talk with RR and COMMA

Engineering Datalog

Oege de Moor (University of Oxford)

Datalog has beautiful and crisp semantics, but it hasn't yet been widely adopted in industry. In this talk, I will argue that Datalog lacks the necessary software engineering properties for wide-spread adoption, and I will report on experience within Semmle and at Semmle's clients to overcome that problem.
Our first and most significant step was to introduce object-orientation without compromising the clean semantics. The "power of the dot" enables the easy creation and use of query libraries. It did however require the invention of several novel optimizations to ensure the abstraction facilities do not incur prohibitive efficiency overheads.
We also introduced several static analyses to catch common errors in Datalog programs, which are essential because debugging queries can be hard.
Finally, I'll highlight a few areas where we initially got our language design wrong, in particular for recursive aggregates and to support fast reachability queries, and I'll explain how we corrected those early mistakes.

Existential Rules: A Graph-based View

Marie-Laure Mugnier (University of Montpellier)

We consider existential rules, that allow to assert the existence of new individuals. Existential rules have long been studied in databases as high-level constraints called tuple generating dependencies (TGDs). Recently they have also been studied in connection with Datalog. In particular, existential rules have motivated a recent extension of Datalog with value invention, called Datalog+/-. Existential rules have also been studied as part of another line of research based on (hyper)graphs. This formalism, based on conceptual graphs, introduces a notion of reasoning that relies on graph mechanisms, which are sound and complete with respect to the logical semantics of the rules.
In this talk, we present a graph view of the existential rule framework and some related results. Two examples of results exploiting the graph structure will be detailed: the decidable class of (greedy) bounded-treewidth sets of rules, which is based on the tree decomposition of a graph, and a backward chaining mechanism based on subgraphs called pieces.

Invited Tutorials

LogicBlox, Platform and Language: a Tutorial

Todd J. Green (University of California, Davis and LogicBlox)

The modern enterprise software stack a collection of applications supporting bookkeeping, analytics, planning, and forecasting for enterprise data is in danger of collapsing under its own weight. The task of building and maintaining enterprise software is tedious and laborious; applications are cumbersome for end-users; and adapting to new computing hardware and infrastructures is difficult. We believe that much of the complexity in todays architecture is accidental, rather than inherent. This tutorial provides an overview of the LogicBlox platform, an ambitious redesign of the enterprise software stack centered around a unified declarative programming model, based on an extended version of Datalog. (joint work with Molham Aref and Grigoris Karvounarakis, LogicBlox)

How (well) do Datalog, SPARQL and RIF interplay?

Axel Polleres (Siemens AG Austria)

In this tutorial we will give an overview of the W3C standard query language for RDF - SPARQL - and its relation to Datalog as well as on the interplay with another W3C standard closely related to Datalog, the Rule Interchange Format (RIF). As we will learn while these three interplay nicely on the surface and in academic research papers some details within the W3C specs impose challenges on seamlessly integrating Datalog rules and SPARQL.