On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds
Forssell, Henrik
Kharlamov, Evgeny
Thorstensen, Evgenij
Data 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. 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*.
 Let's talk about semantics of incomplete databases, in particular on equivalents and cores for incomplete databases in open and closed worlds. Our paper is quite theoretical and I'll focus on the theoretical aspects here to try to give you the gist of it and the time available. We'll fix some terminology first. Fix a database schema. Fix sets of constants and labeled nulls. Then an incomplete instance, or just instance from now on, is an instance that can contain both constants and labeled nulls, whereas a complete instance can only contain constants. An annotated instance is an instance in which every occurrence of a constant or null is annotated as open or closed. In this example, the constant a is annotated as closed here and open here. A semantics for incomplete databases is a function which assigns a non-empty set of complete instances to every instance a. We say that a represents the set of complete instances. We say that a implies b if the set that a represents is included in the set that b represents. We say that they're equivalent if they represent the same set. Forming equivalence classes of semantically equivalent instances, we can say that the minimization problem is find a function which picks a smallest in some suitable sense representative from each semantic equivalence class. We'll briefly recall some semantics of incomplete databases. Under OWA, open world assumption, an instance a represents all complete instances to which a has a homomorphism. A implies b if there is a homomorphism from b to a. These are database homomorphisms, so they fix the constants. And a is equivalent to b if there are database homomorphisms going back and forth. Semantic minimization for OWA is solved quite elegantly and we'll return to that in a few slides. Under CWA, closed world assumption, an instance a represents all complete instances i which are images of a. So there's a database homomorphism from a to i such that all atoms of i are in the image or hit. The semantic minimization here is trivial as two instances are equivalent if and only if they're isomorphic. The closed power set semantics, PCWA, has an instance a representing all complete instances i which are unions of images of a. That is to say such that every atom of i is in the image of some homomorphism from a. We say that there's a homomorphic cover from a to i. That is a set of homomorphisms which are jointly surjective on the atoms of i. A implies b if there is such a homomorphic cover from b to a. Then a is semantically equivalent to an instance b if they mutually cover each other. And so semantic minimization here we can take to be the question of how to find a b that is as small as possible while still mutually covering with a. We highlight this as it is one of the focal points of our work and I'll also focus on it in this presentation. Finally, the OCWA, open and closed world assumption, has a represent here a is an annotated instance. As we saw an example of earlier, it has a represent the complete instances such that first there's a homomorphism from a to i and second for all atoms in i there is an atom in the image of this homomorphism which it agrees with on all positions annotated as closed. So to give an example, a here represents i because first there's a homomorphism, the inclusion and second this atom agrees with this one on the position annotated as closed. OCWA subsumes OWA by annotating everything is open and subsumes CWA by annotating everything is closed, but it does not subsume PCWA. We propose a new semantics called here OCWA star. This is a more expressive semantics it subsumes both PCWA and OCWA and thus it allows semantic comparison between instances under PCWA on one hand and OCWA on the other. It also uses annotated instances, but the semantics is defined in terms of homomorphic covers as in PCWA. This facilitates characterization and study of semantic implication and equivalence. It's defined as follows annotation first. The OCWA star uses annotation where only nulls are annotated as open or closed. Constants are not annotated and the same null has the same annotation in all occurrences in the instance. If you have such an instance A, then it represents the closed instances i such that there is a homomorphic cover from A to I with the added condition that all homomorphisms in that cover agree on the nulls that are annotated as closed. Such a cover we refer to as an RCN cover from A to I. As mentioned OCWA star subsumes both PCWA and OCWA. If all nulls are open then OCWA is the same as PCWA. For OCWA star is the same as PCWA. For OCWA we have a translation which gives you for every OCWA annotated instance an OCWA star annotated instance which it is semantically equivalent to. They represent the same sets of closed instances. We have multiple equivalent characterizations of semantic implication in OCWA star. Here we show you the following. By this we mean the open null disjoint union which is formed by taking A, taking a copy of A, renaming the open nulls, only the open nulls, and then taking the union. So A implies B if there exists an RCA cover from B to this open null disjoint union of A with itself such that at least one of the homomorphisms in the cover factors through the first copy. It's only the first copy. We come now to the minimization problem in PCWA that we highlighted before. We recall first the situation in OWA. There any instance has at least semantically equivalent sub-instance known as the core. Two instances, A and B, are semantically equivalent if and only if they have the same core. Moreover, cores are easily characterized. C is a core if and only if any homomorphism from C to C must be an isomorphism. This neat situation does not carry over to PCWA, however. We have counter examples that show that an instance can have multiple minimal semantically equivalent sub-instances. This is also the case for other notions of smallness in particular, image and reflective sub-instance. I'll come back to sub-instance, reflective sub-instance on the next slide. However, there is a weaker notion of core for PCWA as follows. Say that an instance is a PCWA core if any homomorphic cover from A to A contains an isomorphism. Such PCWA core has the property that if A is a PCWA core and A is equivalent to B, then A must be a reflective sub-instance of B, meaning that there are database homomorphisms, one from A to B, and one going back from B to A such that when you compose them, there are the identity on A. Now an instance doesn't have to be equivalent to PCWA core, but it is equivalent to a set of them in the following sense. There is a function which assigns a set of PCWA cores to an instance A. We call that set the multicore of A. It has the properties that first every member of the multicore of A is a reflective sub-instance of A. Next AMB are semantically equivalent if they have the same multicore. And finally, the null disjoint union of the PCWA cores in the multicores, that union is equivalent to A. Now the structure of this multicore gives information about the equivalence class of A, and we show you the following too. First if it's a singleton, then the equivalence class is the least element, that is the member of the multicore, the single member. More generally, minimal elements of the equivalence class must be images of the union of the elements in the multicore, so that the multicore gives you a bound of how many minimal elements there are and a way to find them. We extend this analysis in these results also to OCWA star, but unfortunately there's no time to go into the details there. We summarize. So we have a new semantics OCWA star which properly extends PCWA and OCWA. We have characterization and analysis of somatic implications and equivalence for PCWA, OCWA and OCWA star. Negative results regarding the existence of unique minimal instances in PCWA and OCWA star. We have this new concept of PCWA core and in terms of it, we have a new canonical representative function for PCWA and OCWA star. Thank you.
 Let's talk about semantics of incomplete databases, in particular on equivalents and cores for  incomplete databases in open and closed worlds.  Our paper is quite theoretical and I'll focus on the theoretical aspects here to try to  give you the gist of it and the time available.  We'll fix some terminology first.  Fix a database schema.  Fix sets of constants and labeled nulls.  Then an incomplete instance, or just instance from now on, is an instance that can contain  both constants and labeled nulls, whereas a complete instance can only contain constants.  An annotated instance is an instance in which every occurrence of a constant or null is annotated  as open or closed.  In this example, the constant a is annotated as closed here and open here.  A semantics for incomplete databases is a function which assigns a non-empty set of complete  instances to every instance a.  We say that a represents the set of complete instances.  We say that a implies b if the set that a represents is included in the set that b represents.  We say that they're equivalent if they represent the same set.  Forming equivalence classes of semantically equivalent instances, we can say that the  minimization problem is find a function which picks a smallest in some suitable sense representative  from each semantic equivalence class.  We'll briefly recall some semantics of incomplete databases.  Under OWA, open world assumption, an instance a represents all complete instances to which  a has a homomorphism.  A implies b if there is a homomorphism from b to a.  These are database homomorphisms, so they fix the constants.  And a is equivalent to b if there are database homomorphisms going back and forth.  Semantic minimization for OWA is solved quite elegantly and we'll return to that in a few  slides.  Under CWA, closed world assumption, an instance a represents all complete instances i which  are images of a.  So there's a database homomorphism from a to i such that all atoms of i are in the image  or hit.  The semantic minimization here is trivial as two instances are equivalent if and only  if they're isomorphic.  The closed power set semantics, PCWA, has an instance a representing all complete instances  i which are unions of images of a.  That is to say such that every atom of i is in the image of some homomorphism from a.  We say that there's a homomorphic cover from a to i.  That is a set of homomorphisms which are jointly surjective on the atoms of i.  A implies b if there is such a homomorphic cover from b to a.  Then a is semantically equivalent to an instance b if they mutually cover each other.  And so semantic minimization here we can take to be the question of how to find a b that  is as small as possible while still mutually covering with a.  We highlight this as it is one of the focal points of our work and I'll also focus on  it in this presentation.  Finally, the OCWA, open and closed world assumption, has a represent here a is an annotated instance.  As we saw an example of earlier, it has a represent the complete instances such that  first there's a homomorphism from a to i and second for all atoms in i there is an atom  in the image of this homomorphism which it agrees with on all positions annotated as  closed.  So to give an example, a here represents i because first there's a homomorphism, the  inclusion and second this atom agrees with this one on the position annotated as closed.  OCWA subsumes OWA by annotating everything is open and subsumes CWA by annotating everything  is closed, but it does not subsume PCWA.  We propose a new semantics called here OCWA star.  This is a more expressive semantics it subsumes both PCWA and OCWA and thus it allows semantic  comparison between instances under PCWA on one hand and OCWA on the other.  It also uses annotated instances, but the semantics is defined in terms of homomorphic  covers as in PCWA.  This facilitates characterization and study of semantic implication and equivalence.  It's defined as follows annotation first.  The OCWA star uses annotation where only nulls are annotated as open or closed.  Constants are not annotated and the same null has the same annotation in all occurrences  in the instance.  If you have such an instance A, then it represents the closed instances i such that there is  a homomorphic cover from A to I with the added condition that all homomorphisms in that cover  agree on the nulls that are annotated as closed.  Such a cover we refer to as an RCN cover from A to I.  As mentioned OCWA star subsumes both PCWA and OCWA.  If all nulls are open then OCWA is the same as PCWA.  For OCWA star is the same as PCWA.  For OCWA we have a translation which gives you for every OCWA annotated instance an OCWA  star annotated instance which it is semantically equivalent to.  They represent the same sets of closed instances.  We have multiple equivalent characterizations of semantic implication in OCWA star.  Here we show you the following.  By this we mean the open null disjoint union which is formed by taking A, taking a copy  of A, renaming the open nulls, only the open nulls, and then taking the union.  So A implies B if there exists an RCA cover from B to this open null disjoint union of  A with itself such that at least one of the homomorphisms in the cover factors through  the first copy.  It's only the first copy.  We come now to the minimization problem in PCWA that we highlighted before.  We recall first the situation in OWA.  There any instance has at least semantically equivalent sub-instance known as the core.  Two instances, A and B, are semantically equivalent if and only if they have the same core.  Moreover, cores are easily characterized.  C is a core if and only if any homomorphism from C to C must be an isomorphism.  This neat situation does not carry over to PCWA, however.  We have counter examples that show that an instance can have multiple minimal semantically  equivalent sub-instances.  This is also the case for other notions of smallness in particular, image and reflective  sub-instance.  I'll come back to sub-instance, reflective sub-instance on the next slide.  However, there is a weaker notion of core for PCWA as follows.  Say that an instance is a PCWA core if any homomorphic cover from A to A contains an isomorphism.  Such PCWA core has the property that if A is a PCWA core and A is equivalent to B, then  A must be a reflective sub-instance of B, meaning that there are database homomorphisms,  one from A to B, and one going back from B to A such that when you compose them, there  are the identity on A.  Now an instance doesn't have to be equivalent to PCWA core, but it is equivalent to a set  of them in the following sense.  There is a function which assigns a set of PCWA cores to an instance A. We call that  set the multicore of A. It has the properties that first every member of the multicore of  A is a reflective sub-instance of A.  Next AMB are semantically equivalent if they have the same multicore.  And finally, the null disjoint union of the PCWA cores in the multicores, that union is  equivalent to A. Now the structure of this multicore gives information about the equivalence  class of A, and we show you the following too.  First if it's a singleton, then the equivalence class is the least element, that is the member  of the multicore, the single member.  More generally, minimal elements of the equivalence class must be images of the union of the elements  in the multicore, so that the multicore gives you a bound of how many minimal elements there  are and a way to find them.  We extend this analysis in these results also to OCWA star, but unfortunately there's no  time to go into the details there.  We summarize.  So we have a new semantics OCWA star which properly extends PCWA and OCWA.  We have characterization and analysis of somatic implications and equivalence for PCWA, OCWA  and OCWA star.  Negative results regarding the existence of unique minimal instances in PCWA and OCWA  star.  We have this new concept of PCWA core and in terms of it, we have a new canonical representative  function for PCWA and OCWA star.  Thank you.
ForssellKharlamovThorstensen_0_635.png ForssellKharlamovThorstensen_636_1535.png ForssellKharlamovThorstensen_1536_2363.png ForssellKharlamovThorstensen_2364_2687.png ForssellKharlamovThorstensen_2688_4439.png ForssellKharlamovThorstensen_4440_5783.png ForssellKharlamovThorstensen_5784_5963.png ForssellKharlamovThorstensen_5964_7367.png ForssellKharlamovThorstensen_7368_7691.png ForssellKharlamovThorstensen_7692_8135.png ForssellKharlamovThorstensen_8136_9635.png ForssellKharlamovThorstensen_9636_11651.png ForssellKharlamovThorstensen_11652_13271.png ForssellKharlamovThorstensen_13272_14339.png ForssellKharlamovThorstensen_14340_16715.png ForssellKharlamovThorstensen_16716_17792.png
Let's talk about semantics of incomplete databases, in particular on equivalents and cores for incomplete databases in open and closed worlds. Our paper is quite theoretical and I'll focus on the theoretical aspects here to try to give you the gist of it and the time available. We'll fix some terminology first. Fix a database schema. Fix sets of constants and labeled nulls. Then an incomplete instance, or just instance from now on, is an instance that can contain both constants and labeled nulls, whereas a complete instance can only contain constants. An annotated instance is an instance in which every occurrence of a constant or null is annotated as open or closed. In this example, the constant a is annotated as closed here and open here. A semantics for incomplete databases is a function which assigns a non-empty set of complete instances to every instance a. We say that a represents the set of complete instances. We say that a implies b if the set that a represents is included in the set that b represents. We say that they're equivalent if they represent the same set. Forming equivalence classes of semantically equivalent instances, we can say that the minimization problem is find a function which picks a smallest in some suitable sense representative from each semantic equivalence class. We'll briefly recall some semantics of incomplete databases. Under OWA, open world assumption, an instance a represents all complete instances to which a has a homomorphism. A implies b if there is a homomorphism from b to a. These are database homomorphisms, so they fix the constants. And a is equivalent to b if there are database homomorphisms going back and forth. Semantic minimization for OWA is solved quite elegantly and we'll return to that in a few slides. Under CWA, closed world assumption, an instance a represents all complete instances i which are images of a. So there's a database homomorphism from a to i such that all atoms of i are in the image or hit. The semantic minimization here is trivial as two instances are equivalent if and only if they're isomorphic. The closed power set semantics, PCWA, has an instance a representing all complete instances i which are unions of images of a. That is to say such that every atom of i is in the image of some homomorphism from a. We say that there's a homomorphic cover from a to i. That is a set of homomorphisms which are jointly surjective on the atoms of i. A implies b if there is such a homomorphic cover from b to a. Then a is semantically equivalent to an instance b if they mutually cover each other. And so semantic minimization here we can take to be the question of how to find a b that is as small as possible while still mutually covering with a. We highlight this as it is one of the focal points of our work and I'll also focus on it in this presentation. Finally, the OCWA, open and closed world assumption, has a represent here a is an annotated instance. As we saw an example of earlier, it has a represent the complete instances such that first there's a homomorphism from a to i and second for all atoms in i there is an atom in the image of this homomorphism which it agrees with on all positions annotated as closed. So to give an example, a here represents i because first there's a homomorphism, the inclusion and second this atom agrees with this one on the position annotated as closed. OCWA subsumes OWA by annotating everything is open and subsumes CWA by annotating everything is closed, but it does not subsume PCWA. We propose a new semantics called here OCWA star. This is a more expressive semantics it subsumes both PCWA and OCWA and thus it allows semantic comparison between instances under PCWA on one hand and OCWA on the other. It also uses annotated instances, but the semantics is defined in terms of homomorphic covers as in PCWA. This facilitates characterization and study of semantic implication and equivalence. It's defined as follows annotation first. The OCWA star uses annotation where only nulls are annotated as open or closed. Constants are not annotated and the same null has the same annotation in all occurrences in the instance. If you have such an instance A, then it represents the closed instances i such that there is a homomorphic cover from A to I with the added condition that all homomorphisms in that cover agree on the nulls that are annotated as closed. Such a cover we refer to as an RCN cover from A to I. As mentioned OCWA star subsumes both PCWA and OCWA. If all nulls are open then OCWA is the same as PCWA. For OCWA star is the same as PCWA. For OCWA we have a translation which gives you for every OCWA annotated instance an OCWA star annotated instance which it is semantically equivalent to. They represent the same sets of closed instances. We have multiple equivalent characterizations of semantic implication in OCWA star. Here we show you the following. By this we mean the open null disjoint union which is formed by taking A, taking a copy of A, renaming the open nulls, only the open nulls, and then taking the union. So A implies B if there exists an RCA cover from B to this open null disjoint union of A with itself such that at least one of the homomorphisms in the cover factors through the first copy. It's only the first copy. We come now to the minimization problem in PCWA that we highlighted before. We recall first the situation in OWA. There any instance has at least semantically equivalent sub-instance known as the core. Two instances, A and B, are semantically equivalent if and only if they have the same core. Moreover, cores are easily characterized. C is a core if and only if any homomorphism from C to C must be an isomorphism. This neat situation does not carry over to PCWA, however. We have counter examples that show that an instance can have multiple minimal semantically equivalent sub-instances. This is also the case for other notions of smallness in particular, image and reflective sub-instance. I'll come back to sub-instance, reflective sub-instance on the next slide. However, there is a weaker notion of core for PCWA as follows. Say that an instance is a PCWA core if any homomorphic cover from A to A contains an isomorphism. Such PCWA core has the property that if A is a PCWA core and A is equivalent to B, then A must be a reflective sub-instance of B, meaning that there are database homomorphisms, one from A to B, and one going back from B to A such that when you compose them, there are the identity on A. Now an instance doesn't have to be equivalent to PCWA core, but it is equivalent to a set of them in the following sense. There is a function which assigns a set of PCWA cores to an instance A. We call that set the multicore of A. It has the properties that first every member of the multicore of A is a reflective sub-instance of A. Next AMB are semantically equivalent if they have the same multicore. And finally, the null disjoint union of the PCWA cores in the multicores, that union is equivalent to A. Now the structure of this multicore gives information about the equivalence class of A, and we show you the following too. First if it's a singleton, then the equivalence class is the least element, that is the member of the multicore, the single member. More generally, minimal elements of the equivalence class must be images of the union of the elements in the multicore, so that the multicore gives you a bound of how many minimal elements there are and a way to find them. We extend this analysis in these results also to OCWA star, but unfortunately there's no time to go into the details there. We summarize. So we have a new semantics OCWA star which properly extends PCWA and OCWA. We have characterization and analysis of somatic implications and equivalence for PCWA, OCWA and OCWA star. Negative results regarding the existence of unique minimal instances in PCWA and OCWA star. We have this new concept of PCWA core and in terms of it, we have a new canonical representative function for PCWA and OCWA star. Thank you.
Let's talk about semantics of incomplete closed. In this example, the constant a is semantics for incomplete databases is a function that the minimization problem is find a function incomplete databases. Under OWA, open world minimization here is trivial as two instances are a representing all complete instances i which are PCWA. We propose a new semantics called here OCWA star. This is a more expressive semantics it subsumes both PCWA and OCWA and thus it allows in terms of homomorphic covers as in PCWA. This facilitates characterization and study of semantic implication and equivalence. It's annotated as open or closed. Constants are not the closed instances i such that there is a agree on the nulls that are annotated as closed. same as PCWA. For OCWA star is the same as PCWA. to the minimization problem in PCWA that we counter examples that show that an instance can notions of smallness in particular, image and slide. However, there is a weaker notion of core core, but it is equivalent to a set of them in Next AMB are semantically equivalent if they have extend this analysis in these results also to unique minimal instances in PCWA and OCWA star.