{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:16:41Z","timestamp":1787386601464,"version":"build-2736575974"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/F028288\/1, G049165, and J015377"],"award-info":[{"award-number":["EP\/F028288\/1, G049165, and J015377"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/J017728\/1"],"award-info":[{"award-number":["EP\/J017728\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SOCIAM: The Theory and Practice of Social Machines"},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["233599"],"award-info":[{"award-number":["233599"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Laboratory for Foundations of Computer Science"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/2556524","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Classification of annotation semirings over containment of conjunctive queries"],"prefix":"10.1145","volume":"39","author":[{"given":"Egor V.","family":"Kostylev","sequence":"first","affiliation":[{"name":"University of Edinburgh"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan L.","family":"Reutter","sequence":"additional","affiliation":[{"name":"University of Edinburgh and Pontificia Universidad Cat\u00f3lica de Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e1s Z.","family":"Salamon","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.02.017"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376918"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656274"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2nd International Workshop on the Role of Semantic Web in Provenance Management (SWPM'10)","author":"Buneman Peter","unstructured":"Peter Buneman and Egor V. Kostylev . 2010. Annotation algebras for RDFS . In Proceedings of the 2nd International Workshop on the Role of Semantic Web in Provenance Management (SWPM'10) . http:\/\/ceur-ws.org\/Vol-670\/paper_4.pdf Peter Buneman and Egor V. Kostylev. 2010. Annotation algebras for RDFS. In Proceedings of the 2nd International Workshop on the Role of Semantic Web in Provenance Management (SWPM'10). http:\/\/ceur-ws.org\/Vol-670\/paper_4.pdf"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153856"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274604"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656573"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219093"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357777"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497511"},{"key":"e_1_2_1_14_1","unstructured":"Samuel Eilenberg. 1974. Automata Languages and Machines. Pure and Applied Mathematics Vol. A. Academic Press New York NY.   Samuel Eilenberg. 1974. Automata Languages and Machines. Pure and Applied Mathematics Vol. A. Academic Press New York NY."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/239041.239045"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645502.656105"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9323-x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9327-6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142363"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Workshop on Optimization and Operations Research. Lecture Notes in Economics and Mathematical Systems, R. Henn, B. Korte, and W. Oettli (Eds.)","volume":"157","author":"Kannan R.","unstructured":"R. Kannan and C. L. Monma . 1978. On the computational complexity of integer programming problems . In Proceedings of the Workshop on Optimization and Operations Research. Lecture Notes in Economics and Mathematical Systems, R. Henn, B. Korte, and W. Oettli (Eds.) , Vol. 157 . Springer-Verlag, Berlin, 161--172. R. Kannan and C. L. Monma. 1978. On the computational complexity of integer programming problems. In Proceedings of the Workshop on Optimization and Operations Research. Lecture Notes in Economics and Mathematical Systems, R. Henn, B. Korte, and W. Oettli (Eds.), Vol. 157. Springer-Verlag, Berlin, 161--172."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380776.2380778"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42273"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213590"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28685"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00129-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2011.08.006"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2556524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:05Z","timestamp":1750234205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2556524"],"URL":"https:\/\/doi.org\/10.1145\/2556524","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}