Containment in Annotation Semi-rings

Egor Kostylev (Edinburgh)

Info

We study the problem of query containment of (unions of) conjunctive

queries over annotated databases. Annotations are typically attached

to tuples and represent metadata such as probability, multiplicity,

comments, or provenance. It is usually assumed that annotations

are drawn from a commutative semiring.

Such data\-bases pose new challenges in query optimization, since many related fundamental tasks,

such as query containment, have to be reconsidered in the presence of propagation of annotations.

We axiomatize several classes of semirings for each of which

containment of conjunctive queries is equivalent to existence

of a particular type of homomorphism. For each of these types we

also specify all semirings for which existence of a corresponding

homomorphism is a sufficient (or necessary) condition for the

containment. We exploit these techniques to develop new decision

procedures for containment of unions of conjunctive queries and

axiomatize corresponding classes of semirings. This generalizes

previous approaches and allows us to improve known complexity bounds.

Related series

Information Systems Seminar