The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Are inclusion dependencies reducible to foreign-key dependencies?

Quote from Erwin on October 19, 2019, 5:34 pm
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

VAR X REL {A ODD, B ODD};

X := REL {A INT, B INT}{TUP {A 5, B 7}}

Since both 5 and 7 are members of ODD, the MST of the RHS of the assignment is REL {A ODD, B ODD}.  The RHS can be evaluated at compile time, along with the MST of the result.

(1) Should a compiler error be thrown because REL{A INT, B INT} is not a subtype of REL {A ODD, B ODD}?

(2) Should a compiler error be thrown when the most-specific type of a relation constant does not match its declared type?

Finally,  REL {A ALPHA, B ALPHA}{} and REL {A OMEGA, B OMEGA}{} denote the same value.  Quibbling about my usage of either is therefore moot.

Brian

To my mind, no and no.

The fact that the programmer chose to explicitize '{A INT, B INT}' in 'REL {A INT, B INT}{TUP {A 5, B 7}}' does not make a difference.  It's just an optical illusion, so to speak, possibly deluding some compiler writers / language definers into believing that this "must" influence [the way the compiler determines] the declared type the expression on the RHS has.

Now you consider REL {TUP{A 5, B 7}}, which is the way the vast majority of programmers would certainly prefer to write it.

What other option is there but to treat this as an expression of declared type the same as the MST of the value ?  What reasons are there for suddenly doing anything different if the programmer chooses to add those noise words '{A INT, B INT}' to what he minimally needed to write ?

You're making my point.  What reasons are there for declaring the type of any literal?  The only literals in TTM with or without the IM that require such declaration denote empty relations.

Brian

Quote from Brian S on October 20, 2019, 12:48 pm
Quote from Erwin on October 19, 2019, 5:34 pm
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

VAR X REL {A ODD, B ODD};

X := REL {A INT, B INT}{TUP {A 5, B 7}}

Since both 5 and 7 are members of ODD, the MST of the RHS of the assignment is REL {A ODD, B ODD}.  The RHS can be evaluated at compile time, along with the MST of the result.

(1) Should a compiler error be thrown because REL{A INT, B INT} is not a subtype of REL {A ODD, B ODD}?

(2) Should a compiler error be thrown when the most-specific type of a relation constant does not match its declared type?

Finally,  REL {A ALPHA, B ALPHA}{} and REL {A OMEGA, B OMEGA}{} denote the same value.  Quibbling about my usage of either is therefore moot.

Brian

To my mind, no and no.

The fact that the programmer chose to explicitize '{A INT, B INT}' in 'REL {A INT, B INT}{TUP {A 5, B 7}}' does not make a difference.  It's just an optical illusion, so to speak, possibly deluding some compiler writers / language definers into believing that this "must" influence [the way the compiler determines] the declared type the expression on the RHS has.

Now you consider REL {TUP{A 5, B 7}}, which is the way the vast majority of programmers would certainly prefer to write it.

What other option is there but to treat this as an expression of declared type the same as the MST of the value ?  What reasons are there for suddenly doing anything different if the programmer chooses to add those noise words '{A INT, B INT}' to what he minimally needed to write ?

You're making my point.  What reasons are there for declaring the type of any literal?  The only literals in TTM with or without the IM that require such declaration denote empty relations.

Brian

In programming in general, you declare variable types -- sometimes even in languages that support type inference -- because:

a) You wish to establish and document a contract that subsequent assignments must obey (i.e., "all subsequent assignments must be of this explicit type"); and/or
b) You wish to allow assignments that belong to a specified subtype of the declared type, and first literal assigned is a subtype of the declared type.

The same applies to relations and relation headings -- the heading establishes and explicitly documents a contract that all tuples must obey. In Tutorial D, you're not required to specify the heading of a relation -- it can be inferred from tuples -- but you may wish to specify it for the reasons noted.

The relation heading is unconditionally retained -- even in empty relations -- because it indicates the realm of values to which the relation belongs and type erasure is bad, both of which can impact on integrating database languages into application development environments and (ultimately) applications.

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 Brian S on October 20, 2019, 12:48 pm
Quote from Erwin on October 19, 2019, 5:34 pm
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

VAR X REL {A ODD, B ODD};

X := REL {A INT, B INT}{TUP {A 5, B 7}}

Since both 5 and 7 are members of ODD, the MST of the RHS of the assignment is REL {A ODD, B ODD}.  The RHS can be evaluated at compile time, along with the MST of the result.

(1) Should a compiler error be thrown because REL{A INT, B INT} is not a subtype of REL {A ODD, B ODD}?

(2) Should a compiler error be thrown when the most-specific type of a relation constant does not match its declared type?

Finally,  REL {A ALPHA, B ALPHA}{} and REL {A OMEGA, B OMEGA}{} denote the same value.  Quibbling about my usage of either is therefore moot.

Brian

To my mind, no and no.

The fact that the programmer chose to explicitize '{A INT, B INT}' in 'REL {A INT, B INT}{TUP {A 5, B 7}}' does not make a difference.  It's just an optical illusion, so to speak, possibly deluding some compiler writers / language definers into believing that this "must" influence [the way the compiler determines] the declared type the expression on the RHS has.

Now you consider REL {TUP{A 5, B 7}}, which is the way the vast majority of programmers would certainly prefer to write it.

What other option is there but to treat this as an expression of declared type the same as the MST of the value ?  What reasons are there for suddenly doing anything different if the programmer chooses to add those noise words '{A INT, B INT}' to what he minimally needed to write ?

You're making my point.  What reasons are there for declaring the type of any literal?  The only literals in TTM with or without the IM that require such declaration denote empty relations.

Brian

I thought we disagreed on something.

The reasons you ask for are probably pragmatic in nature.

Relation literals are lengthy expressions making them more prone to mistakes.  Overlooking an attribute in the body of the tuples might not invalidate the expression overall (e.g. if the literal is merely used in a JOIN/MATCHING/NOT MATCHING), but might still be wrong, and might still cause long search times before finding the error.  If a programmer has the possibility to explicitize the heading he's planning to specify in the body, the compiler can check that and raise flags (that word again - RED flags are meant here) earlier on.

 

Quote from dandl on October 20, 2019, 1:44 am
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

I think you need to read TIRT.

Is it available online?  Is there definitive information concerning the IM that is available in that book that isn't available on the TTM website?

The Inheritance Model posted on the TTM website doesn't directly address the types of empty relation values.  While it's possible to determine the most-specific type of a nonempty set of scalar values, and as a result the most-specific type of a non-empty set of tuples, it is unclear what the most specific type is when those sets are empty.  One can assume that the most-specific type of an empty set of scalar values is omega, but that is not explicitly stated in the text.  Moreover, it is not clear from the text what the tuple type is when a relation is empty.  We can assume that it is a minimal tuple type, but that is also not explicitly stated in the text.  It could be an empty tuple type with the same set of attribute names (assuming that all of the attributes are scalar, of course).

I'm beginning to wonder whether that omission was deliberate.  A D where there is only one empty relation doesn't violate TTM with the IM, since the most-specific type of a relation value is defined in terms of the most-specific types of the tuples in the body.  The most-specific type of a tuple is derived from the most-specific types of its components; likewise, the heading of a relation under the IM is derived from the body.  But when there are no tuples, there is nothing to derive from.

VAR X REL {A INT, B INT}

VAR Y REL {A CHAR, B CHAR}

Now suppose that there is a union type INT_OR_CHAR.

The declared type of the expression X UNION Y is REL {X INT_OR_CHAR, Y INT_OR_CHAR}, but what is the most-specific type of X UNION Y when both X and Y are empty?

Is it REL {X INT_OR_CHAR, Y INT_OR_CHAR}, REL {X INT_OR_CHAR, Y omega}, REL {X omega, Y INT_OR_CHAR} or REL {X omega, Y omega}?  In other words, does the most-specific type become the declared type when the body is empty?  Is an empty type with the same structure as the declared type arbitrarily chosen?  Or must it always be the minimal type with the same structure as the declared type whenever the result is empty?  The IM prescriptions don't make that clear.

In my view, the most-specific type of an empty relation should simply be REL {}, and REL {} must be a subtype of all relation types.  The only place where this poses a problem is for static type checking of relation expressions having dissimilar structures.  I think such constructions should be allowed, but with a warning being issued at compile time.

Having a single empty relation, namely, the empty set, makes it possible to generalize the model with tuplesets--sets of tuples having dissimilar headings--at least for the results of queries.  Producing a report containing all employees, for example, some of which are hourly, some salaried, and some under contract.  There are a lot of hoops you have to jump through in order to make that happen using only relation values.  Seniority, for instance, is common to hourly and salaried employees, but not contractors.  Returning a set of tuples instead simplifies the process.  Also, from a logical standpoint, the predicate of the tupleset result above is simply the disjunction of the predicates of HOURLY_EMPLOYEES, SALARIED_EMPLOYEES and CONTRACTORS.  That is not the case for a relational result, which requires special values to be injected to indicate inapplicable information.

Brian

Quote from Brian S on October 20, 2019, 3:36 pm
Quote from dandl on October 20, 2019, 1:44 am
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

I think you need to read TIRT.

Is it available online?  Is there definitive information concerning the IM that is available in that book that isn't available on the TTM website?

The Inheritance Model posted on the TTM website doesn't directly address the types of empty relation values. [...]

It specifically expands on that and related issues.

https://books.google.co.uk/books?id=alsdDQAAQBAJ

 

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 Brian S on October 20, 2019, 12:48 pm

You're making my point.  What reasons are there for declaring the type of any literal?  The only literals in TTM with or without the IM that require such declaration denote empty relations.

Not so. In many languages literals can be ambiguous. The value 987 could be a small integer, large integer, decimal, single or double precision float, and used to initialise a variable or attribute declared to be of that type. IOW: in some languages the values REL { INT X, INT Y }{ 0,0 } and REL { INT X, FLOAT Y }{ 0,0 } are valid and different. The type has to be specified.

Andl - A New Database Language - andl.org
Quote from Dave Voorhis on October 20, 2019, 1:21 pm

The relation heading is unconditionally retained -- even in empty relations -- because it indicates the realm of values to which the relation belongs and type erasure is bad, both of which can impact on integrating database languages into application development environments and (ultimately) applications.

I think this is meaningless, or at least vacuous. A relation has a heading when it is created (always); it retains its heading because it is immutable, not for any other reason. Or perhaps you meant something different?

Andl - A New Database Language - andl.org
Quote from Brian S on October 20, 2019, 3:36 pm
Quote from dandl on October 20, 2019, 1:44 am
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

I think you need to read TIRT.

Is it available online?  Is there definitive information concerning the IM that is available in that book that isn't available on the TTM website?

You can easily find a paid edition (if you have budget to spend)and there is a link on the TTM site to O'Reilly, but I found a free one here: https://www.allitebooks.in/type-inheritance-relational-theory/.  It would be nice if the TTM site linked to it.

@Hugh?

Yes, It contains heaps of additional explanatory material, including much that bears directly on your proposition, but nothing that answers it head on (that I could find).

The Inheritance Model posted on the TTM website doesn't directly address the types of empty relation values.  While it's possible to determine the most-specific type of a nonempty set of scalar values, and as a result the most-specific type of a non-empty set of tuples, it is unclear what the most specific type is when those sets are empty.  One can assume that the most-specific type of an empty set of scalar values is omega, but that is not explicitly stated in the text.  Moreover, it is not clear from the text what the tuple type is when a relation is empty.  We can assume that it is a minimal tuple type, but that is also not explicitly stated in the text.  It could be an empty tuple type with the same set of attribute names (assuming that all of the attributes are scalar, of course).

The topic is addressed directly in TIRT. To cut to the chase, it says that the MST of the empty relation is the minimal type T_omega, but that comparing for equality is not permitted (fails to compile) unless the types of the respective headings are related in a particular way. IOW they don't all compare equal just because they have the same MST.

I'm beginning to wonder whether that omission was deliberate.  A D where there is only one empty relation doesn't violate TTM with the IM, since the most-specific type of a relation value is defined in terms of the most-specific types of the tuples in the body.  The most-specific type of a tuple is derived from the most-specific types of its components; likewise, the heading of a relation under the IM is derived from the body.  But when there are no tuples, there is nothing to derive from.

VAR X REL {A INT, B INT}

VAR Y REL {A CHAR, B CHAR}

Now suppose that there is a union type INT_OR_CHAR.

The declared type of the expression X UNION Y is REL {X INT_OR_CHAR, Y INT_OR_CHAR}, but what is the most-specific type of X UNION Y when both X and Y are empty?

Addressed in TIRT. The heading is derived from X and Y according to the rule 'most specific common supertype', correct. The MST is again T_omega.

Is it REL {X INT_OR_CHAR, Y INT_OR_CHAR}, REL {X INT_OR_CHAR, Y omega}, REL {X omega, Y INT_OR_CHAR} or REL {X omega, Y omega}?  In other words, does the most-specific type become the declared type when the body is empty?  Is an empty type with the same structure as the declared type arbitrarily chosen?  Or must it always be the minimal type with the same structure as the declared type whenever the result is empty?  The IM prescriptions don't make that clear.

No, but I think TIRT does. Each of those types is perfectly legal, in a different context. The declared type is not quite the right term for an expression, but I won't try to paraphrase TIRT, it does address the issue. See p24

In my view, the most-specific type of an empty relation should simply be REL {}, and REL {} must be a subtype of all relation types.  The only place where this poses a problem is for static type checking of relation expressions having dissimilar structures.  I think such constructions should be allowed, but with a warning being issued at compile time.

Having a single empty relation, namely, the empty set, makes it possible to generalize the model with tuplesets--sets of tuples having dissimilar headings--at least for the results of queries.  Producing a report containing all employees, for example, some of which are hourly, some salaried, and some under contract.  There are a lot of hoops you have to jump through in order to make that happen using only relation values.  Seniority, for instance, is common to hourly and salaried employees, but not contractors.  Returning a set of tuples instead simplifies the process.  Also, from a logical standpoint, the predicate of the tupleset result above is simply the disjunction of the predicates of HOURLY_EMPLOYEES, SALARIED_EMPLOYEES and CONTRACTORS.  That is not the case for a relational result, which requires special values to be injected to indicate inapplicable information.

I don't think any of this is consistent with either the intent or the wording in TIRT.

 

Andl - A New Database Language - andl.org
Quote from dandl on October 21, 2019, 12:11 am
Quote from Brian S on October 20, 2019, 3:36 pm
Quote from dandl on October 20, 2019, 1:44 am
Quote from Brian S on October 19, 2019, 2:17 pm

My position is that it is redundant, and possibly problematic to include the heading with the value. Consider:

I think you need to read TIRT.

Is it available online?  Is there definitive information concerning the IM that is available in that book that isn't available on the TTM website?

You can easily find a paid edition (if you have budget to spend)and there is a link on the TTM site to O'Reilly, but I found a free one here: https://www.allitebooks.in/type-inheritance-relational-theory/.

Thank you David. I'm not engaging with Brian's pet peeve. On an oblique 'never mind the quality, feel the width': can it really take over 500 pages to explore Date's Inheritance Model? Even given Date's usual prolixity, that seems way beyond anything reasonable. By comparison, how much would it take to explain Java's inheritance and contrast it with C++? Haskell's inheritance (which is not inheritance of types, but achieves the same objectives) takes a couple of pages in the Language Report, and maybe half a dozen pages to explore the consequences in an introductory text. Maybe another half dozen pages in documentation of compiler extensions.

Date's preface says " the book isn’t so much a textbook as it is a plea for the community at large to take a careful look at what we’ve done: a careful look, in fact, at what we consider to be a logical, sensible, and pragmatically useful approach to the subject."

If I count as part of the 'community at large', wading through DBE Ch 19 was bad enough; I'm not going to take a "careful look" at 500+ pages unless I can see WIIFM. But AFAICT looking at the index entries, nothing on: sum types, product types, sum-of-product types, tagged unions, abstract types, parametric types, ... (I'm not saying the IM is without equivalents to those; I am saying that if Date wants to engage 'the community' he should try to explain in the community's language. OTOH I'm not asking for another 100 pages.)

 

Quote from dandl on October 20, 2019, 11:43 pm
Quote from Dave Voorhis on October 20, 2019, 1:21 pm

The relation heading is unconditionally retained -- even in empty relations -- because it indicates the realm of values to which the relation belongs and type erasure is bad, both of which can impact on integrating database languages into application development environments and (ultimately) applications.

I think this is meaningless, or at least vacuous. A relation has a heading when it is created (always); it retains its heading because it is immutable, not for any other reason. Or perhaps you meant something different?

TTM defines a relation to have a heading and a body (consisting of a set of tuples), all immutable.

A different relational model could define a relation as an immutable set of tuples with the same attribute names and types. A heading might then only be part of (say) the specification of a relation literal, not a relation itself.

My explanation provides a justification for preferring the former over the latter.

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