Questions about some relational operator definitions and comments about the DIVIDEBY operation
Quote from dandl on February 25, 2020, 3:04 amQuote from Greg Klisch on February 24, 2020, 12:37 amCan someone provide a definition of relational division (or a reference to such a definition); such that. the definition that follow consists of (a) a formal specification of the rules, if any, that apply to the operands of the operator in question, (b) a formal specification of the heading of the result of that operator, and (c) a formal specification of the body of that result, followed by (d) an informal discussion of the formal specifications.
Unlike other relational operators, the relational division is not formally defined in DTATRM,
Codd 1972 provides a formal definition, both in isolation and in terms of other operations.
DTATRM and DBE provide operational definitions, in terms of equivalent code using other operations. To me this says it all.
r1 DIVIDEBY r2 ::= r1 { X } MINUS ( ( r1 { X } JOIN r2 ) MINUS r1 ) { X }
Thank you.
CODD’S DIVIDE USING IMAGE RELATIONS
I’m investigating the use of the Image Relation Operator, as defined in chapter 14 of "Database Explorations", to implement Codd’s Divide. I’m using the same example database of Suppliers under contract (relvar S), Parts (relvar P), and Parts supplied by Suppliers (relvar SP) as defined in DTATRM. The query to be implemented is “Get suppliers who supply all parts”.
In this regard: is it allowable to partition a set with itself as in the following?
SP {S#} WHERE ( ‼SP ) { P# } = P { P# }
or, would it be necessary to first create a new set from the PROJECTion separately as in the following?
WITH ( SP {S#} ) AS SPP:
SPP WHERE (!!SP) {P#} = P {P#} ;
Quote from Greg Klisch on March 24, 2020, 5:55 pmCODD’S DIVIDE USING IMAGE RELATIONS
I’m investigating the use of the Image Relation Operator, as defined in chapter 14 of "Database Explorations", to implement Codd’s Divide. I’m using the same example database of Suppliers under contract (relvar S), Parts (relvar P), and Parts supplied by Suppliers (relvar SP) as defined in DTATRM. The query to be implemented is “Get suppliers who supply all parts”.
In this regard: is it allowable to partition a set with itself as in the following?
SP {S#} WHERE (
SP ) { P# } = P { P# }
I don't see why not. It works in Rel:
| S# S# |
|---|
| S#("S1") |
Quote from Dave Voorhis on March 24, 2020, 6:14 pmQuote from Greg Klisch on March 24, 2020, 5:55 pmCODD’S DIVIDE USING IMAGE RELATIONS
I’m investigating the use of the Image Relation Operator, as defined in chapter 14 of "Database Explorations", to implement Codd’s Divide. I’m using the same example database of Suppliers under contract (relvar S), Parts (relvar P), and Parts supplied by Suppliers (relvar SP) as defined in DTATRM. The query to be implemented is “Get suppliers who supply all parts”.
In this regard: is it allowable to partition a set with itself as in the following?
SP {S#} WHERE (
I don't see why not. It works in Rel:
SP {S#} WHERE (‼SP) {P#} = P {P#}
S#
S#S#("S1")
Thank you for that Dave.
Then would this query: "Get suppliers who supply all purple parts” be correct? I Apply the RESTRICT for purple parts to both SP and P? That is, to both relvars containing parts.
WITH ( P WHERE COLOR = COLOR('Purple') ) AS PP ,
( SP JOIN PP) AS SPP :
SPP {S#} WHERE ( ‼SPP ) { P# } = PP { P# } ;
If I coded this correctly, I would expect to get an empty set. If you see an error in the code, please let me know.
Quote from Greg Klisch on March 24, 2020, 6:25 pmQuote from Dave Voorhis on March 24, 2020, 6:14 pmQuote from Greg Klisch on March 24, 2020, 5:55 pmCODD’S DIVIDE USING IMAGE RELATIONS
I’m investigating the use of the Image Relation Operator, as defined in chapter 14 of "Database Explorations", to implement Codd’s Divide. I’m using the same example database of Suppliers under contract (relvar S), Parts (relvar P), and Parts supplied by Suppliers (relvar SP) as defined in DTATRM. The query to be implemented is “Get suppliers who supply all parts”.
In this regard: is it allowable to partition a set with itself as in the following?
SP {S#} WHERE (
I don't see why not. It works in Rel:
SP {S#} WHERE (‼SP) {P#} = P {P#}
S#
S#S#("S1") Thank you for that Dave.
Then would this query: "Get suppliers who supply all purple parts” be correct? I Apply the RESTRICT for purple parts to both SP and P? That is, to both relvars containing parts.
WITH ( P WHERE COLOR = COLOR('Purple') ) AS PP ,
( SP JOIN PP) AS SPP :
SPP {S#} WHERE ( ‼SPP ) { P# } = PP { P# } ;If I coded this correctly, I would expect to get an empty set. If you see an error in the code, please let me know.
The syntax needs an update for a later Tutorial D revision, but it indeed returns no tuples:
| S# S# |
|---|
Quote from Greg Klisch on March 24, 2020, 6:25 pmQuote from Dave Voorhis on March 24, 2020, 6:14 pmQuote from Greg Klisch on March 24, 2020, 5:55 pmCODD’S DIVIDE USING IMAGE RELATIONS
I’m investigating the use of the Image Relation Operator, as defined in chapter 14 of "Database Explorations", to implement Codd’s Divide. I’m using the same example database of Suppliers under contract (relvar S), Parts (relvar P), and Parts supplied by Suppliers (relvar SP) as defined in DTATRM. The query to be implemented is “Get suppliers who supply all parts”.
In this regard: is it allowable to partition a set with itself as in the following?
SP {S#} WHERE (
I don't see why not. It works in Rel:
SP {S#} WHERE (‼SP) {P#} = P {P#}
S#
S#S#("S1") Thank you for that Dave.
Then would this query: "Get suppliers who supply all purple parts” be correct? I Apply the RESTRICT for purple parts to both SP and P? That is, to both relvars containing parts.
WITH ( P WHERE COLOR = COLOR('Purple') ) AS PP ,
( SP JOIN PP) AS SPP :
SPP {S#} WHERE ( ‼SPP ) { P# } = PP { P# } ;If I coded this correctly, I would expect to get an empty set. If you see an error in the code, please let me know.
Greg,
The result can't be anything but empty :
PP is defined as a restriction of something that happens to be empty (given the usual sample value of the suppliers-and-parts database) and therefore itself necessarily empty
SPP is defined as a JOIN of something with PP therefore with an empty relation therefore SPP itself empty
and the final result a projection of a restriction of that empty SPP relation - hope you see why that must necessarily be empty too.
If you find an implementation that does not produce an empty relation here you have reason for doing either of :
submitting a bug ticket
not even bothering to do that and just dismiss the implementation at hand as hopelessly flawed with no reasonable perspective of ever getting sufficiently fixed
Quote from DTATRM:
But this expression misses suppliers who supply no parts at all—even though (logically
speaking) such a supplier does supply every purple part, because, as is well known, “FORALL x
(exp)” always evaluates to TRUE if there are no x’s, regardless of what the boolean expression exp
happens to be. By contrast, the following expression (which involves a Small Divide) is guaranteed
to give the right answer in all cases:
I assume Greg's question is leading towards one about the 'right answer'? DTATRM does not supply that 'right answer', but I presume it is intended to include S5.
Quote from Erwin on March 24, 2020, 11:08 pmQuote from Greg Klisch on March 24, 2020, 6:25 pmQuote from Dave Voorhis on March 24, 2020, 6:14 pmQuote from Greg Klisch on March 24, 2020, 5:55 pmCODD’S DIVIDE USING IMAGE RELATIONS
I’m investigating the use of the Image Relation Operator, as defined in chapter 14 of "Database Explorations", to implement Codd’s Divide. I’m using the same example database of Suppliers under contract (relvar S), Parts (relvar P), and Parts supplied by Suppliers (relvar SP) as defined in DTATRM. The query to be implemented is “Get suppliers who supply all parts”.
In this regard: is it allowable to partition a set with itself as in the following?
SP {S#} WHERE (
I don't see why not. It works in Rel:
SP {S#} WHERE (‼SP) {P#} = P {P#}
S#
S#S#("S1") Thank you for that Dave.
Then would this query: "Get suppliers who supply all purple parts” be correct? I Apply the RESTRICT for purple parts to both SP and P? That is, to both relvars containing parts.
WITH ( P WHERE COLOR = COLOR('Purple') ) AS PP ,
( SP JOIN PP) AS SPP :
SPP {S#} WHERE ( ‼SPP ) { P# } = PP { P# } ;If I coded this correctly, I would expect to get an empty set. If you see an error in the code, please let me know.
Greg,
The result can't be anything but empty :
PP is defined as a restriction of something that happens to be empty (given the usual sample value of the suppliers-and-parts database) and therefore itself necessarily empty
SPP is defined as a JOIN of something with PP therefore with an empty relation therefore SPP itself empty
and the final result a projection of a restriction of that empty SPP relation - hope you see why that must necessarily be empty too.
If you find an implementation that does not produce an empty relation here you have reason for doing either of :
submitting a bug ticket
not even bothering to do that and just dismiss the implementation at hand as hopelessly flawed with no reasonable perspective of ever getting sufficiently fixed
Dandl, you correctly anticipate where I was leading. Regarding the FORALL x(exp): Both the Small Divide and Codd's divide satisfy the quantifier. Codd's divide satisifies it with the suppliers who supply parts (IE. per the predicate: the suppliers in relation SP). The Small Divide satisfies it with the suppliers in relation S. I am not saying that one is more 'right' than the other. The problem with supplier S5 is not that is was left out of the FORALL but that it was inconsistent: i.e., either all suppliers should be suppliers of 'purple' parts or none should be. There shouldn't be some but not others. The choice made for the Small Divide was "all suppliers" and to implement that choice they had to introduce a third relation (S) to the division. If they had chosen otherwise then they could have omitted relation S from the implementation. This implementation represents the 'no suppliers' choice.
Erwin,
First, I want to say that I was unsure that I had correctly coded the implementation. Dave kindly corrected the syntax for me.
I would very much like to hear an explanation as to what is flawed with the implementation: I am still very much a neophyte in the subject matter. I certainly could have flaws in my logic.
However, this implementation seems to entail directly from the premises of relation SP (given below), is in agreement with the CWA and gives a correct answer for every part even when there are no parts. Of course the projections lead to a series of empty sets. But that was exactly the method Date and Darwen used to make their point about the Small Divide and how it handles the case when there are no 'purple' parts. They added a third relation to the division specifically to support their choice that all suppliers supply non-existent parts. The point of this implementation is that it is not a necessary condition to introduce a third relation to do the division because one can choose that no suppliers supply non-existent parts without violating the premises and without violating the CWA.
The premises are:
a) If a supplier s supplies a part p then there will be a tuple {s,p,..} in relation SP. This premise follows directly from the predicate for SP.
b) If there is not a tuple for {s,p,...} in relation SP then supplier s does not supply that part p. This follows from the predicate for SP as well as from the CWA.
c) There is is a tuple for {s,p,..} if and only if supplier s supplies part p. This follows from a) and b).
It follows from c) that if s supplies a purple part p then there would be a tuple {s,p,...} in SP for that pair of attributes. There is not such a pair.
Quote from Greg Klisch on March 25, 2020, 7:33 pmThe premises are:
a) If a supplier s supplies a part p then there will be a tuple {s,p,..} in relation SP. This premise follows directly from the predicate for SP.
b) If there is not a tuple for {s,p,...} in relation SP then supplier s does not supply that part p. This follows from the predicate for SP as well as from the CWA.
c) There is is a tuple for {s,p,..} if and only if supplier s supplies part p. This follows from a) and b).
It follows from c) that if s supplies a purple part p then there would be a tuple {s,p,...} in SP for that pair of attributes. There is not such a pair.
Logic error.
Mathematical convention says that FORALL x : P(x) ===== NOT EXISTS x : NOT P(x)
The consequence is that if `NOT EXISTS <some hypothetical purple part>` is true in and of itself, then surely any further restriction ("such that <some given supplier> does _NOT_ supply that purple part") of that empty set will be empty too, so it will have no members, so the `NOT EXISTS` is indeed true, and for the tautology expressed in the equation above, it means that the FORALL must be true.
Get it out of your head that stating a universal quantification _presumes_ the very existence of at least one `x` in the first place. It does not.
Not so long ago I was pointed to a paper "the traditional square of opposition". It explains the views that have been held about this issue throughout the centuries ever since Aristofocles (sorry), and the key phrase to remember from that doc went something like "If you ***want*** to make that presumption of the very existence of at least one `x` [as a precondition for your universal quantification to be true], then the device of logic per se can ***easily*** express this by saying FORALL x : P(x) ===== NOT EXISTS x : NOT P(x) *** & EXISTS x ***. It's not a problem of logic per se.". It's a problem of being precise about expressing what your presumptions are. (And the derived ensuing problem is one of the lengths of the resulting logical formulae and possibility of the "& EXISTS x" part leading to combinatorial explosion of cases if we find we have to apply laws of distributivity of logical AND and OR.)
Quote from Erwin on March 25, 2020, 10:09 pmQuote from Greg Klisch on March 25, 2020, 7:33 pmThe premises are:
a) If a supplier s supplies a part p then there will be a tuple {s,p,..} in relation SP. This premise follows directly from the predicate for SP.
b) If there is not a tuple for {s,p,...} in relation SP then supplier s does not supply that part p. This follows from the predicate for SP as well as from the CWA.
c) There is is a tuple for {s,p,..} if and only if supplier s supplies part p. This follows from a) and b).
It follows from c) that if s supplies a purple part p then there would be a tuple {s,p,...} in SP for that pair of attributes. There is not such a pair.
Logic error.
Mathematical convention says that FORALL x : P(x) ===== NOT EXISTS x : NOT P(x)
The consequence is that if `NOT EXISTS <some hypothetical purple part>` is true in and of itself, then surely any further restriction ("such that <some given supplier> does _NOT_ supply that purple part") of that empty set will be empty too, so it will have no members, so the `NOT EXISTS` is indeed true, and for the tautology expressed in the equation above, it means that the FORALL must be true.
Get it out of your head that stating a universal quantification _presumes_ the very existence of at least one `x` in the first place. It does not.
Not so long ago I was pointed to a paper "the traditional square of opposition". It explains the views that have been held about this issue throughout the centuries ever since Aristofocles (sorry), and the key phrase to remember from that doc went something like "If you ***want*** to make that presumption of the very existence of at least one `x` [as a precondition for your universal quantification to be true], then the device of logic per se can ***easily*** express this by saying FORALL x : P(x) ===== NOT EXISTS x : NOT P(x) *** & EXISTS x ***. It's not a problem of logic per se.". It's a problem of being precise about expressing what your presumptions are. (And the derived ensuing problem is one of the lengths of the resulting logical formulae and possibility of the "& EXISTS x" part leading to combinatorial explosion of cases if we find we have to apply laws of distributivity of logical AND and OR.)
I'm not sure what I said to make you think that I was presuming that universal qualification required at least one 'x'. I don't think that. What I was awkwardly attempting to say was that all of the suppliers in SP (after the RESTRICT operation left no suppliers) actually supplied all of the P(x) which, of course, was empty.