10.08.14 - 14.08.14, Seminar 14331

Querying and Reasoning Under Expressive Constraints

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.


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.