## The Forum for Discussion about The Third Manifesto and Related Matters

Forum breadcrumbs - You are here:
You need to log in to create posts and topics.

# Generalising Codd's operators; and a quiz

Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

It's an interesting question, but I'm surprised it causes such difficulty. I've always been of the view that, despite Codd's restrictive definitions, all the set-like operations (UNION, INTERSECT, MINUS, etc) generalise simply:

• project each argument onto the set of common attributes
• apply Codd-like operation.

`MINUS` (with union-compatible operands) is not commutative nor idempotent nor associative. It has neither left nor right identity. No amount of generalising will give it nice algebraic properties; and projecting each argument on to the set of common attributes won't improve the situation. So I'm happy to generalise to `NOT MATCHING` (whose result has heading same as its left operand, and which has right identity `DUM`) and leave it at that.

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

That certainly looks associative, and I can see no way to construct a counter-example. Does that not suggest a method for a proof?

For `INTERSECT` project on to common attributes, looks can be deceptive it seems. And Tegiri has given a counter-example. So no wonder there's no proof. More of a concern is that Mace4 can't find a counter-example (perhaps I didn't run it for long enough, but it should only need a 6-element model; small beer by its lights).

Indeed. Informally, intersection before projection can remove tuples that would survive if projection goes first. Seems obvious given the counter-example.

I wonder if this has a real world application.

Andl - A New Database Language - andl.org
Quote from johnwcowan on July 6, 2019, 2:03 pm

I'm puzzled by all this.  Why should it be supposed that for the relational algebra to make sense, it must be single-sorted? It is certainly not your usual multi-sorted algebra with impermeable boundaries between types (analogous to parametric polymorphism), nor is it generalized multi-sorted algebra with a hierarchy of types (analogous to inclusion polymorphism).  Instead, there are complex relationships between sorts ("hyper-generalized multi-sorted algebra"?) with some operators constrained to classical multi-sortedness, and others with more complicated realizations.

I know that this just restates Codd's own definitions, but it does so in terms of a framework that is reasonably well understood.

? Is "single-sorted" the term you mean? It's generally taken relations are multi-sorted: relations with distinct headings are not directly comparable. (Then for example we can still distinguish two different-heading empty relations at the type level, even though there's no tuples to compare.)

For a lattice structure approach to relations, we're just expecting every relation value to be an element of a set. That's not the set-of-values sense in RM Pre 1 -- which is talking only about scalar types. No expectation that the set of relation values is homogeneous. Every expectation that operations over relations will be polymorphic.

If you're worried about operations over different-heading relations producing a result of another distinct heading: Codd's algebra already included Cartesian Product. What's notable about that (from a type-theory level, and in distinction to mathematicians' Cartesian Product) is the result isn't a pairing of tuples from the operands, but a 'flattened' structure: tuples from each operand are concatenated, not paired. And Codd included Natural Join in his original set, which will only work if we do the 'flattening' to produce a result of different heading from the two operands.

Codd's Natural Join was not a primitive; he defined it in terms of Cartesian Product and Renaming. All the lattice approach is doing is making Natural Join a primitive (we might say the primitive), and defining other operations relative to it. We don't even need to specifically define Cartesian Product: it's a natural (heh) consequence of the definition of Natural Join for relations with disjoint headings.

One other observation: the lattice approach is playing fast-and-lose with the math in a sense. These operations I'm talking about are 'navigating' through a lattice structure that is abstract; it's just nodes and edges. The lattice structure doesn't know anything about headings or tuples or attributes, let alone attribute types. So we come with an interpretation that maps the nodes/edges to familiar things like `DEE, DUM`, empty relations, relations with the same heading, relations whose heading is the union of headings from two other relations, etc.

So it's easy to dream up abstract operations over the lattice nodes/edges (like that `<"and">`). It's not always easy to see how to interpret that operation into the structure of relations. Then it's the convention to specify the operation using setbuilder notation, per Appendix A. Might we make a mistake in that interpretation? Yes. So it's always good to find relation value values forming a counter-example to verify a finding couched in terms of the lattice abstraction -- as Tegiri did to show non-associativity of `InnerIntersection`.

Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

• ...

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

Re that last, note Appendix A already defines `<REMOVE>` to take an attribute-name-list r.h. operand. Instead I want to put a relation (and consider only its heading). Then we get

• `x PROJECT_ON y ≡ x PROJECT_AWAY (x PROJECT_AWAY y);`
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

This has come up before. My view is that a simple extension gets us a long way. Allow any { attribute_list } to be replaced by a type expression, using terms such as relvars and obvious operators similar to those already in the language. Eg

{{ R1 intersect R2 }} or {{ R1 and R2 }} means the attributes common to both relations. Simple.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.
• {{ r }}
• r1 {{ r1 and r2 }} union r2 {{ r1 and r2 }}
• r1 {{ r1 minus r2 }}

Re that last, note Appendix A already defines `<REMOVE>` to take an attribute-name-list r.h. operand. Instead I want to put a relation (and consider only its heading). Then we get

• `x PROJECT_ON y ≡ x PROJECT_AWAY (x PROJECT_AWAY y);`
• x {{ y minus x }}
Andl - A New Database Language - andl.org
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

• ...

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

Rel provides TYPE_OF(e) where e may be any expression. E.g.:

TYPE_OF(sys.Catalog)
`NonScalar("RELATION",`
```AttrName

CHARACTER```
```AttrType

TypeInfo```
`Name`
`Scalar("CHARACTER")`
`Definition`
`Scalar("CHARACTER")`
`Owner`
`Scalar("CHARACTER")`
`CreationSequence`
`Scalar("INTEGER")`
`isVirtual`
`Scalar("BOOLEAN")`
`isExternal`
`Scalar("BOOLEAN")`
`Attributes`
`Scalar("NonScalar")`
`Keys`
`NonScalar("RELATION",`
```AttrName

CHARACTER```
```AttrType

TypeInfo```
`Attributes`
`NonScalar("RELATION",`
```AttrName

CHARACTER```
```AttrType

TypeInfo```
`Name`
`Scalar("CHARACTER")`
`)`
`)`
`)`

Per @Dandl's question, I do wonder about practical application.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org
Quote from Dave Voorhis on July 7, 2019, 7:46 am
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

• ...

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

Rel provides TYPE_OF(e) where e may be any expression. E.g.:

I think that's not going to help. What's the type of the value returned by `TYPE_OF(e)`? At least I assume it returns a value? How do I use it?

What I'm looking for is something more like `RELATION SAME_HEADING_AS(e) INIT (REL{})`.

Per @Dandl's question, I do wonder about practical application.

I can be flexible: let's cut a deal.

I'll give away `HEADING_OF(e)` because the longhand `(e) JOIN DUM` isn't much longer. I'll even give away `InnerUnion` providing I get both of

• `rx PROJECT_ON e`      //  project `rx` on attributes in common with `e` -- which might be anything from the whole heading to nothing in common
• `rx PROJECT_AWAY e`  // project `rx` on attributes not common with `e` -- which ditto
• in which `rx, e` are <relation exp>s, whose headings/types must be join compatible
• `e` need not be evaluated, indeed better if not: we only want to know its heading
• I can then express `r1 InnerUnion r2 = (r1 PROJECT_ON r2) UNION (r2 PROJECT_ON r1)`

Practical application? Rel is using them already, just in an ad-hoc and unsystematic way. (I made exactly that objection about Date's `IMAGE_IN`, but you implemented that ad-hockery.) I note that `IMAGE_IN` (like `COMPOSE`) involves exactly the sort of set-algebra over headings that I'm asking for. Indeed if we had the two generic projections above we could go

• `r1 COMPOSE r2 = (r1 JOIN r2) PROJECT_AWAY (r1 PROJECT_ON r2)`
• `IMAGE_IN(r, t) = (r JOIN RELATION{ t }) PROJECT_AWAY RELATION{ t }`
• And note `r1 MATCHING r2 = (r1 JOIN r2) PROJECT_ON r1`

You might object that definition for `COMPOSE` is heavyweight, but there's no computational cost: we want only the heading for the r.h. operand.

How many times do you write out an attribute list laboriously for a projection (or `ALL BUT`), when the list is exactly the heading of some relation, or the heading difference between two relations?

From Appendix A

─we have allowed ourselves the luxury (some might think) of including a "macro" operator called <COMPOSE>. <COMPOSE> is a combination of <AND> and <REMOVE>,

Why say "macro" and why in scare quotes, when it could just be an operator? Similar remarks re Appendix A's treatment of `<RENAME>`, which also needs weasly words to get round the obligation to use attribute name constants "(we assume here that R denotes a relation with an attribute called X and no attribute called Y).". Indeed a lot of the final section of Appendix A 'How Tutorial D Builds on A' has similar language giving stipulations for attribute-comma-lists. To pick a quote more or less at random:

(where A1 is the set of attributes common to r1 and r3, A2 is the set of attributes common to r2 and r4, and A3 is the set of attributes common to r3 and r4),

I could also see set-algebra over headings as useful for the attributes in

```r GROUP { [ ALL BUT ] <attribute ref commalist> } AS <introduced name>```

I'll concede that `InnerUnion` might be a bit opaque for tutorial purposes, but `PROJECT_ON` and `PROJECT_AWAY` are surely a natural lead in to pedagogy about headings and normalisation and the benefits of same-naming attributes in different base tables. This might go some way to defanging the jerks on StackOverflow who bleat "Natural Join considered harmful" at every opportunity.

Quote from dandl on July 7, 2019, 6:37 am
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

This has come up before. My view is that a simple extension gets us a long way. Allow any { attribute_list } to be replaced by a type expression, using terms such as relvars and obvious operators similar to those already in the language. Eg

{{ R1 intersect R2 }} or {{ R1 and R2 }} means the attributes common to both relations. Simple.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

(This is more of a follow-up to my response to Dave.)

• {{ r }}
• r1 {{ r1 and r2 }} union r2 {{ r1 and r2 }}
• r1 {{ r1 minus r2 }}

If I might be allowed unparliamentary language, there's a possibly-useful idea here, and a great deal of daftness. Why go using reserved words that are already relational operators to apply in exactly the opposite sense? (`union` of headings is the heading of `JOIN` of relations.) Furthermore there's already reserved words in Tutorial D to indicate the relative complement of a  heading: `ALL BUT`. The possibly-useful bit is to overload the trailing `{ }` syntax for projection. How about

• `r1 {ON r2}`           // project `r1` on attributes in common with `r2`; note this is not currently valid syntax, so no clashes
• `r1 {REMOVE r2}` // project `r1` on attributes not common with `r2` (I'd love to use `r1 {ALL BUT r2}`, but that would be syntactically ambiguous)
• in which `r2` is a relational expression, possibly itself using suffixed `{ }` for projection.

Re that last, note Appendix A already defines `<REMOVE>` to take an attribute-name-list r.h. operand. Instead I want to put a relation (and consider only its heading). Then we get

• `x PROJECT_ON y ≡ x PROJECT_AWAY (x PROJECT_AWAY y);`
• x {{ y minus x }}
• `x {ON y} = x {REMOVE x{REMOVE y} }`

Also from my message to Dave

• `r1 COMPOSE r2 = (r1 JOIN r2) {REMOVE r1 {ON r2}}`
• `IMAGE_IN(r, t) = (r JOIN RELATION{ t }) {REMOVE RELATION{ t }}`
• `r1 MATCHING r2 = (r1 JOIN r2) {ON r1}`
Quote from AntC on July 7, 2019, 10:35 am
Quote from Dave Voorhis on July 7, 2019, 7:46 am
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

• ...

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

Rel provides TYPE_OF(e) where e may be any expression. E.g.:

I think that's not going to help. What's the type of the value returned by `TYPE_OF(e)`? At least I assume it returns a value? How do I use it?

It's a value of type TypeInfo:

```TYPE TypeInfo UNION;
TYPE Scalar IS {TypeInfo POSSREP {TypeName CHAR}};
TYPE NonScalar IS {TypeInfo POSSREP {Kind CHAR, Attributes RELATION {AttrName CHAR, AttrType TypeInfo}}};
```
Quote from AntC on July 7, 2019, 10:35 am
Quote from Dave Voorhis on July 7, 2019, 7:46 am
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

• ...

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

Rel provides TYPE_OF(e) where e may be any expression. E.g.:

I think that's not going to help. What's the type of the value returned by `TYPE_OF(e)`? At least I assume it returns a value? How do I use it?

What I'm looking for is something more like `RELATION SAME_HEADING_AS(e) INIT (REL{})`.

Per @Dandl's question, I do wonder about practical application.

I can be flexible: let's cut a deal.

I'll give away `HEADING_OF(e)` because the longhand `(e) JOIN DUM` isn't much longer. I'll even give away `InnerUnion` providing I get both of

• `rx PROJECT_ON e`      //  project `rx` on attributes in common with `e` -- which might be anything from the whole heading to nothing in common
• `rx PROJECT_AWAY e`  // project `rx` on attributes not common with `e` -- which ditto
• in which `rx, e` are <relation exp>s, whose headings/types must be join compatible
• `e` need not be evaluated, indeed better if not: we only want to know its heading
• I can then express `r1 InnerUnion r2 = (r1 PROJECT_ON r2) UNION (r2 PROJECT_ON r1)`

Rel already provides these. PROJECT_ON is achieved via the extension pseudo-operator ATTRIBUTES_OF(r) where r is a tuple or relation expression, which returns an attribute list at compile-time. E.g.:

```VAR AODemo1 REAL RELATION {x INT, y INT, z INT} KEY {x};
VAR AODemo2 REAL RELATION {x INT, z INT} KEY {x};

Ok.

AODemo1 {ATTRIBUTES_OF(AODemo2)}```
```x

INTEGER```
```z

INTEGER```
```
AODemo1 {ALL BUT ATTRIBUTES_OF(AODemo2)}```
`y`
`INTEGER`
I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org
Quote from AntC on July 5, 2019, 11:30 am

Quiz first. Here's an operator `InnerIntersect` that is equivalent to `INTERSECT` if its operands have same heading. If they're different, project each operand on the attributes in common; then `INTERSECT` their projections. I.e.

`r1 InnerIntersect r2 =`df` r1{attributes-in-common} INTERSECT r2{attributes-in-common};`

In setbuilder, given `r1[X, Y], r2[Y, Z]` in which `X, Y, Z` are groups of attributes (each possibly empty)

`r1 InnerIntersect r2 =`df` {(Y) | ∃X (XY)∈r1 ∧ ∃Z (YZ)∈r2 }`

What algebraic properties does this have? It's clearly commutative and idempotent. It has an 'absorbing element' `DUM`. (Whereas `JOIN` has an identity element `DEE`.)

The money question: is it associative? That is, `(r1 InnerIntersect (r2 InnerIntersect r3)) = ((r1 InnerIntersect r2) InnerIntersect r3)`. I can see that if all operands are empty relations, that holds; or if they all have the same heading. I can see that the heading of the result must be the intersection of all headings. But in general? Intuition tells me it ought to be associative, because it's intersections all the way down; intuition is unreliable here. If not, please provide a counter-example.

(There could be other questions like: is this distributive over Appendix A's `<OR>`; but I need to prove associativity first; and I'm not making much headway.)

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

`MINUS` we can generalise to allow the headings of the operands to be different (not necessarily even having any attributes in common) -- as `NOT MATCHING`, then Appendix A generalises as `<AND> <NOT>`.

For `UNION`, if the operands have different headings, Appendix A chooses to generalise by returning a result with the union of headings, `<OR>` which might also be called `OuterUnion`, on a similar basis to `OUTER JOIN`. I've always felt queasy about that, because it's domain-dependent -- even if Tutorial D makes sure it could never be called in an 'unsafe query'. I prefer `InnerUnion` aka SQL's `UNION CORRESPONDING`, which is what ISBL implemented as Union: project each operand on the attributes in common; then `UNION` the projections. This operation is the dual of `JOIN`, in the sense if `r1 JOIN r2 = r2` then `r1 InnerUnion r2 = r1``JOIN` takes the union of headings and the intersection of tuples; `InnerUnion` takes the intersection of headings and the union of tuples.

Then if `InnerUnion` is the dual of `JOIN` aka `<AND>`, what is the dual of `<OR>` aka `OuterUnion`? It ought to be `InnerIntersect`, as described in the quiz. But then it ought to have complementary properties to `<OR>` (Union the headings and union the tuples cp intersect the headings and intersect the tuples.) But I'm not getting those properties to 'behave'.

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

I'm glad somebody else answered the quiz question (thanks).  As for InnerUnion, BS12 had it too and just called it UNION (perhaps not wisely).  I expect we were copying ISBL, as with many of our relational operators.  We also called our semijoin operator INTERSECT (even less wisely, perhaps, it's NOT MATCHING in TD).  I discovered years later that we had misunderstood Stephen Todd when he told us about "generalised intersection"; he actually meant JOIN, which of course we had anyway.

Hugh

Coauthor of The Third Manifesto and related books.
Quote from AntC on July 7, 2019, 10:35 am
Quote from Dave Voorhis on July 7, 2019, 7:46 am
Quote from AntC on July 6, 2019, 11:36 pm
Quote from dandl on July 6, 2019, 5:10 pm
Quote from AntC on July 6, 2019, 6:52 am
Quote from dandl on July 6, 2019, 5:00 am
Quote from AntC on July 5, 2019, 11:30 am

...

Generalising Codd

Codd's original set of operators for the Relational Algebra are rather annoying: there's tiresome restrictions on the headings of operands; which makes them all partial; and means they lack nice algebraic properties.

In particular, `UNION, INTERSECT, MINUS` require their operands to have the same headings ('union-compatible') whereas `TIMES` requires its operands to have disjoint headings. As Appendix A points out, we can observe that `TIMES` is a special case (disjoint headings) of `JOIN`, and `INTERSECT` is also a special case (same headings); so we can dispense with both and generalise as `JOIN`, or `<AND>` as Appendix A uses.

...

Yes I've copied `InnerIntersection` from Tropashko (he calls it InnerJoin). His papers claim it's not associative, not distributive over `<OR>`, and in general has disappointing properties. I suspect he has his definitions wrong.

• ...

The common attributes approach works for `UNION` as `InnerUnion`. The surprise (to me) is that gives a dual to `JOIN` aka `<AND>`. And we can combine with the properties for `DUM` (as Hugh investigated), as the join-to-make-it-empty element to get

`x PROJECT_ON y =`df` x InnerUnion HEADING_OF(y);` // i.e. project x on the attributes in common with y

`x SAME_HEADING_AS y =`df` HEADING_OF(x) = HEADING_OF(y);`

`HEADING_OF(x) =`df` x JOIN DUM;`

Then we can represent headings as relation values and start doing set-algebra on headings.

I wonder if this has a real world application.

The obvious application is to implement RM VSS 6 generic relational operators. Currently in Tutorial D/ Rel there's no way to access something that denotes the heading of a relation or to do the "set-algebra on headings" I talked about. The only way to get a projection is by explicitly naming the wanted attributes as constants (or naming the unwanted attributes with `ALL BUT`).

We can't even in Rel define my `HEADING_OF( )` above, even though it uses only Tutorial D operators/values, because it's polymorphic.

Even without opening the Pandora's box of user-defined relational operators, if there were just a few of these Tropashko operators available in Rel, we could really start cooking. We'd need

• `HEADING_OF( )`;
• `InnerUnion`, giving my `PROJECT_ON` above;
• `PROJECT_AWAY` aka generic `REMOVE`: project away from the left operand the attributes in common with the right operand.

I'll give away `HEADING_OF(e)` because the longhand `(e) JOIN DUM` isn't much longer. I'll even give away `InnerUnion` providing I get both of

• `rx PROJECT_ON e`      //  project `rx` on attributes in common with `e` -- which might be anything from the whole heading to nothing in common
• `rx PROJECT_AWAY e`  // project `rx` on attributes not common with `e` -- which ditto
• in which `rx, e` are <relation exp>s, whose headings/types must be join compatible
• `e` need not be evaluated, indeed better if not: we only want to know its heading
• I can then express `r1 InnerUnion r2 = (r1 PROJECT_ON r2) UNION (r2 PROJECT_ON r1)`

Rel already provides these.

Then doesn't that answer the question about practical applications?

PROJECT_ON is achieved via the extension pseudo-operator ATTRIBUTES_OF(r) where r is a tuple or relation expression, which returns an attribute list at compile-time. E.g.:

```VAR AODemo1 REAL RELATION {x INT, y INT, z INT} KEY {x};
VAR AODemo2 REAL RELATION {x INT, z INT} KEY {x};

AODemo1 {ATTRIBUTES_OF(AODemo2)}```
```
AODemo1 {ALL BUT ATTRIBUTES_OF(AODemo2)}```

OK good. And I like being able to use `ALL BUT`. I asked for a little more: can the `ATTRIBUTES_OF( )` return attributes that don't appear in the l.h. relation expression? If not, how to 'trim down' `ATTRIBUTES_OF(  )` appropriately? That's needed for example with the `IMAGE_IN( )` expression:

• `IMAGE_IN(r, t) = (r JOIN RELATION{ t }) {ALL BUT ATTRIBUTES_OF( t )}`  // `t` might have attributes not in `r`

BTW `ATTRIBUTES_OF( )` isn't documented in the Tut D approved variations, so how would I have known about it?

• `IMAGE_IN(r, t) = (r JOIN RELATION{ t }) {ALL BUT ATTRIBUTES_OF( RELATION{ t } {ALL BUT ATTRIBUTES_OF( r )})}`
because `r` might have attributes not in `t`.