The Equational Approach to Contrary-to-duty Obligations

Dov M. Gabbay

Bar-Ilan University, Ramat-Gan, Israel King’s College London,

London, UK University of Luxembourg, Luxembourg


We apply the equational approach to logic to define numerical equational semantics and consequence relations for contrary to duty obligations, thus avoiding some of the traditional known paradoxes in this area. We also discuss the connection with abstract argumentation theory. Makinson and Torre’s input output logic and Governatori and Rotolo’s logic of violation.

Data Structures for Emergency Planing

Cyril Gavoille

LaBRI - University of Bordeaux, Bordeaux, France


We present in this talk different techniques for quickly answer graph problems where some of the nodes may be turn off. Typical graph problems are such as connectivity or distances between pair of nodes but not only. Emergency planing for such problems is achieved by pre-processing the graphs and by virtually preventing all possible subsequent node removals. To obtain efficient data structures, the idea is to attach very little and localized information to nodes of the input graph so that queries can be solved using solely on these information. Contexts and solutions for several problems will be surveyed.

A Survey of the Data Complexity of Consistent Query Answering Under Key Constraints

Jef Wijsen

Université de Mons, Mons, Belgium


This talk adopts a very elementary representation of uncertainty. A relational database is called uncertain if it can violate primary key constraints. A repair of an uncertain database is obtained by selecting a maximal number of tuples without selecting two distinct tuples of the same relation that agree on their primary key. For any Boolean query q, CERTAINTY(q) is the problem that takes an uncertain database db on input, and asks whether q is true in every repair of db. The complexity of these problems has been particularly studied for q ranging over the class of Boolean conjunctive queries. A research challenge is to solve the following complexity classification task: given q, determine whether CERTAINTY(q) belongs to complexity classes FO, P, or coNPcomplete. The counting variant of CERTAINTY(q), denoted ]CERTAINTY(q), asks to determine the exact number of repairs that satisfy q. This problem is related to query answering in probabilistic databases. This talk motivates the problems CERTAINTY(q) and ]CERTAINTY(q), surveys the progress made in the study of their complexity, and lists open problems. We also show a new result comparing complexity boundaries of both problems with one another.