The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Questions about New Relational Algebra A

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Dispensing with UNION

We can combine natural language predicates with OR as well as AND. Thus, there is a ternary relation corresponding to the triadic predicate “Employee E works in department D or employee E works on project J.” If employee EX works in department DX, then <EX,DX,j> is a tuple in the body of this relation for all possible projects j, regardless of whether employee EX actually works on project j (and regardless of whether there is even a project j in the company at this time).

Likewise, if employee EX works on project JX, then <EX,d,JX> is a tuple in the body of this relation for all possible departments d, regardless of whether employee EX actually works in department d (and regardless of whether there is even a department d in the company at this time).

Are 'j' and 'd' scalars? What value does ‘j’ have in a tuple in the body of the relation when there are no projects? Or, would there be no tuples in the body of the relation for a nonexistent project?

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Let s be r1 ◄OR► r2. It is required that if <A,T1> ∈ Hr1 and <A,T2> ∈ Hr2, then T1 = T2.

           Hs = Hr1 union Hr2

           Bs = { ts : exists tr1 exists tr2 ( ( tr1 ∈ Br1 or tr2 ∈ Br2 ) and ts = tr1 union tr2 ) }

The ◄OR► operator is relational disjunction, being a generalization of what in previous literature has been referred to as union (in the special case where the given relations r1 and r2 have the same heading, the result s is in fact the union of those two relations in the traditional sense). The heading of s is the union of the headings of r1 and r2. The body of s contains every tuple that conforms to the heading of s and is a superset of either some tuple in the body of r1 or some tuple in the body of r2. We remark that the ◄OR► operator might logically be called the disjoin.

 

Given an example of relation R1 with heading {A,B} and R2 wih heading {C,D} where the body of R1 is these two tuples:

                 { {A1,B1} , {A2, B2} }

and the body of R2 is these 3 tuples

                 { {C1,D1} , {C2,D2}, {C3, D3} }

What would the body of the result set of R1 ◄OR► R2 look like? What would be the cardinality of the result? What would be the values of the tuples in the body?  I don’t understand how the tuple union operation will work. Since there is no requirement for R1 and R2 to have the same header how would the tuple matching be applied.? Given a tuple tr1 to which tuple tr2 would the tuple union apply? Every tr2 ? 

Quote from Greg Klisch on February 24, 2020, 3:04 am

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Let s be r1 ◄OR► r2. It is required that if <A,T1> ∈ Hr1 and <A,T2> ∈ Hr2, then T1 = T2.

           Hs = Hr1 union Hr2

           Bs = { ts : exists tr1 exists tr2 ( ( tr1 ∈ Br1 or tr2 ∈ Br2 ) and ts = tr1 union tr2 ) }

The ◄OR► operator is relational disjunction, being a generalization of what in previous literature has been referred to as union (in the special case where the given relations r1 and r2 have the same heading, the result s is in fact the union of those two relations in the traditional sense). The heading of s is the union of the headings of r1 and r2. The body of s contains every tuple that conforms to the heading of s and is a superset of either some tuple in the body of r1 or some tuple in the body of r2. We remark that the ◄OR► operator might logically be called the disjoin.

 

Given an example of relation R1 with heading {A,B} and R2 wih heading {C,D} where the body of R1 is these two tuples:

                 { {A1,B1} , {A2, B2} }

and the body of R2 is these 3 tuples

                 { {C1,D1} , {C2,D2}, {C3, D3} }

What would the body of the result set of R1 ◄OR► R2 look like? What would be the cardinality of the result? What would be the values of the tuples in the body?  I don’t understand how the tuple union operation will work. Since there is no requirement for R1 and R2 to have the same header how would the tuple matching be applied.? Given a tuple tr1 to which tuple tr2 would the tuple union apply? Every tr2 ? 

Consider a tuple (following your own syntax) {A7,B7,C1,D1} and just apply the definition Bs={...}.  Does that tuple satisfy the condition or not ?  Repeat same exercise for a hypothetical tuple {A1,B1,C7,D7}.  Does that one satisfy the condition or not ?

Next exercise : I now rewrite the condition "tr1 ∈ Br1 or tr2 ∈ Br2" to "(tr1 ∈ Br1 and tr2 ∈ Ur2) or (tr2 ∈ Br2 and tr1 ∈ Ur1)".  In there Urx are the "universal" relations of their respective types (the ones that contain all possible tuples of their types).  Does that actually alter the condition or are those conditions provably equivalent ?

Next exercise : is the rewritten condition then equivalent to the algebraic expression (R1 JOIN UR2) UNION (R2 JOIN UR1) ?

(Bonus question : what might be the reason the typical DBMS won't provide an operator such as ◄OR► ?)

Quote from Greg Klisch on February 23, 2020, 11:43 pm

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Dispensing with UNION

We can combine natural language predicates with OR as well as AND. Thus, there is a ternary relation corresponding to the triadic predicate “Employee E works in department D or employee E works on project J.” If employee EX works in department DX, then <EX,DX,j> is a tuple in the body of this relation for all possible projects j, regardless of whether employee EX actually works on project j (and regardless of whether there is even a project j in the company at this time).

Likewise, if employee EX works on project JX, then <EX,d,JX> is a tuple in the body of this relation for all possible departments d, regardless of whether employee EX actually works in department d (and regardless of whether there is even a department d in the company at this time).

Are 'j' and 'd' scalars? What value does ‘j’ have in a tuple in the body of the relation when there are no projects? Or, would there be no tuples in the body of the relation for a nonexistent project?

IIRC in DTATRM projects and departments are letterdigit codes. So in this case, yes 'j' and 'd' are scalars. In general with <OR> they aren't necessarily so.

The wording "all possible projects" is woolly. It means 'all possible project codes'; that is, all possible letterdigit codes meeting the constraint for the type of projects. [My italics in both cases there.]

Your "when there are no projects" presumably expects there to be some relvar holding current/actual/authorised/being worked on projects "in the company at this time". <OR> ignores any referential integrity constraints, and looks just at the attribute's type.

Because <OR> looks at the type, not the content (it can't because there's no attribute project in the Department relvar), it suffers being 'domain dependent'; something Codd was at pains to avoid with his 1972 operators -- that's why that algebra requires 'union-compatible' operands. That restriction might be worse than the disease. YMMV

Quote from Greg Klisch on February 24, 2020, 3:04 am

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Let s be r1 ◄OR► r2. It is required that if <A,T1> ∈ Hr1 and <A,T2> ∈ Hr2, then T1 = T2.

           Hs = Hr1 union Hr2

           Bs = { ts : exists tr1 exists tr2 ( ( tr1 ∈ Br1 or tr2 ∈ Br2 ) and ts = tr1 union tr2 ) }

The ◄OR► operator is relational disjunction, being a generalization of what in previous literature has been referred to as union (in the special case where the given relations r1 and r2 have the same heading, the result s is in fact the union of those two relations in the traditional sense). The heading of s is the union of the headings of r1 and r2. The body of s contains every tuple that conforms to the heading of s and is a superset of either some tuple in the body of r1 or some tuple in the body of r2. We remark that the ◄OR► operator might logically be called the disjoin.

 

Given an example of relation R1 with heading {A,B} and R2 wih heading {C,D} where the body of R1 is these two tuples:

                 { {A1,B1} , {A2, B2} }

and the body of R2 is these 3 tuples

                 { {C1,D1} , {C2,D2}, {C3, D3} }

What would the body of the result set of R1 ◄OR► R2 look like? What would be the cardinality of the result? What would be the values of the tuples in the body?  I don’t understand how the tuple union operation will work. Since there is no requirement for R1 and R2 to have the same header how would the tuple matching be applied.? Given a tuple tr1 to which tuple tr2 would the tuple union apply? Every tr2 ? 

[previous wrong answer deleted]

For the three cases where the common attributes are (none, some, all):

  • ◄AND►looks like (cross join, natural join, set intersection)
  • ◄OR►looks like (**, ***, set union)

The 4 named cases are familiar, and equivalences are given in App-A. The two others do not obviously correspond to common relational operators. In case *** I would expect the common attributes to include values equivalent to a union of R1 and R2, combined with non-common values from both, which would lead to a kind of cross join on steroids. Then ** is a just a cross join.

But I confess, I too would like to hear it from the experts.

Andl - A New Database Language - andl.org
Quote from dandl on February 24, 2020, 10:24 am
Quote from Greg Klisch on February 24, 2020, 3:04 am

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Let s be r1 ◄OR► r2. It is required that if <A,T1> ∈ Hr1 and <A,T2> ∈ Hr2, then T1 = T2.

           Hs = Hr1 union Hr2

           Bs = { ts : exists tr1 exists tr2 ( ( tr1 ∈ Br1 or tr2 ∈ Br2 ) and ts = tr1 union tr2 ) }

The ◄OR► operator is relational disjunction, being a generalization of what in previous literature has been referred to as union (in the special case where the given relations r1 and r2 have the same heading, the result s is in fact the union of those two relations in the traditional sense). The heading of s is the union of the headings of r1 and r2. The body of s contains every tuple that conforms to the heading of s and is a superset of either some tuple in the body of r1 or some tuple in the body of r2. We remark that the ◄OR► operator might logically be called the disjoin.

 

Given an example of relation R1 with heading {A,B} and R2 wih heading {C,D} where the body of R1 is these two tuples:

                 { {A1,B1} , {A2, B2} }

and the body of R2 is these 3 tuples

                 { {C1,D1} , {C2,D2}, {C3, D3} }

What would the body of the result set of R1 ◄OR► R2 look like? What would be the cardinality of the result? What would be the values of the tuples in the body?  I don’t understand how the tuple union operation will work. Since there is no requirement for R1 and R2 to have the same header how would the tuple matching be applied.? Given a tuple tr1 to which tuple tr2 would the tuple union apply? Every tr2 ? 

The answer looks a lot like JOIN.

No.

With disjoint headings this is roughly equivalent to a cross product.

No.

The cardinality is 6.

No. We can't compute the cardinality without knowing the cardinality of the attribute types (which Greg doesn't give). There's an "or" in here: "( tr1 ∈ Br1 or tr2 ∈ Br2 )"

Every tuple conforms to the heading {A,B,C,D}.

Yes. The heading of the result is the union of the headings of the operands " Hs = Hr1 union Hr2". That much is like JOIN/<AND>.

Quote from dandl on February 24, 2020, 10:24 am
Quote from Greg Klisch on February 24, 2020, 3:04 am

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Let s be r1 ◄OR► r2. It is required that if <A,T1> ∈ Hr1 and <A,T2> ∈ Hr2, then T1 = T2.

           Hs = Hr1 union Hr2

           Bs = { ts : exists tr1 exists tr2 ( ( tr1 ∈ Br1 or tr2 ∈ Br2 ) and ts = tr1 union tr2 ) }

The ◄OR► operator is relational disjunction, being a generalization of what in previous literature has been referred to as union (in the special case where the given relations r1 and r2 have the same heading, the result s is in fact the union of those two relations in the traditional sense). The heading of s is the union of the headings of r1 and r2. The body of s contains every tuple that conforms to the heading of s and is a superset of either some tuple in the body of r1 or some tuple in the body of r2. We remark that the ◄OR► operator might logically be called the disjoin.

 

Given an example of relation R1 with heading {A,B} and R2 wih heading {C,D} where the body of R1 is these two tuples:

                 { {A1,B1} , {A2, B2} }

and the body of R2 is these 3 tuples

                 { {C1,D1} , {C2,D2}, {C3, D3} }

What would the body of the result set of R1 ◄OR► R2 look like? What would be the cardinality of the result? What would be the values of the tuples in the body?  I don’t understand how the tuple union operation will work. Since there is no requirement for R1 and R2 to have the same header how would the tuple matching be applied.? Given a tuple tr1 to which tuple tr2 would the tuple union apply? Every tr2 ? 

The answer looks a lot like JOIN. With disjoint headings this is roughly equivalent to a cross product. The cardinality is 6. Every tuple conforms to the heading {A,B,C,D}.

May I politely suggest you do the very same 4 exercises I gave in my answer ?  And then reconsider what you've written here ?

Quote from dandl on February 24, 2020, 10:24 am
Quote from Greg Klisch on February 24, 2020, 3:04 am

Quoting from “Appendix A : A New Relational Algebra” in DTATRM:

Let s be r1 ◄OR► r2. It is required that if <A,T1> ∈ Hr1 and <A,T2> ∈ Hr2, then T1 = T2.

           Hs = Hr1 union Hr2

           Bs = { ts : exists tr1 exists tr2 ( ( tr1 ∈ Br1 or tr2 ∈ Br2 ) and ts = tr1 union tr2 ) }

The ◄OR► operator is relational disjunction, being a generalization of what in previous literature has been referred to as union (in the special case where the given relations r1 and r2 have the same heading, the result s is in fact the union of those two relations in the traditional sense). The heading of s is the union of the headings of r1 and r2. The body of s contains every tuple that conforms to the heading of s and is a superset of either some tuple in the body of r1 or some tuple in the body of r2. We remark that the ◄OR► operator might logically be called the disjoin.

 

Given an example of relation R1 with heading {A,B} and R2 wih heading {C,D} where the body of R1 is these two tuples:

                 { {A1,B1} , {A2, B2} }

and the body of R2 is these 3 tuples

                 { {C1,D1} , {C2,D2}, {C3, D3} }

What would the body of the result set of R1 ◄OR► R2 look like? What would be the cardinality of the result? What would be the values of the tuples in the body?  I don’t understand how the tuple union operation will work. Since there is no requirement for R1 and R2 to have the same header how would the tuple matching be applied.? Given a tuple tr1 to which tuple tr2 would the tuple union apply? Every tr2 ? 

[previous wrong answer deleted]

For the three cases where the common attributes are (none, some, all):

  • ◄AND►looks like (cross join, natural join, set intersection)

which 'looks like' (natural join, natural join, natural join).

  • ◄OR►looks like (**, ***, set union)

The 4 named cases are familiar, and equivalences are given in App-A. The two others do not obviously correspond to common relational operators. In case *** I would expect the common attributes to include values equivalent to a union of R1 and R2, combined with non-common values from both, which would lead to a kind of cross join on steroids. Then ** is a just a cross join.

In the case where the operands have no attributes in common, <OR> is the Cartesian product of the tuples in R1 times all values in the types of the attributes in R2, unioned with the Cartesian product of the tuples in R2 times all values in the types of the attributes in R1. I think it's downright confusing to call that any sort of "join".

But I confess, I too would like to hear it from the experts.

Appendix A is written by experts. Just read and apply the setbuilder rules.

But I confess, I too would like to hear it from the experts.

Appendix A is written by experts. Just read and apply the setbuilder rules.

“The definition of genius is taking the complex and making it simple.”

"If you can't explain it simply, you don't understand it well enough."

I think Albert was onto something. On the evidence, you are neither a genius nor do you understand it well enough. Maybe someone else can assist?

Andl - A New Database Language - andl.org

I am confused by the use of predicate logic operators as relational operators.  The predicate operators have Boolean values as operands as demonstrated by a truth table.  The relational operators have relvars (sets of tuples) as operands.  In what sense do relvar values have Boolean values of TRUE and FALSE? I believe only two relvar values have been defined as having BOOLEAN values:  TABLE_DEE and TABLE_DUM.  I obviously have failed to recognize the truth.