algebric types and db integration

Tom Pledger Tom.Pledger@peace.com
Thu, 6 Sep 2001 09:10:37 +1200


(Warning: this message contains evil SQL.  If in doubt, look away now.)

Cagdas Ozgenc writes:
 | Hi,
 | 
 | I am wondering how one would store instances of algebric types in a
 | database. For example:
 | 
 | data Shape = Circle Float | Rectangle Float Float | Triangle Float Float
 | Float
 | 
 | All three constructors are representing different schemas. Hence I
 | won't be able to store them in a single table. I think algebric
 | types seem to represent an inheritance hierarchy in terms of OO
 | terms, Shape being the base class, and Circle, Rectangle, Triangle
 | being its subclasses. Is this a correct way of looking at it?

In this case, I think it is.  It's fair to say that every circle is a
shape, every rectangle is a shape, and every triangle is a shape.
Some other algebraic types don't translate so well into an inheritance
hierarchy: it's confusing to say that every Just is a Maybe.

See section 4 of the paper

    http://www.cse.ogi.edu/~mpj/pubs/modinterp.html

for an example of how to treat a sum type as a supertype of its
summands.

 | How do you suggest I conceptually map it to a relational database?

If your RDBMS allows you to declare algebraic types or object classes,
that'd be a good way to represent Shape.  Then you could use Shape as
a column type.

Otherwise it gets messy.  You could denormalise and have overloaded
length columns

    create table shape (
        shape_id   integer not null, primary key (shape_id),
        shape_type char(1) not null, check (shape_type in ("C","R","T")),
        x1         float not null,
        x2         float,
        x3         float
    );

or normalise it and have each shape represented by two rows, one in
the generic shape table and one in a more specific table.

    create table shape (
        shape_id   integer not null, primary key (shape_id),
        shape_type char(1) not null, check (shape_type in ("C","R","T"))
    );

    create table circle (
        shape_id integer not null, primary key (shape_id),
                                   foreign key (shape_id) references shape,
        radius   float not null
    );

    create table rectangle (
        shape_id integer not null, primary key (shape_id),
                                   foreign key (shape_id) references shape,
        width    float not null,
        height   float not null
    );

    create table triangle (
        shape_id integer not null, primary key (shape_id),
                                   foreign key (shape_id) references shape,
        side1    float not null,
        side2    float not null,
        side3    float not null
    );

IMO these last two approaches are using the wrong tool for the job.
The relational model is great for representing a world view, made up
of statements about objects, but it's not so suitable for the
`subatomic' structure within objects.

Regards,
Tom