Classification of Annotation Semirings over Containment of Conjunctive Queries

Simple item page
dc.contributor.authorKostylev, Egor V.
dc.contributor.authorReutter, Juan L.
dc.contributor.authorSalamon, Andraz Z.
dc.date.accessioned2025-01-23T21:48:54Z
dc.date.available2025-01-23T21:48:54Z
dc.date.issued2014
dc.description.abstractWe 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.
dc.description.abstractWe 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.
dc.fuente.origenWOS
dc.identifier.doi10.1145/2556524
dc.identifier.eissn1557-4644
dc.identifier.issn0362-5915
dc.identifier.urihttps://doi.org/10.1145/2556524
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/101766
dc.identifier.wosidWOS:000331124300001
dc.issue.numero1
dc.language.isoen
dc.revistaAcm transactions on database systems
dc.rightsacceso restringido
dc.subjectDesign
dc.subjectAlgorithms
dc.subjectTheory
dc.subjectAnnotation
dc.subjectprovenance
dc.subjectquery optimization
dc.titleClassification of Annotation Semirings over Containment of Conjunctive Queries
dc.typeartículo
dc.volumen39
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas