Dagstuhl Seminar 14331
Querying and Reasoning Under Expressive Constraints
( Aug 10 – Aug 14, 2014 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/14331
Organizers
- Michael Benedikt (University of Oxford, GB)
- Carsten Lutz (Universität Bremen, DE)
- Balder Ten Cate (University of California - Santa Cruz, US)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Schedule
The theme of the seminar is query answering in the presence of expressive constraints and logical rules,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 - e.g. 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 both these application areas has recently been seen to be 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 which arose out of work by the modal logic and finite model theory communities.
This seminar will focus on the convergence of interest of the databases, knowledge representation, and computational logic communities. It aims 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 practice, and to propose new ways to combine techniques across communities.
Topics of interest include:
- New applications of querying with constraints, including new uses of constraints in data integration and data cleaning.
- Logics that capture querying with constraints, including exploration of the boundaries of decidability for logics that are rich enough to be able to express large classes of constraints and queries.
- Complexity of query answering under constraints. For example, syntactic restrictions that ensure that these query answering tractable in data complexity; dichotomy theorems that effectively separate the tractable from the intractable cases; first-order rewritings and Datalog rewritings,
- Meta-data management: manipulating and optimizing constraints: optimization of schema mappings and ontologies; operations and transformations on schema mappings and ontologies.
- Revisiting data management architectures: the impact of new techniques for reasoning with expressive constraints on fundamental components database management systems, e.g., view and index selection for query optimization.
Motivation
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.
Conclusion
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
- Isolde Adler (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Antoine Amarilli (ENST - Paris, FR) [dblp]
- Molham Aref (LogicBlox - Atlanta, US) [dblp]
- Marcelo Arenas (Pontificia Universidad Catolica de Chile, CL) [dblp]
- Michael Benedikt (University of Oxford, GB) [dblp]
- Meghyn Bienvenu (University Paris-Sud, FR) [dblp]
- Manuel Bodirsky (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Pierre Bourhis (ENS - Cachan, FR) [dblp]
- Cristina Civili (SapienzaUniversity of Rome, IT) [dblp]
- Gaelle Fontaine (University of Chile - Santiago de Chile, CL) [dblp]
- Birte Glimm (Universität Ulm, DE) [dblp]
- Tomasz Gogacz (University of Wroclaw, PL) [dblp]
- André Hernich (University of Liverpool, GB) [dblp]
- Ian Horrocks (University of Oxford, GB) [dblp]
- Yazmin Angelica Ibanez-Garcia (Free University of Bozen-Bolzano, IT) [dblp]
- Emanuel Kieronski (University of Wroclaw, PL) [dblp]
- Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
- Roman Kontchakov (University of London, GB) [dblp]
- Tomer Kotek (TU Wien, AT) [dblp]
- Markus Krötzsch (TU Dresden, DE) [dblp]
- Carsten Lutz (Universität Bremen, DE) [dblp]
- Florent R. Madelaine (Clermont University, FR) [dblp]
- Jerzy Marcinkowski (University of Wroclaw, PL) [dblp]
- Wim Martens (Universität Bayreuth, DE) [dblp]
- Jakub Michaliszyn (Imperial College London, GB) [dblp]
- Giorgio Orsi (University of Oxford, GB) [dblp]
- Magdalena Ortiz (TU Wien, AT) [dblp]
- Martin Otto (TU Darmstadt, DE) [dblp]
- Reinhard Pichler (TU Wien, AT) [dblp]
- Andreas Pieris (University of Oxford, GB) [dblp]
- Lucian Popa (IBM Almaden Center, US) [dblp]
- Ian Pratt-Hartmann (University of Manchester, GB) [dblp]
- Sebastian Rudolph (TU Dresden, DE) [dblp]
- Vadim Savenkov (TU Wien, AT) [dblp]
- Inanc Seylan (Universität Bremen, DE) [dblp]
- Dan Suciu (University of Washington - Seattle, US) [dblp]
- Balder Ten Cate (University of California - Santa Cruz, US) [dblp]
- Lidia Tendera (University of Opole, PL) [dblp]
- Michaël Thomazo (TU Dresden, DE) [dblp]
- David Toman (University of Waterloo, CA) [dblp]
- Michael Vanden Boom (University of Oxford, GB) [dblp]
- Grant Weddell (University of Waterloo, CA) [dblp]
- Scott Weinstein (University of Pennsylvania, US) [dblp]
- Frank Wolter (University of Liverpool, GB) [dblp]
- Michael Zakharyaschev (University of London, GB) [dblp]
- Katja Zeume (Universität Bayreuth, DE) [dblp]
- Thomas Zeume (TU Dortmund, DE) [dblp]
Classification
- artificial intelligence / robotics
- data bases / information retrieval
- verification / logic
Keywords
- Constraints
- Ontologies
- Queries
- Reasoning
- Decidability
- Information Integration
