Computing Universal Models Under Linear TGDs
Andre Hernich (Humboldt-Universität zu Berlin, Germany)
Info
|
Date |
15th November 2011 (week , Trinity Term 2011) |
|
Time |
11:30 |
|
Place |
147 |
Abstract
A universal model of a database D and a set S of integrity
constraints is a database that extends D, satis es , and is
most general in the sense that it contains sound and complete
information. Universal models have applications like
answering conjunctive queries, or deciding containment of
conjunctive queries, with respect to databases with integrity
constraints. In general, it is undecidable whether a database
possesses a universal model, but in the past few years researchers
identi ed various settings where this problem is
decidable, and even e ciently solvable.
This talk focuses on computing finite universal models under
nite sets of linear TGDs, non-conflicting keys, and negative constraints.
Such constraints generalize inclusion dependencies,
and were recently shown to be expressive enough to
capture two members of the DL-Lite family of description
logics. The main result is an algorithm that, given a database
without null values and a fi nite set of such constraints,
decides whether there is a finite universal model, and if so, outputs
such a model. If S is fi xed, the algorithm runs in polynomial
time. The algorithm can be extended to cope with databases
containing nulls.
Further info
|
Related series |
|
