'Closed over relations'; another possibly-quiz [was: Uniqueness of R00]
Warning: non-algebraicist speaking.
I'm continuing to plug away at the problem of non-uniqueness of R00 (which we want to identify with DUM).
I'm getting counter-examples generated which can't possibly be a whole set of relations. For example like the M3 lattice here.
What do I mean by "a whole set of relations"? If I'm given some relation values, that gives me a set of attribute names, and a set of attribute values for each name. (I'm going to assume that all of the given relations are join-compatible; that is same attribute name gives same attribute type.) Then TTM Pre's say I can construct tuples with any combo of the attribute names paired with their values, and construct relations with any combo of the same-heading tuples.
Furthermore Natural Join is 'closed over relations' so I can take all those possible relations pairwise, and JOIN them to get some other relation in the possible set. Oh, I need to include DEE, DUM, and all the possible empty relations for the combos of attribute names.
The JOINing means I can arrange all these possible relations into a lattice, with the edges showing which JOIN produced which relation as result. Then I'm claiming that the M3 lattice can't represent a full set of relations, there must be some missing.
This exercise is comparable to producing the powerset from some starting elements, then arranging them in a lattice as resulting from Intersections.
I can see how you get the lower half of the diamond: a, b, c are relations with the same heading, each with a single tuple, none of which are joinable. Then lattice bottom '0' is the empty relation with that heading. Lattice top '1' is the relation with the same heading and content the union of the three. But there's possible relations missing: each of the pairwise unions of a, b, c.
Or I can see how to get the top half: lattice top '1' is DEE; a, b, c are relations each with a single attribute, each distinct. But now the bottom half's wrong: there should be each of the pairings of those attributes, as produced by JOIN = Cartesian product.
Or: (this is the quiz) can somebody see a complete set of relations that does have the M3 structure?
Vadim+Marshall's 'Relational Lattice Axioms' paper seems to be suffering the same trouble: Figure 1 doesn't include all possible relation values for the illustrated attribute names and values. So when the section on Distributivity says "It is easy to spot the “pentagon” N5 sublattices on Fig.1. ", that pentagon appears only because some relations are omitted (and/or not all the edges are drawn in).
Quote from AntC on August 16, 2019, 4:53 pmWarning: non-algebraicist speaking.
I'm continuing to plug away at the problem of non-uniqueness of R00 (which we want to identify with DUM).
I'm getting counter-examples generated which can't possibly be a whole set of relations. For example like the M3 lattice here.
What do I mean by "a whole set of relations"? If I'm given some relation values, that gives me a set of attribute names, and a set of attribute values for each name. (I'm going to assume that all of the given relations are join-compatible; that is same attribute name gives same attribute type.) Then TTM Pre's say I can construct tuples with any combo of the attribute names paired with their values, and construct relations with any combo of the same-heading tuples.
Furthermore Natural Join is 'closed over relations' so I can take all those possible relations pairwise, and JOIN them to get some other relation in the possible set. Oh, I need to include DEE, DUM, and all the possible empty relations for the combos of attribute names.
The JOINing means I can arrange all these possible relations into a lattice, with the edges showing which JOIN produced which relation as result. Then I'm claiming that the M3 lattice can't represent a full set of relations, there must be some missing.
This exercise is comparable to producing the powerset from some starting elements, then arranging them in a lattice as resulting from Intersections.
I can see how you get the lower half of the diamond: a, b, c are relations with the same heading, each with a single tuple, none of which are joinable. Then lattice bottom '0' is the empty relation with that heading. Lattice top '1' is the relation with the same heading and content the union of the three. But there's possible relations missing: each of the pairwise unions of a, b, c.
Or I can see how to get the top half: lattice top '1' is DEE; a, b, c are relations each with a single attribute, each distinct. But now the bottom half's wrong: there should be each of the pairings of those attributes, as produced by JOIN = Cartesian product.
Or: (this is the quiz) can somebody see a complete set of relations that does have the M3 structure?
No, M3 is not a relational lattice. (This means that you can't exhibit a database of 5 relations such that those would be joined and unioned exactly as the elements {0,1,a,b,c} of M3. Here is the proof.
First, we have to fix R_{00}. If is easy to see that it can't be lattice top or bottom. Then, it must be either a, b, or c. For all practical purposes those elements are equivalent, so lets assume R_{00}=a. (By "equivalence" I mean that you may replace "a" by "b", and literally have the same arguments).
Then, the lattice elements x in the interval R_{10} \le x \le R_{00} (which is in M3 terms 0 \le x \le a) are the empty relations. Since there are only two such lattice elements, and we know one of them -- R_{00}, then let's just assume that the other relation R_{10} AKA M3 0 has an attribute p.
Both b and c cover element R_{10} AKA M3 0. Therefore, they have the same signature, consisting of single attribute p. Both are nonempty, and their natural join (that is lattice meet) is 0. Without loss of generality those elements can be fixed as relations like these
| p |
| 1 |
and
| p |
| 2 |
The the inner union of these two according the M3 Hasse diagram should be 1 -- the lattice top. But lattice top -- R_{01} -- is the relation with the empty set of attributes (Dee) while inner union produces relation with attribute p.
BTW, M3 lattice example is remarkable because it is toy version of the lattice of linear subspaces of 2-dimensional Hilbert space. Birkhoff and von-Neumann initiated the whole new direction describing logic of quantum mechanics on those lattices... In a word, by establishing that M3 is not relational lattice we see that relational lattices have little in common with quantum lattices. Both are not distributive, but that's about it.
Vadim+Marshall's 'Relational Lattice Axioms' paper seems to be suffering the same trouble: Figure 1 doesn't include all possible relation values for the illustrated attribute names and values. So when the section on Distributivity says "It is easy to spot the “pentagon” N5 sublattices on Fig.1. ", that pentagon appears only because some relations are omitted (and/or not all the edges are drawn in).
Can you please be more concrete, that is point out which relations are missing on the Figure 1? Please keep in mind, that if you allow making complements then, certainly the complement of
| x |
| 1 |
relative to
| x |
| 1 |
| 2 |
is nowhere to be found on Figure 1. However, in bare bone algebra consisting of natural join, inner union, and constant R_{00} there are no more relations that you can add to this picture.
Quote from Vadim on August 17, 2019, 1:18 amQuote from AntC on August 16, 2019, 4:53 pmWarning: non-algebraicist speaking.
I'm continuing to plug away at the problem of non-uniqueness of R00 (which we want to identify with DUM).
I'm getting counter-examples generated which can't possibly be a whole set of relations. For example like the M3 lattice here.
What do I mean by "a whole set of relations"? If I'm given some relation values, that gives me a set of attribute names, and a set of attribute values for each name. (I'm going to assume that all of the given relations are join-compatible; that is same attribute name gives same attribute type.) Then TTM Pre's say I can construct tuples with any combo of the attribute names paired with their values, and construct relations with any combo of the same-heading tuples.
Furthermore Natural Join is 'closed over relations' so I can take all those possible relations pairwise, and JOIN them to get some other relation in the possible set. Oh, I need to include DEE, DUM, and all the possible empty relations for the combos of attribute names.
The JOINing means I can arrange all these possible relations into a lattice, with the edges showing which JOIN produced which relation as result. Then I'm claiming that the M3 lattice can't represent a full set of relations, there must be some missing.
This exercise is comparable to producing the powerset from some starting elements, then arranging them in a lattice as resulting from Intersections.
I can see how you get the lower half of the diamond: a, b, c are relations with the same heading, each with a single tuple, none of which are joinable. Then lattice bottom '0' is the empty relation with that heading. Lattice top '1' is the relation with the same heading and content the union of the three. But there's possible relations missing: each of the pairwise unions of a, b, c.
Or I can see how to get the top half: lattice top '1' is DEE; a, b, c are relations each with a single attribute, each distinct. But now the bottom half's wrong: there should be each of the pairings of those attributes, as produced by JOIN = Cartesian product.
Or: (this is the quiz) can somebody see a complete set of relations that does have the M3 structure?
Reply part 1 of several.
No, M3 is not a relational lattice.
Then why does Mace4 generate models that are M3? Answer: because there's no axioms telling it that's not allowed. So we are backtracking from the non-uniqueness of R00 to the inadequately-defined 'Relational Lattice'? Will adding the Litak axioms prevent Mace4 generating such models?
I'm going to ignore your so-called proof. hand-waving: "it must be" "for all practical purposes" "let's assume" "since there are only two such" [yes in a set of relations as defined in TTM, but you haven't shown you've got that] "let's assume" [again] "both of them are nonempty" [defined how?] I summarise it thusly: starting with something that isn't defined as a set of relations you're claiming to have proved it can't be a set of relations.
... linear subspaces of 2-dimensional Hilbert space. Birkhoff and von-Neumann initiated ... quantum mechanics on those lattices... In a word, by establishing that M3 is not relational lattice ...
You have not established that anything is or is not a relational lattice. So just quit the smoke-blowing. Your definition of a relational lattice seems to be bunkum [see later part-reply]. The more I try to nail down some algebraic approach, the less and less am I finding any substance.
Quote from Vadim on August 17, 2019, 1:18 amQuote from AntC on August 16, 2019, 4:53 pmWarning: non-algebraicist speaking.
I'm continuing to plug away at the problem of non-uniqueness of R00 (which we want to identify with DUM).
..., in bare bone algebra consisting of natural join, inner union, and constant R_{00} there are no more relations that you can add to this picture.
Reply part 2 of several.
Please give a citation for the procedure in Section 2. Example of that paper "Relational lattices can be generated in fairly straightforward way. "
Why do you think it generates a 'Relational lattice'? Why do you think it generates a lattice at all? What it generates is entirely dependent on the (arbitrary) choice of the starting set of relations. For example, suppose your starting set didn't happen to include R00. Then the procedure would never generate any empty relations and in particular would never generate lattice bottom aka R10. For another example, it's only by chance choice there's two distinct relations with each full set of values for the two attributes. Without those, the procedure wouldn't necessarily generate lattice top as R01, nor the 'full' relation (aka R11) with all attributes and all combs of values for those attributes.
So is a lattice without R01, R10, R00 nor R11 a Relational lattice? please give a definition of 'Relational lattice'. The inability to uniquely define R00 seems a small problem compared to an inability to define a lattice with those four.
Note that in the approach I gave, I insisted R01 and R00 appear, along with empty relations for all possible headings (combinations of attribute names).
Addit: I'm asking for a citation because nowhere can I find this procedure indicated. For all of the examples on the wikipedia page, and all the examples in the references/texts linked from it, they assume some set of elements is given then arrange the elements into a lattice by the given ordering. Of course the choice of elements could be completely random, but usually it's some naturally-defined set: Integers, integer pairs, factors of some integer, partitions of a set, powerset of some set, ... Even if there's no 'natural' membership criterion, none of the examples go extending the given set by lattice meet/joining the elements pairwise.
So Section 2. Example is entitled to choose some random set of relations. All it can then do is arrange them according to the ordering induce by NatJOIN as lattice meet. There's no guarantee that gives a lattice (see wikipedia examples of non-lattices). Even if by luck it does form a lattice, that's merely a lattice with elements that are relations. That's not a 'Relational Lattice' as I've understood the term.
As far as I can tell from the Litak et al papers, they are forming the elements of the lattice by taking all possible Attribute-value pairs, generating all possible tuples from them/all possible combos of tuples of same heading into relations. That's what I'd call a 'natural' membership criterion, not a random collection of relations.
Addit2: Yes I'm sure that's what Litak et al are doing. Critical sections from the 2015 paper:
Lemma 2.1. For any D and A, R(D,A) is a lattice.
Along with the definitions leading up to R(D, A) in section 2.1 paragraph 1 and first two sentences of para 2.
Notice they're taking the algebraicists usual simplification of assuming a universal set of values D for all attributes. They assume a given set of attribute names A. Hugh will have to >sigh< when they call an arbitrary subset H of A a header. Usual definition of a relation as consisting of a head-thing and a body, where the body is a subset of all possible tuples having that head-thing.
The collection of all relations over D whose headers are contained in A will be denoted as R(D,A).
"contained in A" means they're taking all possible combos of attribute names; "all relations" means all possible combos of values from D.
I'm happy that definition is consistent with how I've been using 'Relational Lattice'. I'm also happy it rejects with the outcome from the procedure described in Vadim's Section 2. Example: in general that procedure will not produce a Relational Lattice, by Litak et al's definition.
Quote from Vadim on August 17, 2019, 1:18 amQuote from AntC on August 16, 2019, 4:53 pmWarning: non-algebraicist speaking.
Final reply part 3 of 3.
Vadim+Marshall's 'Relational Lattice Axioms' paper seems to be suffering the same trouble: Figure 1 doesn't include all possible relation values for the illustrated attribute names and values. So when the section on Distributivity says "It is easy to spot the “pentagon” N5 sublattices on Fig.1. ", that pentagon appears only because some relations are omitted (and/or not all the edges are drawn in).
Can you please be more concrete, that is point out which relations are missing on the Figure 1? Please keep in mind, that if you allow making complements then, certainly the complement of
x 1 relative to
x 1 2 is nowhere to be found on Figure 1.
Of course relation {(x = 2)} must appear. Yes it happens to be (B MINUS A) from the starting set, but how it got there doesn't matter (there's plenty of other queries with that result). Notice I'm using Codd's MINUS so I'm not doing anything domain-dependent. It must appear because it's the answer to a possible-query. If it doesn't appear, the lattice can't express all possibly query results over your starting set of relations. See 'Relationally complete'.
Similarly all the tuple subsets of relation R11 = B TIMES D must appear, not just the one that forms the two pentagons. They would greatly complicate the central area of Figure 1, such that I'm unsure whether we'd get a pentagon.
Or is the procedure in Section 2. Example your definition of (possible) 'Relational Lattice'? Then there are a very large number of possible 'Relational Lattice's including an attribute-value pair x=2 somewhere (along with all the other A-v pairs from the starting set), with no properties in common -- not even having an element corresponding to DEE nor DUM. I'm not sure they're even bound to be bi-lattices: some might be semi-lattices; some might not even be semi-lattices.
Note: I am not denying that Relational Lattices are in general non-distributive. I am saying that Figure 1 and the procedure in section 2. Example is not evidence.
Quote from AntC on August 18, 2019, 12:56 pmQuote from Vadim on August 17, 2019, 1:18 amNo, M3 is not a relational lattice.
Then why does Mace4 generate models that are M3? Answer: because there's no axioms telling it that's not allowed. So we are backtracking from the non-uniqueness of R00 to the inadequately-defined 'Relational Lattice'? Will adding the Litak axioms prevent Mace4 generating such models?
It will not, but to see that you have to develop some skill of mapping lattice elements to relations. You ask where do those relations appear from; there is nothing in the algebra axioms hinting their structure? That is absolutely right, but misses the point. No matter what set of relations you attempt to map M_3 into, there would always be a problem of doing so. In other words, somewhere on M_3 Hasse diagram you'll get misfit.
BTW, lets use correct term of what we are trying to do there -- it is called lattice representation.
I'm going to ignore your so-called proof. hand-waving: "it must be" "for all practical purposes" "let's assume" "since there are only two such" [yes in a set of relations as defined in TTM, but you haven't shown you've got that] "let's assume" [again] "both of them are nonempty" [defined how?] I summarise it thusly: starting with something that isn't defined as a set of relations you're claiming to have proved it can't be a set of relations.
The central idea of algebraic representation is mapping abstract algebraic elements into the elements of some concrete structure. The mapping is not arbitrary, as algebraic operations in the algebra must fit those defined in the mapped structure.
Quote from AntC on August 18, 2019, 1:49 pmOf course relation
{(x = 2)}must appear. Yes it happens to be(B MINUS A)from the starting set, but how it got there doesn't matter (there's plenty of other queries with that result). Notice I'm using Codd's MINUS so I'm not doing anything domain-dependent. It must appear because it's the answer to a possible-query. If it doesn't appear, the lattice can't express all possibly query results over your starting set of relations. See 'Relationally complete'.
Figure 1 from "Relational Lattice Axioms"
is abbreviated Hasse Diagram from section 3 of
"First Steps in Relational Lattice"
Yes, some elements on Figure 1 of that paper are not labeled with relations, otherwise it would clutter the picture.
Similarly all the tuple subsets of relation
R11 = B TIMES Dmust appear, not just the one that forms the two pentagons. They would greatly complicate the central area of Figure 1, such that I'm unsure whether we'd get a pentagon.
Yes, it is challenging to spot pentagons on Figure 1 of
"First Steps in Relational Lattice"
but let's approach it the other way. Consider the lattice of 6 elements:
R_{00}
R_{01}
| p |
| p |
| 1 |
| p |
| 2 |
| p |
| 1 |
| 2 |
It is complete in terms of classic RA operations (that is you can't query any other relations out of this set), and yet pentagons are pretty easy to spot.
Quote from AntC on August 18, 2019, 1:11 pmPlease give a citation for the procedure in Section 2. Example of that paper "Relational lattices can be generated in fairly straightforward way. "
Why do you think it generates a 'Relational lattice'? Why do you think it generates a lattice at all? What it generates is entirely dependent on the (arbitrary) choice of the starting set of relations. For example, suppose your starting set didn't happen to include R00. Then the procedure would never generate any empty relations and in particular would never generate lattice bottom aka R10. For another example, it's only by chance choice there's two distinct relations with each full set of values for the two attributes. Without those, the procedure wouldn't necessarily generate lattice top as R01, nor the 'full' relation (aka R11) with all attributes and all combs of values for those attributes.
The proper term here is "closure". If you have lattice join and meet operations, and you start with a finite set, then certainly, what you'll generate would be a finite lattice with some top and bottom. Now we are not talking about abstract lattice elements but database relations. So you ask: would the lattice top be a relation with the the empty set of attributes? Likewise, would the lattice bottom be a relation with the empty set of tuples? Not necessarily.
So is a lattice without R01, R10, R00 nor R11 a Relational lattice? please give a definition of 'Relational lattice'. The inability to uniquely define R00 seems a small problem compared to an inability to define a lattice with those four.
As you correctly noticed, we may get a lattice with R01 and R10 with non-empty sets of attributes and tuples, correspondingly. However, all the relations in such database universe would have the attributes of R01. Therefore, you can chop off all such columns from all those relations and you will have a database indistinguishable from the original. Likewise, you can do tuple elimination to make R10 the empty relation.
Note that in the approach I gave, I insisted R01 and R00 appear, along with empty relations for all possible headings (combinations of attribute names).
Addit: I'm asking for a citation because nowhere can I find this procedure indicated. For all of the examples on the wikipedia page, and all the examples in the references/texts linked from it, they assume some set of elements is given then arrange the elements into a lattice by the given ordering. Of course the choice of elements could be completely random, but usually it's some naturally-defined set: Integers, integer pairs, factors of some integer, partitions of a set, powerset of some set, ... Even if there's no 'natural' membership criterion, none of the examples go extending the given set by lattice meet/joining the elements pairwise.
So Section 2. Example is entitled to choose some random set of relations. All it can then do is arrange them according to the ordering induce by NatJOIN as lattice meet. There's no guarantee that gives a lattice (see wikipedia examples of non-lattices). Even if by luck it does form a lattice, that's merely a lattice with elements that are relations. That's not a 'Relational Lattice' as I've understood the term.
This is correct: you can't just take any set of elements and expect it to be closed with respect to some algebraic operations. The term you are looking into is called "subalgebra generated by the set of elements". In the Figure 1 example, we just took some initial set, and amended it with the elements generated via lattice operations.
Quote from Vadim on August 18, 2019, 4:30 pmQuote from AntC on August 18, 2019, 1:11 pmPlease give a citation for the procedure in Section 2. Example of that paper "Relational lattices can be generated in fairly straightforward way. "
Why do you think it generates a 'Relational lattice'? Why do you think it generates a lattice at all? What it generates is entirely dependent on the (arbitrary) choice of the starting set of relations. For example, suppose your starting set didn't happen to include R00. Then the procedure would never generate any empty relations and in particular would never generate lattice bottom aka R10. For another example, it's only by chance choice there's two distinct relations with each full set of values for the two attributes. Without those, the procedure wouldn't necessarily generate lattice top as R01, nor the 'full' relation (aka R11) with all attributes and all combs of values for those attributes.
The proper term here is "closure".
Yes, which is why I titled this thread 'closed over relations'.
If you have lattice join and meet operations, and you start with a finite set, then certainly, what you'll generate would be a finite lattice with some top and bottom. Now we are not talking about abstract lattice elements but database relations. So you ask: would the lattice top be a relation with the the empty set of attributes? Likewise, would the lattice bottom be a relation with the empty set of tuples? Not necessarily.
Then you are incorrect to claim your R01 is DEE or that your R00 is DUM. I have to say I'm experiencing the usual frustration I get with your writings: it takes great deal of hard work to get any idea what you're talking about. When I push and push to get you to clarify, I find that your writings are wrong. See my Addit2 just added to this message you're quoting from.
So is a lattice without R01, R10, R00 nor R11 a Relational lattice? please give a definition of 'Relational lattice'. The inability to uniquely define R00 seems a small problem compared to an inability to define a lattice with those four.
As you correctly noticed, we may get a lattice with R01 and R10 with non-empty sets of attributes and tuples, correspondingly. However, all the relations in such database universe would have the attributes of R01. Therefore, you can chop off all such columns from all those relations and you will have a database indistinguishable from the original. Likewise, you can do tuple elimination to make R10 the empty relation.
Again, you're defining R01 in such a way that it doesn't meet the definition of DEE.
If there's tuples you can "do elimination" on then the relation isn't empty. We want R00 JOIN R11 = R10; but if R10 is not in fact empty, what on earth behaviour do you expect for R00? You're making this far more complicated than it needs to be.
Note that in the approach I gave, I insisted R01 and R00 appear, along with empty relations for all possible headings (combinations of attribute names).
Addit: I'm asking for a citation because nowhere can I find this procedure indicated. For all of the examples on the wikipedia page, and all the examples in the references/texts linked from it, they assume some set of elements is given then arrange the elements into a lattice by the given ordering. Of course the choice of elements could be completely random, but usually it's some naturally-defined set: Integers, integer pairs, factors of some integer, partitions of a set, powerset of some set, ... Even if there's no 'natural' membership criterion, none of the examples go extending the given set by lattice meet/joining the elements pairwise.
So Section 2. Example is entitled to choose some random set of relations. All it can then do is arrange them according to the ordering induce by NatJOIN as lattice meet. There's no guarantee that gives a lattice (see wikipedia examples of non-lattices). Even if by luck it does form a lattice, that's merely a lattice with elements that are relations. That's not a 'Relational Lattice' as I've understood the term.
This is correct: you can't just take any set of elements and expect it to be closed with respect to some algebraic operations. The term you are looking into is called "subalgebra generated by the set of elements". In the Figure 1 example, we just took some initial set, and amended it with the elements generated via lattice operations.
Then my assessment of Section 2. Example and Figure 1 is correct: bunkum. This is not a Relational Lattice and any observations about it are a waste of time.
Quote from Vadim on August 18, 2019, 3:00 pmQuote from AntC on August 18, 2019, 12:56 pmQuote from Vadim on August 17, 2019, 1:18 amNo, M3 is not a relational lattice.
Then why does Mace4 generate models that are M3? Answer: because there's no axioms telling it that's not allowed. So we are backtracking from the non-uniqueness of R00 to the inadequately-defined 'Relational Lattice'? Will adding the Litak axioms prevent Mace4 generating such models?
It will not, but to see that you have to develop some skill of mapping lattice elements to relations. You ask where do those relations appear from; there is nothing in the algebra axioms hinting their structure? That is absolutely right, but misses the point. No matter what set of relations you attempt to map M_3 into, there would always be a problem of doing so. In other words, somewhere on M_3 Hasse diagram you'll get misfit.
OK so we should be able to specify (through axioms) that property of relational lattices that doesn't apply for lattices-in-general. Does it go something like this?
- For any 3 elements that are not only distinct but in no lattice ordering:
- Either we can
NatJOINtwo of them thenNatJOINthat to the third to obtain a greatest lower bound different to theNatJOINof the first two; - Or we can
InnerUniontwo of them thenInnerUnionthat to the third to obtain a least upper bound different to theInnerUnionof the first two; - Or both 2. and 3.
BTW, lets use correct term of what we are trying to do there -- it is called lattice representation.
The central idea of algebraic representation is mapping abstract algebraic elements into the elements of some concrete structure. The mapping is not arbitrary, as algebraic operations in the algebra must fit those defined in the mapped structure.
Without being able to prevent a M_3 structure appearing, the algebraic operations don't fit the mapped structure. So this difficulty is wider than the inability to fix R00.