Re: The Practical Benefits of the Relational Model

>>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.

Most of the OO folks I've met don't understand OO :) That's hardly an argument. Most of the supposed relational folks don't understand relational. Just visit your local bookstore and consult Oracle Press publications.

>>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 endeavor (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.

I understand that (kind of). But in the meantime they cry foul that there's (supposedly) no general consensus on the issue (1) and then they go on to say that if a system is to support "inheritance" at all (meaning subtyping) then it logically has to be their version or it's otherwise flawed.

Kind of contradictory, don't you think ? It's orthogonal as long as it's _only_ "S by C".

> Someone surely could propose an alternative
> type model for implementation in a relational system. To my
> knowledge, nobody has done this.

To begin with nobody has implemented a relational system as yet.

>>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.

That type can take an automatic name (maybe the same as the name of the class, because the namespaces should be distinct) or what have you.

A concrete class is mainly a mechanism to define an implementation. Think C++ and Java for a moment: what do you define with a concrete class, you define the template for the internal structure that objects instantiated from that class will have. In case of an abstract class, you define the implementation mechanism only in part, leaving for the concrete classes that will inherit to fill in the gap, but altogether the sub-classes *inherit* the _implementation structure_ (fields, functions,etc).

What happens then when you declare that a method expects an argument of a class ? Here's the confusion of C++ comes in (and you can't really blame Stroustroup because C+ was designed many moons ago when things weren't settled). When you use the class to qualify a parameter or a variable: you want to declare that the actual parameter (or the actual object) being passed to the variable *conmforms to* certain expectations (that it has an expected type).

With few exceptions, you couldn't care less what's the implementation mechanims as long as you can interact with the object through certain methods. Unfortunately in C++ class has two double role of defining an implementation _and_ defining a type. Pure abstract classes (classes which contain abstract methods *only*) can be said to represent a type, because they only established a contract , they don't mandate any implementation mechanism.

Java went half-way forward and introduced interfaces, which can be said to be pure types (in Java type system). But again classes can play this double role.

Imagine now for a brief moment that you have a system where classes and types are entirely distinct. Then to describe, let's say "apples" you'd have to define:
  class Apple {...} // the implementation of apples   type Apple { ... } // the type of apples - what apples expose to the outside world

Clearly this can be cumbersome in some cases, or at least inconvenient for lazy users. So it can be justified that when you declare class Apple, the system will automatically derive a type apple.

Now you get the picture?

> Let's make sure we agree that the simplest complete definition of a
> type is nothing more or less than a set of values. If we disagree
> there, we will need to change gears in this discussion.

I'm sure we disagree here, although I simpathize your view. Let's be clear: I'm not saying that you are wrong. You can define a framework (model) in which types are sets of values by definition. Nothing wrong with that.

By the way, how do you define values? As far as Mr. Date is concerned the values are immutable and carry their type with them. Kind of circular don't you think ?

But the real question is how useful that system is? (Assuming you can get past the circularity between values and types). It turns out that it is not really, as you probably found out when you decided not to implement features of the type system that are essential. You move complexities to the user's shoulders, because sets are defined by (arbitrarily complex) predicates, implication is undecidable, so:

         the user has to make sure that he doesn't have type errors.

But this is the main feature of a type system. That's what they were introduced in the mathematics to begin with. To make sure that type errors do not occur. So D&D's requirements for subtyping will automatically lead to systems that are cumbersome for users to work with.

There are two directions in which you can go for changing the definition type=set.

1. You can strengthen it or you can relax it. To strengthen it, we simply need to add a structure to the sets. That's what OO and separately functional programming came up with. By the way, I forgot to mention that functions are also subject to typing. That's an important subject that TTM misses altogether. But what structure to add? Sets can be structured as fields (Rationals), anneaux, modules, vector spaces, and lots of other things. One important answer to this dilemma the mathematical theory of categories to the rescue, because it derives theorems whatever the particular structure is chosen (it doesn't even have to be a set).
2. In the same way you can relax it through abstraction. You can choose something more abstract than the notion of set, but still useful in modeling. Sets can be derived from the more abstract framework.

I'm sure you'll find the reading of some of the books I referenced fascinating.

So I'd say that:

1. you can't separate the sets of values (in case we are talking about sets of values and not something more abstract, and for the programming activity that's kind of good enough) from the *structure* defined over them. For example it's irrelvant to consider the set of Rationals without the associated *,+ operator. The distinguished value 0 (and possiblty 1), and their associated mathematical theorems that tell me that Rational is a *field*. From this perspective you can easily see that Integer is not a sub-field of Rational, and therefore it might not be very useful to regard Integer as a *subtype* of Rational, it is a sub-set but not necessarily of sub-type. And this is merely when we are talking about abstract algebra.

When it comes to implementing that in computers, it runs out it is most *definitely not* a matter of logical model vs. implementation, because no computer in the world is going to implement Rationals as field in a useful way. Both let's say double (64 bit floating point numbers) and int (let's say 32 bit integers) are *approximations* of the mathematical objects, and this approximation has to be done again according to a mathematical model (the books on numeric algorithms deal with that extensively ) so we can have control over the process. Therefore, nomatter what D&D may say modeling Integer as subtype of Rational serves no useful purpose, and it is much more useful to have a type coercion (conversion) between int values and double values.

2) values have to be positively constructed, and not existentially assumed. So you shouldn't say "let there be rationals", but you should start with the implementation of certain objects that you can prove approximate the properties of rationals. Otherwise you go into the circular dependency type -> values -> types. This construction starts with primitive values, more exactly starts with the primitve values of 0 and 1 (the Bit or Boolean type), and goes through type constructors according to a well established rules that are integral part of the type system.

>>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.

It's not exactly delegation. But even that has no automatic support either in C++ or Java. Again inheritance has several useful models. But the main thing is that it allows reuse of implementation code.

>>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.

Indeed. The practical benefits, you already saw I think that is basically unimplementable in many aspects. So here's the clean separation between a nice logical model and the freedom of implementation :)

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

>>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.

Oh, glad to see that you're throwing responsibilities of the type system   into the hands of the user. I'm sure they'll be delighted :)

The user should only have to think about what he has to think, not checking that every intersection type is specifed and other such rubish things.

>>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. ... 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.

Missed reuse ? You must be kidding, right. The product is *undefined behaviour*, type errors, abnormal results, etc, etc.

>>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.
>>...
>>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 ?

The difference is that type system are supposed to taske care specifically of type errors.

>>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.

Because you know your attempt is doomed to fail.

My suggestion is that if you are serious about your product you should contact an expert in type theory (you probably won't find any around Usenet), but you can find, and see if you can come up with an indepenedent rigurous and scientific analysis fo the implications of D&D proposals.

Look around if you can't actually reuse type systems that are well established and some are even *proven* that they are well defined and sound (much different than an ambitious claim).

>>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.

Easier said than done :)

> Regards,
>
> --
> Nathan Allan

Cheers,
Costin Received on Sat Sep 28 2002 - 01:49:02 CEST