Our seminar series is free and available for anyone to attend. Unless otherwise stated, seminars take place on Wednesday afternoons at 2pm in the Kilburn Building during teaching season.

If you wish to propose a seminar speaker please contact Antoniu Pop.


Queries determined by views: pack your views

  • Speaker:   Dr  Maarten Marx  (Universiteit van Amsterdam)
  • Host:   Uli Sattler
  • 14th February 2007 at 14:15 in 1.5
A query Q is determined by a set of views V if, whenever V(I1)=V(I2) for two database instances I1, I2 then also Q(I1)=Q(I2). Does this imply that Q can be rewritten as a query Q' that only uses the views V?

For first-order (FO) queries and view definitions over possibly infinite databases, the answer is yes, as follows from old results of Beth and Craig. We say that FO is complete for FO-to-FO rewritings. However, Nash, Segoufin and Vianu (2007) prove that if the query and the view definitions are given by conjunctive queries, then it might not be possible to formulate Q' as a conjunctive query. In other words, CQ is not complete for CQ-to-CQ rewritings.

Here we consider queries and view definitions in the packed fragment (PF) of first-order logic. This is a generalization of the guarded fragment, a fragment of particular interest to database theory. Gottlob 2002 show that the guarded conjunctive queries are exactly the acyclic queries. Leinders 2005 characterize the entire guarded fragment as the semijoin algebra.

We show that both for finite and unrestricted databases, PF is complete for PF-to-PF rewritings. The same holds for packed (unions of) conjunctive queries. In both cases, we provide algorithms for testing whether a query is determined by a set of views, and for actually rewriting Q to Q'. To compare: these problems are undecidable for full FO, and still open for conjunctive queries.
▲ Up to the top