{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:51:50Z","timestamp":1773939110945,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T00:00:00Z","timestamp":1600819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001509","name":"Royal Society of New Zealand","doi-asserted-by":"publisher","award":["Marsden grant UOA1628"],"award-info":[{"award-number":["Marsden grant UOA1628"]}],"id":[{"id":"10.13039\/501100001509","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["292767 and 308712"],"award-info":[{"award-number":["292767 and 308712"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Team semantics is the mathematical framework of modern logics of dependence and independence in which formulae are interpreted by sets of assignments (teams) instead of single assignments as in first-order logic. In order to deepen the fruitful interplay between team semantics and database dependency theory, we define Polyteam Semantics in which formulae are evaluated over a family of teams. We begin by defining a novel polyteam variant of dependence atoms and give a finite axiomatization for the associated implication problem. We relate polyteam semantics to team semantics and investigate in which cases logics over the former can be simulated by logics over the latter. We also characterize the expressive power of poly-dependence logic by properties of polyteams that are downwards closed and definable in existential second-order logic ($\\textsf{ESO}$). The analogous result is shown to hold for poly-independence logic and all $\\textsf{ESO}$-definable properties. We also relate poly-inclusion logic to greatest fixed point logic.<\/jats:p>","DOI":"10.1093\/logcom\/exaa048","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T11:13:54Z","timestamp":1599822834000},"page":"1541-1566","source":"Crossref","is-referenced-by-count":4,"title":["Polyteam semantics"],"prefix":"10.1093","volume":"30","author":[{"given":"Miika","family":"Hannula","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland"},{"name":"School of Computer Science, University of Auckland, Auckland, New Zealand"}]},{"given":"Juha","family":"Kontinen","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland"}]},{"given":"Jonni","family":"Virtema","sequence":"additional","affiliation":[{"name":"Department of Philosophy and Ethics, Hokkaido University, Sapporo, Japan"},{"name":"Databases & theoretical computer science group, Hasselt University, Hasselt, Belgium"}]}],"member":"286","published-online":{"date-parts":[[2020,9,23]]},"reference":[{"key":"2020120307171945100_ref1","first-page":"580","article-title":"Dependency structures of data base relationships","volume-title":"Proceedings of IFIP World Computer Congress","author":"Armstrong","year":"1974"},{"key":"2020120307171945100_ref2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0022-0000(84)90075-8","article-title":"Inclusion dependencies and their interaction with functional dependencies","volume":"28","author":"Casanova","year":"1984","journal-title":"Journal of Computer and System Sciences"},{"key":"2020120307171945100_ref3","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10472-017-9568-4","article-title":"Approximation and dependence via multiteam semantics","volume":"83","author":"Durand","year":"2018","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2020120307171945100_ref4","first-page":"186","article-title":"Probabilistic team semantics","volume-title":"Foundations of Information and Knowledge Systems\u201410th International Symposium, FoIKS 2018, Budapest, Hungary, May 14\u201318, 2018, Proceedings","author":"Durand","year":"2018"},{"key":"2020120307171945100_ref5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/978-3-319-31803-5_2","article-title":"Expressivity and complexity of dependence logic","volume-title":"Dependence Logic: Theory and Applications","author":"Durand","year":"2016"},{"key":"2020120307171945100_ref6","first-page":"89","article-title":"Data exchange: semantics and query answering","volume-title":"Theoretical Computer Science","author":"Fagin","year":"2005"},{"key":"2020120307171945100_ref7","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.apal.2011.08.005","article-title":"Inclusion and exclusion dependencies in team semantics: on some logics of imperfect information","volume":"163","author":"Galliani","year":"2012","journal-title":"Annals of Pure and Applied Logic"},{"key":"2020120307171945100_ref8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/978-3-319-31803-5_4","article-title":"On strongly first-order dependencies","volume-title":"Dependence Logic, Theory and Applications","author":"Galliani","year":"2016"},{"key":"2020120307171945100_ref9","first-page":"281","article-title":"Inclusion logic and fixed point logic","volume-title":"Computer Science Logic 2013 (CSL 2013)","author":"Galliani","year":"2013"},{"key":"2020120307171945100_ref10","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0890-5401(91)90077-F","article-title":"Axioms and algorithms for inferences involving probabilistic independence","volume":"91","author":"Geiger","year":"1991","journal-title":"Information and Computation"},{"key":"2020120307171945100_ref11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/s11225-013-9479-2","article-title":"Dependence and independence","volume":"101","author":"Gr\u00e4del","year":"2013","journal-title":"Studia Logica"},{"key":"2020120307171945100_ref12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.apal.2014.09.002","article-title":"Axiomatizing first-order consequences in independence logic","volume":"166","author":"Hannula","year":"2015","journal-title":"Annals of Pure and Applied Logic"},{"key":"2020120307171945100_ref13","first-page":"16","article-title":"Reasoning about embedded dependencies using inclusion dependencies","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning\u201420th International Conference, LPAR-20 2015, Suva, Fiji, November 24\u201328, 2015, Proceedings","author":"Hannula","year":"2015"},{"key":"2020120307171945100_ref14","first-page":"304","article-title":"Facets of distribution identities in probabilistic team semantics","volume-title":"JELIA","author":"Hannula","year":"2019"},{"key":"2020120307171945100_ref15","first-page":"121","article-title":"A finite axiomatization of conditional independence and inclusion dependencies","volume-title":"Information and Computation","author":"Hannula","year":"2016"},{"key":"2020120307171945100_ref16","doi-asserted-by":"crossref","first-page":"856","DOI":"10.1016\/j.jcss.2016.02.007","article-title":"On the finite and general implication problems of independence atoms and keys","volume":"82","author":"Hannula","year":"2016","journal-title":"Journal of Computer and System Sciences"},{"key":"2020120307171945100_ref17","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/inco.1995.1148","article-title":"On the undecidability of implications between embedded multivalued database dependencies","volume":"122","author":"Herrmann","year":"1995","journal-title":"Information and Computation"},{"key":"2020120307171945100_ref18","first-page":"539","article-title":"Compositional semantics for a language of imperfect information","volume":"5","author":"Hodges","year":"1997","journal-title":"Journal of the Interest Group in Pure and Applied Logics"},{"key":"2020120307171945100_ref19","first-page":"1073","article-title":"Elements of relational database theory","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B)","author":"Kanellakis","year":"1990"},{"key":"2020120307171945100_ref20","first-page":"60:1","article-title":"Decidability of predicate logics with team semantics","volume-title":"Proceedings of MFCS 2016","author":"Kontinen","year":"2016"},{"key":"2020120307171945100_ref21","first-page":"179","article-title":"Independence in database relations","volume-title":"Proceedings of 20th WoLLIC","author":"Kontinen","year":"2013"},{"key":"2020120307171945100_ref22","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10849-009-9082-0","article-title":"On definability in dependence logic","volume":"3","author":"Kontinen","year":"2009","journal-title":"Journal of Logic, Language and Information"},{"key":"2020120307171945100_ref23","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1016\/j.apal.2013.05.006","article-title":"Axiomatizing first-order consequences in dependence logic","volume":"164","author":"Kontinen","year":"2013","journal-title":"Annals of Pure and Applied Logic"},{"key":"2020120307171945100_ref24","first-page":"149","article-title":"A double team semantics for generalized quantifiers","volume-title":"Journal of Logic, Language and Information","author":"Kuusisto","year":"2015"},{"key":"2020120307171945100_ref25","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/322290.322297","article-title":"Subset dependencies and a completeness result for a subclass of embedded multivalued dependencies","volume":"29","author":"Sagiv","year":"1982","journal-title":"Journal of the ACM"},{"key":"2020120307171945100_ref26","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/582250.582259","article-title":"Inferences involving embedded multivalued dependencies and transitive dependencies","volume-title":"Proceedings of the 1980 ACM SIGMOD International Conference on Management of Data","author":"Parker, Jr","year":"1980"},{"key":"2020120307171945100_ref27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511611193","volume-title":"Dependence Logic","author":"V\u00e4\u00e4n\u00e4nen","year":"2007"},{"key":"2020120307171945100_ref28","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1016\/j.apal.2019.04.010","article-title":"Negation and partial axiomatizations of dependence and independence logic revisited","volume":"170","author":"Yang","year":"2019","journal-title":"Annals of Pure and Applied Logic"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/8\/1541\/34673307\/exaa048.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/8\/1541\/34673307\/exaa048.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T12:20:30Z","timestamp":1606998030000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/30\/8\/1541\/5910069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,23]]},"references-count":28,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,9,23]]},"published-print":{"date-parts":[[2020,12,10]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaa048","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12]]},"published":{"date-parts":[[2020,9,23]]}}}