Re: The Practical Benefits of the Relational Model

>>I took notice of Mr. Date's reply, and I'll choose to reply to him in
>>private to the more important issues, because I see no fun in corresponding
>>with Mr. Date through intermediaries.

That's not the reason. But as far as I know Mr. Date doesn't like Internet discussions (not to mention he's disconnected from Internet). He may or may not make the discussion public on his regular sites like www.dbdebunk.com, once he decides whhat value it has and puts some order into it.

>>But since you are the one who claimed in this thread that OO has pretty much
>>all the bad qualities and the relational model (or to say more accurately:
>>the proposal of Date & Darwen for "future directions of data and database
>>management systems") comes and cure them all, including the "type
>>inheritance" , I'll ask you if you did your homework and read the references
>>I gave you.

You'd be interested to read an alternative point of view. Of course OO in database management is not meant to be a replacement for the relational model but an extension of the relational model. Interestingly enough, many of the major contributor to OODB theory have previously contributed substantially to the development of relational theory.

> As
> for OO's particular incarnation of type inheritance (or subtyping if
> you please) I am convinced that it suffers from several problems.

There's no "OO particular incarnation of subtyping". There's C++ incarnation of that, there's Java incarnation of that, and so on, so forth.

Many of such incarnations suffer from various problems. In general, in designing a proper type systems for a particular endeavour (be it a general purpose programming language or a database language), one has to choose some trade-off. Therefore it is quite unlikely that even D&D may ultimately come out with _the_ relational incarnation of subtyping. As they noted in their book the type systems is relatively orthogonal to the relational model, so somebody may come up with a different type system to attach to the same basic relational model.

>>Having read those references how do you see the initial statements that
>>you've made?
>>Are you aware now of the difference between subtyping and inheritance, and
>>what is the practical benefit of separating subtyping from inheritance?

To cut a long reading short, you may want to start with Luca Cardelli "Type Systems" (it's quite short indeed), and possibly Constable's "Naive type theory". Then you'll be able to judge if D&D have a "formal type system" in TTM.

>>"Type inheritance" as such does apear in some OO books here and there,
>>though I think the prevalent term is "class inheritance". In most OO model a
>>class automatically defines a type, but the reverse is not generally true.

No I mean a class defines a type. Meaning for every class in the system there's automatically a type associated with it. It is a common consensus in the scientific community that it is worthy to make the distinction between classes and types.

>>I didn't assume that the Third Manifesto actually contains  a *formal* type
>>system. Even the language and style of the book led me to such a conclusion.

Inheritance is an implementation mechanism: you "inherit" and reuse the code, without being necessarily in a subtyping relation with the class that you inherit from. I know that sounds kind of utopic in C++ and Java but it can be done both in theory and in practice.

Then, as I said to Mr. Date in a previous correspondence the search for a consensus on subtyping is utopic and misguided. Each subtyping definition will belong to a particular type system.

And given the results in type theory so far, it's almost sure there can't be any such "ultimate type system" that's going to meet everyone' s needs in every possible context because of some hard mathematical results with regards to undecidability.

There will naturally be different type systems best fitted for different problems.

> "Part ... of this book describes an inheritance model that (we
> believe) could serve to fill the gap. ... We do not include it as a
> mandatory part of the manifesto, however---we merely insist that
> <b>IF</b> type inheritance is supported at all, <b>then</b> that
> support shall be based on the model described..."
>
> Chapter 13 contains the formal definition of that model.

When you correlate that with Cardelli's requirements "formalizing a type system" you'll see that chapter 13 can't constitute a formal type system. A formal model of subtyping can only be discussed as part of an actual type system.

>>It is in this sense that I said "it is simply not true [that relational
>>model have a formal and well defined model of type inheritance]".

You didn't need to make such a point to begin with!

First of all, _subtyping_ is not an OO concept (it applies to OO as well, and part of the OO literature helped it becoming popular and terribly misunderstood by the larger public). Subtyping is an essential concept in functional programming, logic programming , specialized areas of mathematics.

When it comes to inheritance, this is indeed an OO concept. But because it refers specifically to the implementation of programs, then I don't even think it has a place within a relational framework, because relational is not concerned with code structures.

> I would have likely
> stepped on fewer toes had I stated it that way, but surely you agree
> with the idea?

See above. You made a point that is kind of vacuously true.

>>I never
>>took the _requirements_ for a future type system of a future language as the
>>type system itself, so it wasn't a slighting remark (IMO).

Since you couldn't resist, I couldn't resist to argue that even in this regard, it is probably you that are left with some homework or actual company work to do if you intend to support D&D's type inheritance model in your product :)

I'm aware that they made a great effort. It wasn't quite clear to me that they claim to have a full "formal, rigurous and well defined" model of subtyping. To begin with, such a model can't exist unless within the context of a full "formal, rigurous and well defined type system".

Let's see, "formal" means to have a mathematical account of the relevant aspects (and functions) of type systems. It's quite easy to observe that they present an informal justification in prose for the requirements they make (OO prescriptions) on a virtual type system that would correspond to a D language.

Well defined, means that within their framework every concept is well defined in the mathematical sense, and no contradiction can be derived starting from it. They didn't include such an account in the book, and one can easily find examples of non-well-definedness within their framework.

For example one crucial property in the system is: _most specific type unique_, which ultimately boils down to the condition that the type system forms a lattice with regards to the subtyping relation. Though the unnecessary stronger condition is given on page 332.

Now here's the big problem: how the system makes sure that the user defined types together with the system defined types actually form a lattice ? How to resolve this crucial problem is left open, therefore "undefined". See the final point on the page 333.

A solution to this problem just can't be left as an exercise for the reader, because it is unlikely to find an easy and convenient resolution. As far as the examples in the book go, one could imagine that it is the resonsibility of the user to define intersection types and union types, and the system just has to check they are in there. But I'll give you 100 types to start with (which is _extremely_ modest as real life example) and let you figure out how many intersection types you need to declare. This clearly can't be left for any sane user to do, cause it's sure as hell it will tunr back to Oracle and SQL.

On the other hand, if we let the system to automatically infere union and intersection types where they are missing, it is very likely that no

   computer will be up to the task.

Independently of the resolution of this particular problem, there is the undefined type equivalence, and this is a crucial aspect of type system. When two types are the same ? Or to begin with when a type is a subtype of another ? D&D just declares that by "fiat": when there one is subset of another, but real life doesn't work that way.

How is the system going to decide that? Let's examine a very simple case.

Previously in the chapter Date defines Rhombus as the intersection type between Paralelogram and Equilateral (a parallelogram with all sides equal). He further notes that it could have been defined as the intersection between Quadrilateral and Equilateral, of course anyone who studied mathematics should be aware of that. Except that computer systems are not that intelligent. So let's assume this scenario: a user defines type X1:= Paralelogram INTERSECT Equilateral and type X2:= Quadrilateral INTERSECT Equilateral.

What happens with X1 and X2 from the system point of view ? Are they the same types, and how can the system reach that conclusion ?

D&D can say that this is an implementation exercise, but it can be proven that this exercise cannot be solved, because it ultimately boils down to resolving the implication problem in the case where the predicates defining the types (mandated by S by C) are any boolean expression defined in the D language.

That condition alone is good enough to make it unsolvable,so the bottom line is that the type system _cannot_ decide when one type is a subtype of another. This is hardly a desirable feature for type systems.

To cut a long story short, given the fact that we have so many impossibility results in Mathematics and in Computer Science, what is actually required from a type system, is to be actually _constructed_ (in the spirit of constructive mathematics). It is not good enough to "describe" the properties of a model, you have to define the objects of an instance of such a model, and prove that they satisfy certain properties.

In computer terms, you have to come up at least with one implementation, to show that the model can be implemented. Then you need to prove certain theorems about your system.

> When all is said and done, it may have been a mistake for me to even
> bring up this controversial matter lest I cast a negative shadow on
> the true essence of what I was attempting to portray. My apologies
> for the distraction.

Yes, indeed. I don't think you can accurately say that "a formal and well defined model of type inheritance" IS A "practical benefit of relational model".

The best thing that can be said is that an implementation of relational model can benefit from a formal type system, supporting subtyping. Additionally, the implementation might offer to the user the benefit of using inheritance as a mechanism to more efficiently implement user defined types and user defined functions.

> Regards,
>
> --
> Nathan Allan

Best regards,
Costin Cozianu Received on Fri Sep 27 2002 - 01:54:05 CEST