Invited Talks:

Invited Tutorials:

Monday September 10th

19:00 Registration and Opening Reception

Tuesday September 11th

8:30 - 9:30 Registration
9:00 - 10:00 Session (jointly with RR)
9:00 - 10:00 Keynote: Phokion Kolaitis
A Retrospective on Datalog 1.0
10:00 - 10:30 Coffee break
10:30 - 12:30 Session: New applications of Datalog
10:30 - 11:00 Query Rewriting using Datalog for Duplicate Resolution
Jaffer Gardezi and Leopoldo Bertossi
11:00 - 11:30 Optimizing Large-Scale Semi-Naive Datalog Evaluation in Hadoop
Marianne Shaw, Paraschos Koutris, Bill Howe and Dan Suciu
11:30 - 12:00 Logical Foundations of Continuous Query Languages for Data Streams
Carlo Zaniolo
12:00 - 12:30 Order in Datalog with Applications to Declarative Output
Stefan Brass
12:30 - 14:30 Lunch break
14:30 - 16:00 Session: Datalog for distributed systems
14:30 - 15:00 Confluence Analysis for Distributed Programs: A Model-Theoretic Approach
William Marczak, Peter Alvaro, Neil Conway, Joseph Hellerstein and David Maier
15:00 - 15:30 On the CRON Conjecture
Tom Ameloot and Jan Van Den Bussche
15:30 - 16:00 Reasoning about Knowledge in Distributed Systems Using Datalog
Matteo Interlandi
16:00 - 16:30 Coffee break
16:30 - 17:30 Session (jointly with RR and COMMA)
16:30 - 17:30
Keynote: Robert Kowalski
Towards a Logic-based, Unifying Framework for Computing
19:30 - Workshop Dinner

Wednesday September 12th

9:00 - 10:00 Session
9:00 - 10:00 Keynote: Yuri Gurevich
Datalog: A Perspective and the Potential
10:00 - 10:30 Coffee break
10:30 - 12:30 Session: Tutorials
10:30 - 11:30 Tutorial: LogicBlox, Platform and Language: a Tutorial
T.J. Green, Molham Aref and Grigoris Karvounarakis
11:30 - 12:30 Tutorial: Datalog Development Tools
Onofrio Febbraro, Giovanni Grasso, Nicola Leone, Kristian Reale and Francesco Ricca
12:30 - 14:30 Lunch break
14:30 - 16:00 Session: Datalog and constraints
14:30 - 15:00 A broad class of first-order rewritable tuple-generating dependencies
Cristina Civili and Riccardo Rosati
15:00 - 15:30 Inconsistency-Tolerant Query Rewriting for Linear Datalog+/-
Thomas Lukasiewicz, Maria Vanina Martinez and Gerardo Simari
15:30 - 16:00 Data Exchange in Datalog is mainly a Matter of Choice
Domenico Sacca and Edoardo Serra
16:00 - 16:30 Coffee break
16:30 - 18:30 Session
16:30 - 17:30 Keynote: Marie-Laure Mugnier
Existential Rules: A Graph-based View
17:30 - 18:30 Keynote: Oege de Moor
Engineering Datalog

Thursday September 13th

9:00 - 10:00 Session
9:00 - 10:00 Keynote: Thomas Eiter
Paraconsistent Modular Answer Set Programming
10:00 - 10:30 Coffee break
10:30 - 12:00 Session: System applications
10:30 - 11:30 Tutorial: How (well) do Datalog, SPARQL, and RIF interplay?
Axel Polleres
11:30 - 12:00 System description: Business Network Reconstruction using Datalog
Daniel Ritter and Till Westmann
12:00 - 12:30 Lunch break
12:30 - 13:30 Session: On Datalog per se
12:30 - 13:00 Magic-Sets for Datalog with Existential Quantifiers
Mario Alviano, Nicola Leone, Marco Manna, Giorgio Terracina and Pierfrancesco Veltri
13:00 - 13:30 Declarative Datalog Debugging for Mere Mortals
Sven Koehler, Bertram Ludaescher and Yannis Smaragdaki
13:30 Closing

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).

Invited Talks

Paraconsistent Modular Answer Set Programming

Thomas Eiter (Vienna University of Technology)

Thomas Eiter 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)

Yuri Gurevich 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)

Phokion Kolaitis 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)

Robert Kowalski 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)

Oege de Moor 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)

Marie-Laure Mugnier 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)

Todd J. Green 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)

Axel Polleres 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.