Re: Modelling Disjoint Subtypes

From: Marshall <>
Date: 25 Mar 2007 08:00:22 -0700
Message-ID: <>

On Mar 25, 3:26 am, Joe Thurbon <> wrote:
> Marshall wrote:
> > Having declared to the system that the type of S1.t is
> > a unit type (meaning the type has exactly one value)
> > the system is free not to store anything for the t column.
> Hi Marshall,
> To declare the type of the column, you'll need some storage. That is, I
> think what your suggesting moves some of the space required 'out of the
> column values' and 'into the column definition'. If reckon that to store
> one of N types, you'll need at least log2(N) bits.

Yeah, that's a fair point. The column-type storage costs are O(1), vs. O(count(R)), but it's still some storage.

> > This is possible because the number of bits needed to
> > represent a value of a given type is the log2 of the number
> > of possible values. Since T1 has 1 value, the number
> > of bits needed is log2(1) = 0.
> But there are now N extra types, and you'll need to store them somewhere.

As an aside, there exists systems in which the storage cost *at runtime* for type information is zero, because the types exist only at compile time, and are completely removed after. Such systems clearly cannot support some operations, e.g. ad hoc queries or reflection, which makes them unsuitable for the usual use-cases for a DBMS. However one can imagine a very static relational language, for example, that had this property.

Meta-aside: C++ has this property, which leads many people to believe that this property necessarily means the language is not safe, however the two are not correlated. One can have an entirely safe language with no runtime type information; all that is necessary is that the language not have any unsafe constructs, such as pointer casts. There are many such languages.

Marshall Received on Sun Mar 25 2007 - 17:00:22 CEST

Original text of this message