New Perspectives on Query Reformulation

                                Michael Benedikt

                         Department of Computer Science
                            University of Oxford, UK


    This talk will discuss a very general notion of query reformulation: Given
a query Q, a set of constraints Σ, a target query language or programming
language, and a cost metric, determine if there is an object in the target language
that is equivalent to Q relative to the constraints, and if so find such an object
optimizing the cost metric. The problem has a long history in the database
community, originally motivated by querying over materialized views. This talk
will go over several very recent developments – from a database perspective, but
mentioning the relationship to description logics.
    We will first go over the connection between reformulation and interpola-
tion/preservation properties, originating in the work of Nash, Segoufin, and
Vianu, and show how this can be extended to give a very elegant theoretical
framework for studying the reformulation problem. After that we will turn to
performing interpolation and reformulation directly over a physical plan lan-
guage, rather than a query language. This will include a discussion of:
 – how to extend traditional cost-based query optimization to the setting of
   constraint-based reformulation
 – how to “plug in” reasoners, particularly those for expressive decidable logics
   (guarded negation, guarded TGDs), into the reformulation process.
This includes work with Balder ten Cate, Julien Leblay, Efi Tsamoura, and
Michael Vanden Boom.