August 10 – 14 , 2014, Dagstuhl Seminar 14331
Querying and Reasoning Under Expressive Constraints
1 / 2 >
For support, please contact
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.
Creative Commons BY 3.0 Unported license
Michael Benedikt, Carsten Lutz, and Balder Ten Cate
- Artificial Intelligence / Robotics
- Data Bases / Information Retrieval
- Verification / Logic
- Information Integration