Classification of annotation semirings over containment of conjunctive queries

Egor V. Kostylev; Juan L. Reutter; András Z. Salamon

doi:10.1145/2556524

Classification of annotation semirings over containment of conjunctive queries

Egor V. Kostylev, Juan L. Reutter, András Z. Salamon

School of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We study the problem of query containment 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 databases 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 develop new decision procedures for containment for some semirings which are not in any of these classes. This generalizes and systematizes previous approaches.

Original language	English
Article number	1
Pages (from-to)	1-39
Number of pages	39
Journal	ACM Transactions on Database Systems
Volume	39
Issue number	1
DOIs	https://doi.org/10.1145/2556524
Publication status	Published - 6 Jan 2014

Keywords

Annotation
Provenance
Query optimization

Access to Document

10.1145/2556524

Kostylev-2014-Classification-of-annotation-semirings-ToDS-AAM
Copyright © 2014 ACM. This work has been made available online in accordance with publisher policies or with permission. Permission for further reuse of this content should be sought from the publisher or the rights holder. This is the author created accepted manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1145/2556524.
Accepted author manuscript, 526 KB

Cite this

@article{eac2266d43f74f42b795c7fe24a73f7a,

title = "Classification of annotation semirings over containment of conjunctive queries",

abstract = "We study the problem of query containment 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 databases 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 develop new decision procedures for containment for some semirings which are not in any of these classes. This generalizes and systematizes previous approaches.",

keywords = "Annotation, Provenance, Query optimization",

author = "Kostylev, {Egor V.} and Reutter, {Juan L.} and Salamon, {Andr{\'a}s Z.}",

note = "Funding: This work is supported under SOCIAM: The Theory and Practice of Social Machines, a project funded by the UK Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/J017728/1. This work was also supported by FET-Open Project FoX, grant agreement 233599; EPSRC grants EP/F028288/1, G049165 and J015377; and the Laboratory for Foundations of Computer Science. ",

year = "2014",

month = jan,

day = "6",

doi = "10.1145/2556524",

language = "English",

volume = "39",

pages = "1--39",

journal = "ACM Transactions on Database Systems",

issn = "0362-5915",

publisher = "ACM",

number = "1",

}

TY - JOUR

T1 - Classification of annotation semirings over containment of conjunctive queries

AU - Kostylev, Egor V.

AU - Reutter, Juan L.

AU - Salamon, András Z.

N1 - Funding: This work is supported under SOCIAM: The Theory and Practice of Social Machines, a project funded by the UK Engineering and Physical Sciences Research Council (EPSRC) under grant number EP/J017728/1. This work was also supported by FET-Open Project FoX, grant agreement 233599; EPSRC grants EP/F028288/1, G049165 and J015377; and the Laboratory for Foundations of Computer Science.

PY - 2014/1/6

Y1 - 2014/1/6

N2 - We study the problem of query containment 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 databases 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 develop new decision procedures for containment for some semirings which are not in any of these classes. This generalizes and systematizes previous approaches.

AB - We study the problem of query containment 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 databases 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 develop new decision procedures for containment for some semirings which are not in any of these classes. This generalizes and systematizes previous approaches.

KW - Annotation

KW - Provenance

KW - Query optimization

U2 - 10.1145/2556524

DO - 10.1145/2556524

M3 - Article

SN - 0362-5915

VL - 39

SP - 1

EP - 39

JO - ACM Transactions on Database Systems

JF - ACM Transactions on Database Systems

IS - 1

M1 - 1

ER -

Classification of annotation semirings over containment of conjunctive queries

Abstract

Keywords

Access to Document

Fingerprint

Cite this