August 10 – 14 , 2014, Dagstuhl Seminar 14331

Querying and Reasoning Under Expressive Constraints


Michael Benedikt (University of Oxford, GB)
Carsten Lutz (Universität Bremen, DE)
Balder Ten Cate (University of California – Santa Cruz, US)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 4, Issue 8 Dagstuhl Report
Aims & Scope
List of Participants
Dagstuhl Seminar Schedule [pdf]



Query answering in the presence of expressive constraints and logical rules is a topic that has drawn attention from several different research communities. In databases, the interaction of constraints and queries arises in the context of query optimization - for example, how to make use of integrity constraints such as inclusion dependencies and functional dependencies in running a query more efficiently. The topic is also central to the more recent database topics of data integration and data exchange, where constraints are used in the specification of schema mappings. In the area of knowledge representation, the interaction of constraints and queries plays a great role as well - particularly in ontology-based query answering.

The work in these areas is closely related also to another fundamental topic in theoretical computer science, namely decidable fragments of first-order logic. In particular, many of the query answering and query analysis techniques used in recent work within databases and knowledge representation have close links to static analysis of guarded logics, a family of logics that arose out of work by the modal logic and finite model theory communities.

The seminar focused on the convergence of interest of the databases, knowledge representation, and computational logic communities. Its goal was to make visible the connections between these distinct communities, to look at tools and algorithms in one community that can be applied within others, to understand which formalisms and techniques are most promising from the perspective of practical applications, and to propose new ways to combine techniques across communities.

Overview and Outcome

The week started with three overview lectures from well-known authorities in databases, description logics, and decidable fragments of first-order logic. These talks introduced the necessary background for participants and raised research themes that would be explored in later talks. The week then proceeded with a wide-ranging series of talks by participants. In addition to finite model theory, description logics, and databases, there were also talks concerning the interaction of querying problems with constraint satisfaction. The presentations included theoretical work as well as system demonstrations and discussion of practical obstacles to efficient querying with constraints. There were two presentations by participants from industry (IBM and LogicBlox), describing products that implement integrity constraint-based approaches to entity resolution and data analytics, respectively. There was also a presentation on the status of constraint-based reasoning within the W3C endorsed query language SPARQL. In addition to the formal talks, the seminar had an open discussion session, which included a mention of some major open problems and directions to be explored for the communities, as well an attempt at mapping the distinct vocabularies of the different communities.

A main outcome of the discussion was a desire for further interaction between the communities. There were a number of proposals put forward for how to achieve this, including co-location of a KR-related conference with a database conference like VLDB or SIGMOD/PODS. Another outcome was a collection of topics that were particularly worth pursuing by all communities. The handling of inconsistency in databases was one of these -- both further investigation of the most widely-used approach for inconsistency-handling, based on repair and consistent query answering, and the examination of alternative approaches. The notion of repair tied into the question of investigating the relationship of data uncertainty and constraints. Markov logic networks (MLNs) are likely to play a role in reconciling ``hard'' integrity constraints with probabilities, although the interplay of probabilistic data and classical approaches to integrity constraints will involve a more general revision of the major computational problems with uncertainty in mind. Another topic identified for future work was the notion of incremental checking of constraints. Incremental computation was alluded to in several talks, but there appears to be a need to take a more holistic look at models for incremental computation and their application in constraint maintenance. The recent activity within dynamic complexity makes the topic of incremental computation within constraint handling particularly ripe for revisiting.


We believe that the seminar was very successful in bringing together the involved communities and in promoting interaction and exchange between them. Similarities as well as differences between the communities' research efforts became clearly visible and the participants conceived the seminar as a significant step forwards in bridging the gap and raising mutual awareness. Many participants expressed interest in a followup event.

Summary text license
  Creative Commons BY 3.0 Unported license
  Michael Benedikt, Carsten Lutz, and Balder Ten Cate


  • Artificial Intelligence / Robotics
  • Data Bases / Information Retrieval
  • Verification / Logic


  • Constraints
  • Ontologies
  • Queries
  • Reasoning
  • Decidability
  • Information Integration


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.