Show simple item record

dc.contributor.authorForssell, Henrik
dc.contributor.authorKharlamov, Evgeny
dc.contributor.authorThorstensen, Evgenij
dc.date.accessioned2021-02-23T12:58:08Z
dc.date.available2021-02-23T12:58:08Z
dc.date.created2020-08-07T11:35:05Z
dc.date.issued2020
dc.identifier.citationForssell, H., Kharlamov, E. & Thorstensen, E. (2020). On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds. I C. Lutz & J. C. Jung (Red.), 23rd International Conference on Database Theory (ICDT 2020) (Bd. 155).en_US
dc.identifier.isbn978-3-95977-139-9
dc.identifier.issn1868-8969
dc.identifier.urihttps://hdl.handle.net/11250/2729835
dc.description.abstractData exchange heavily relies on the notion of incomplete database instances. Several semantics for such instances have been proposed and include open (OWA), closed (CWA), and open-closed (OCWA) world. For all these semantics important questions are: whether one incomplete instance semantically implies another; when two are semantically equivalent; and whether a smaller or smallest semantically equivalent instance exists. For OWA and CWA these questions are fully answered. For several variants of OCWA, however, they remain open. In this work we adress these questions for Closed Powerset semantics and the OCWA semantics of [24]. We define a new OCWA semantics, called OCWA*, in terms of homomorphic covers that subsumes both semantics, and characterize semantic implication and equivalence in terms of such covers. This characterization yields a guess-and-check algorithm to decide equivalence, and shows that the problem is NP-complete. For the minimization problem we show that for several common notions of minimality there is in general no unique minimal equivalent instance for Closed Powerset semantics, and consequently not for the more expressive OCWA* either. However, for Closed Powerset semantics we show that one can find, for any incomplete database, a unique finite set of its subinstances which are subinstances (up to renaming of nulls) of all instances semantically equivalent to the original incomplete one. We study properties of this set, and extend the analysis to OCWA*.en_US
dc.language.isoengen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.no*
dc.titleOn equivalence and cores for incomplete databases in open and closed worldsen_US
dc.typeChapteren_US
dc.description.versionpublishedVersionen_US
dc.rights.holder© Henrik Forssell, Evgeny Kharlamov, and Evgenij Thorstensen.en_US
dc.source.pagenumber10:1-10:21en_US
dc.source.volume155en_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.identifier.doiHttps://doi.org/10.4230/LIPIcs.ICDT.2020.10
dc.identifier.cristin1822166
dc.relation.projectNorges forskningsråd: 237898en_US
dc.relation.projectNorges forskningsråd: 230525en_US
dc.source.articlenumber10en_US
cristin.ispublishedtrue
cristin.fulltextoriginal
cristin.qualitycode1


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal