{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T22:05:16Z","timestamp":1779919516322,"version":"3.53.1"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031863189","type":"print"},{"value":"9783031863196","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-86319-6_21","type":"book-chapter","created":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T03:02:21Z","timestamp":1754362941000},"page":"351-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Provenance Analysis and Semiring Semantics for First-Order Logic"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8950-9991","authenticated-orcid":false,"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6847-7274","authenticated-orcid":false,"given":"Val","family":"Tannen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,8]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01182254","volume":"18","author":"K Amer","year":"1984","unstructured":"Amer, K.: Equationally complete classes of commutative monoids with monus. Alg. Universalis 18, 129\u2013131 (1984)","journal-title":"Alg. Universalis"},{"issue":"4","key":"21_CR2","doi-asserted-by":"publisher","first-page":"346","DOI":"10.14778\/2095686.2095693","volume":"5","author":"Y Amsterdamer","year":"2011","unstructured":"Amsterdamer, Y., Davidson, S., Deutch, D., Milo, T., Stoyanovich, J., Tannen, V.: Putting lipstick on pig: enabling database-style workflow provenance. Proc. VLDB 5(4), 346\u2013357 (2011)","journal-title":"Proc. VLDB"},{"key":"21_CR3","unstructured":"Amsterdamer, Y., Deutch, D., Tannen, V.: On the limitations of provenance for queries with difference. In: 3rd Workshop on the Theory and Practice of Provenance, TaPP\u201911 (2011). See also arXiv:1105.2255"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Amsterdamer, Y., Deutch, D., Tannen, V.: Provenance for aggregate queries. In: Principles of Database Systems, PODS, pp. 153\u2013164 (2011). See also arXiv:1101.1110","DOI":"10.1145\/1989284.1989302"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Bertossi, L.: Database repairs and consistent query answering: origins and further developments. In: Principles of Database Systems, PODS 2019, pp. 48\u201358. ACM (2019). Available from: https:\/\/doi.org\/10.1145\/3294052.3322190","DOI":"10.1145\/3294052.3322190"},{"key":"21_CR6","unstructured":"Bizi\u00e8re, C., Gr\u00e4del, E., Naaf, M.: Locality theorems in semiring semantics. In: Proceedings of MFCS 2023 (2023). Full version: arXiv 2303.12627"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Bogaerts, B., Jakubowski, M., Van den Bussche, J.: Postulates for provenance: instance-based provenance for first-order logic. In: Companion of the 43rd Symposium on Principles of Database Systems. PODS (to appear, 2024). https:\/\/doi.org\/10.1145\/3651596","DOI":"10.1145\/3651596"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF01359910","volume":"161","author":"B Bosbach","year":"1965","unstructured":"Bosbach, B.: Komplement\u00e4re Halbgruppen. Math. Ann. 161, 279\u2013295 (1965)","journal-title":"Komplement\u00e4re Halbgruppen. Math. Ann."},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"1862","DOI":"10.24963\/ijcai.2020\/258","volume":"2020","author":"C Bourgaux","year":"2020","unstructured":"Bourgaux, C., Ozaki, A., Pe\u00f1aloza, R., Predoiu, L.: Provenance for the description logic ELHr. In: Proceedings of IJCAI 2020, pp. 1862\u20131869 (2020). https:\/\/doi.org\/10.24963\/ijcai.2020\/258","journal-title":"In: Proceedings of IJCAI"},{"key":"21_CR10","unstructured":"Brinke, S., Gr\u00e4del, E., Mrkonji\u0107, L.: Ehrenfeucht\u2013Fra\u00efss\u00e9 games in semiring semantics. In: Proceedings of CSL 2024 (2024). Full version: arXiv 2308.04910"},{"key":"21_CR11","unstructured":"Brinke, S., Gr\u00e4del, E., Mrkonji\u0107, L., Naaf, M.: Semiring provenance in the infinite. In: Tannen\u2019s Festschrift, vol. 119. Open Access Series in Informatics (2024). Available from: http:\/\/logic.rwth-aachen.de\/pub\/BrinkeGraedelMrkonjicNaaf24.pdf"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Buneman, P., Clemons, E.: Efficiently monitoring relational databases. ACM Trans. Database Syst. 4(3), 368\u2013382 (1979). Available from: https:\/\/doi.org\/10.1145\/320083.320099","DOI":"10.1145\/320083.320099"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Dannert, K., Gr\u00e4del, E.: Provenance analysis: a perspective for description logics? In: Lutz, C., et al. (ed.) Description Logic, Theory Combination, and All That, vol. 11560. Lecture Notes in Computer Science, pp. 266\u2013285. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-22102-7_12","DOI":"10.1007\/978-3-030-22102-7_12"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Dannert, K., Gr\u00e4del, E.: Semiring provenance for guarded logics. In: Hajnal Andr\u00e9ka and Istv\u00e1n N\u00e9meti on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic. Outstanding Contributions to Logic, pp. 53\u201379. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-64187-0_3","DOI":"10.1007\/978-3-030-64187-0_3"},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Dannert, K., Gr\u00e4del, E., Naaf, M., Tannen, V.: Semiring provenance for fixed-point logic. In: Baier, C., Goubault-Larrecq, J. (eds.) 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), vol. 183. Leibniz International Proceedings in Informatics (LIPIcs), pp. 17:1\u201317:22. Dagstuhl (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2021.17","DOI":"10.4230\/LIPIcs.CSL.2021.17"},{"key":"21_CR16","unstructured":"Deutch, D., Milo, T., Roy, S., Tannen, V.: Circuits for datalog provenance. In: Proc. 17th International Conference on Database Theory ICDT, pp. 201\u2013212. OpenProceedings.org (2014). https:\/\/doi.org\/10.5441\/002\/icdt.2014.22"},{"issue":"4","key":"21_CR17","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/s00778-015-0390-5","volume":"24","author":"D Deutch","year":"2015","unstructured":"Deutch, D., Moskovitch, Y., Tannen, V.: Provenance-based analysis of data-centric processes. VLDB J. 24(4), 583\u2013607 (2015)","journal-title":"VLDB J."},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R Fagin","year":"1976","unstructured":"Fagin, R.: Probabilities on finite models. J. Symb. Logic 41, 50\u201358 (1976). https:\/\/doi.org\/10.1017\/S0022481200051756","journal-title":"J. Symb. Logic"},{"key":"21_CR19","first-page":"271","volume":"2008","author":"J Foster","year":"2008","unstructured":"Foster, J., Green, T., Tannen, V.: Annotated XML: queries and provenance. In: Proceedings of PODS 2008, pp. 271\u2013280 (2008). https:\/\/doi.org\/10.1145\/1376916.1376954","journal-title":"In: Proceedings of PODS"},{"issue":"2","key":"21_CR20","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.jal.2009.09.001","volume":"8","author":"F Geerts","year":"2010","unstructured":"Geerts, F., Poggi, A.: On database query languages for K-relations. J. Appl. Logic 8(2), 173\u2013185 (2010). https:\/\/doi.org\/10.1016\/j.jal.2009.09.001","journal-title":"J. Appl. Logic"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Geerts, F., Unger, T., Karvounarakis, G., Fundulaki, I., Christophides, V.: Algebraic structures for capturing the provenance of SPARQL queries. J. ACM 63(1), 7:1\u20137:63 (2016). https:\/\/doi.org\/10.1145\/2810037","DOI":"10.1145\/2810037"},{"issue":"3\u20134","key":"21_CR22","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1561\/1900000068","volume":"9","author":"B Glavic","year":"2021","unstructured":"Glavic, B.: Data provenance. Found. Trends Databases 9(3\u20134), 209\u2013441 (2021). https:\/\/doi.org\/10.1561\/1900000068","journal-title":"Found. Trends Databases"},{"key":"21_CR23","first-page":"17","volume":"2","author":"Y Glebskii","year":"1969","unstructured":"Glebskii, Y., Kogan, D., Liogon\u2019kii, M., Talanov, V.: Range and degree of realizability of formulas in the restricted predicate calculus. Kibernetika 2, 17\u201328 (1969). https:\/\/doi.org\/10.1007\/BF01071084","journal-title":"Kibernetika"},{"key":"21_CR24","doi-asserted-by":"publisher","unstructured":"Gr\u00e4del, E., Mrkonji\u0107, L.: Elementary equivalence versus isomorphism in semiring semantics. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Dagstuhl, vol. 198, pp. 133:1\u2013133:20 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.133","DOI":"10.4230\/LIPIcs.ICALP.2021.133"},{"key":"21_CR25","unstructured":"Gr\u00e4del, E., Tannen, V.: Semiring provenance for first-order model checking. arXiv:1712.01980 [cs.LO] (2017). Available from: https:\/\/arxiv.org\/abs\/1712.01980, arXiv:1712.01980"},{"key":"21_CR26","doi-asserted-by":"publisher","unstructured":"Gr\u00e4del, E., Tannen, V.: Provenance analysis for logic and games. Moscow J. Comb. Number Theory 9(3), 203\u2013228 (2020). Preprint available at https:\/\/arxiv.org\/abs\/1907.08470. https:\/\/doi.org\/10.2140\/moscow.2020.9.203","DOI":"10.2140\/moscow.2020.9.203"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Kolaitis, P.G., Libkin, L., Marx, M., Spencer, J., Vardi, M.Y., Venema, Y., Weinstein, S.: Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer (2007). https:\/\/doi.org\/10.1007\/3-540-68804-8","DOI":"10.1007\/3-540-68804-8"},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., L\u00fccking, N., Naaf, M.: Semiring provenance for B\u00fcchi games: strategy analysis with absorptive polynomials. arXiv:2106.12892 [cs.LO] (2021). Available from: https:\/\/arxiv.org\/abs\/2106.12892","DOI":"10.4204\/EPTCS.346.5"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Helal, H., Naaf, M., Wilke, R.: Zero-one laws and almost sure valuations of first-order logic in semiring semantics. In: Baier, C., Fisman, D. (eds.) LICS \u201922: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science, Haifa, August 2\u20135, 2022, pp. 41:1\u201341:12. ACM (2022) (full version of this paper). Available from: https:\/\/arxiv.org\/abs\/2203.03425, https:\/\/doi.org\/10.1145\/3531130.3533358","DOI":"10.1145\/3531130.3533358"},{"issue":"2","key":"21_CR30","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00224-011-9327-6","volume":"49","author":"T Green","year":"2011","unstructured":"Green, T.: Containment of conjunctive queries on annotated relations. Theory Comput. Syst. 49(2), 429\u2013459 (2011). https:\/\/doi.org\/10.1007\/s00224-011-9327-6","journal-title":"Theory Comput. Syst."},{"key":"21_CR31","unstructured":"Green, T., Karvounarakis, G., Ives, Z., Tannen, V.: Update exchange with mappings and provenance. In: Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, September 23\u201327, 2007, pp. 675\u2013686 (2007)"},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"Green, T., Karvounarakis, G., Tannen, V.: Provenance semirings. In: Principles of Database Systems PODS, pp. 31\u201340. ACM (2007). https:\/\/doi.org\/10.1145\/1265530.1265535","DOI":"10.1145\/1265530.1265535"},{"key":"21_CR33","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s00224-011-9323-x","volume":"49","author":"T Green","year":"2011","unstructured":"Green, T., Ives, Z., Tannen, V.: Reconcilable differences. Theory Comput. Syst. 49, 460\u2013488 (2011). https:\/\/doi.org\/10.1145\/1514894.1514920","journal-title":"Theory Comput. Syst."},{"key":"21_CR34","doi-asserted-by":"crossref","unstructured":"Herschel, M., Hern\u00e1ndez, M.: Explaining missing answers to SPJUA queries. Proc. VLDB Endow. 3(1), 185\u2013196 (2010). Available from: http:\/\/www.vldb.org\/pvldb\/vldb2010\/pvldb_vol3\/R16.pdf, https:\/\/doi.org\/10.14778\/1920841.1920869","DOI":"10.14778\/1920841.1920869"},{"key":"21_CR35","doi-asserted-by":"crossref","unstructured":"Herschel, M., Hern\u00e1ndez, M., Tan, W.: Artemis: a system for analyzing missing answers. Proc. VLDB Endow. 2(2), 1550\u20131553 (2009). Available from: http:\/\/www.vldb.org\/pvldb\/vol2\/vldb09-1004.pdf, https:\/\/doi.org\/10.14778\/1687553.1687588","DOI":"10.14778\/1687553.1687588"},{"issue":"3","key":"21_CR36","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/1462571.1462577","volume":"37","author":"Z Ives","year":"2008","unstructured":"Ives, Z., Green, T., Karvounarakis, G., Taylor, N., Tannen, V., Talukdar, P., Jacob, M., Pereira, F.: The ORCHESTRA collaborative data sharing system. SIGMOD Rec. 37(3), 26\u201332 (2008)","journal-title":"SIGMOD Rec."},{"key":"21_CR37","doi-asserted-by":"crossref","unstructured":"Karvounarakis, G., Ives, Z., Tannen, V.: Querying data provenance. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, June 6\u201310, 2010, pp. 951\u2013962 (2010)","DOI":"10.1145\/1807167.1807269"},{"key":"21_CR38","unstructured":"Meliou, A., Gatterbauer, W., Moore, K., Suciu, D.: WHY so? or WHY no? functional causality for explaining query answers. In: VLDB Workshop on Management of Uncertain Data (MUD 2010), vol. WP10-04. CTIT Workshop Proceedings Series, pp. 3\u201317 (2010)"},{"key":"21_CR39","volume-title":"Elementary Induction on Abstract Structures","author":"Y Moschovakis","year":"1974","unstructured":"Moschovakis, Y.: Elementary Induction on Abstract Structures. North Holland, Amsterdam (1974)"},{"key":"21_CR40","doi-asserted-by":"crossref","unstructured":"Naaf, M.: Computing least and greatest fixed points in absorptive semirings. arXiv:2106.00399 [cs.LO] (2021). Available from: https:\/\/arxiv.org\/abs\/2106.00399","DOI":"10.1007\/978-3-030-88701-8_21"},{"key":"21_CR41","doi-asserted-by":"crossref","unstructured":"Tannen, V.: Provenance propagation in complex queries. In: In Search of Elegance in the Theory and Practice of Computation - Essays Dedicated to Peter Buneman, pp. 483\u2013493 (2013). https:\/\/doi.org\/10.1007\/978-3-642-41660-6_26","DOI":"10.1007\/978-3-642-41660-6_26"},{"issue":"1","key":"21_CR42","first-page":"39","volume":"41","author":"J Xu","year":"2018","unstructured":"Xu, J., Zhang, W., Alawini, A., Tannen, V.: Provenance analysis for missing answers and integrity repairs. IEEE Data Eng. Bull. 41(1), 39\u201350 (2018). Available from: http:\/\/sites.computer.org\/debull\/A18mar\/p39.pdf","journal-title":"IEEE Data Eng. Bull."}],"container-title":["Trends in Mathematics","Model Theory, Computer Science, and Graph Polynomials"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-86319-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T21:29:14Z","timestamp":1779917354000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-86319-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031863189","9783031863196"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-86319-6_21","relation":{},"ISSN":["2297-0215","2297-024X"],"issn-type":[{"value":"2297-0215","type":"print"},{"value":"2297-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"8 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}