Very Computer

In the article Thirty Years of Relational: Extending the Relational
Model by C.J. Date, Date talks about ADTs.  What does he mean by
abstract data types in the context of the relational model?

"But this claim is absurd!  As Hugh Darwen and I have shown in The
Third Manifesto,2 object functionality and the relational model are
completely orthogonal to one another. To quote: "The relational model
needs no extension, no correction, no subsumption, and above all no
perversion, in order [to support object functionality]." All that's
needed is to support relational domains properly (which SQL never
did), recognizing those domains for what they are, which is basically
just abstract data types (ADTs), With All That That Entails.  In other
words, the so-called O/R model is just the relational model, pure and
simple; there aren't any (genuine) "relational model extensions"
involved at all."

http://www.intelligententerprise.com/db_area/archives/1999/990106/onl...

Robert Schiller

Anything that can be described in terms of the operations that are
allowed upon it and has some kind of user readable representation. This
includes things like numbers, dates and strings but also more complex
things like lists, stacks and ... <drum roll> ... relations.

--
  Jan Hidders

Hmmmmm...not exactly. Relations are not abstract data types up to
the time when one would define a complete and exclusive set of
operations acting on relations. Stacks - yes, they are abstract data
types because can be fully served by four classical operations:
push, pop, top and empty. Can we imagine this set of operations for
relations? Relational algebra? This is wrong. Relational algebra
operators are indexed by meta-language expressions, hence in fact
the relational algebra consists of meta-operations, which are
equivalent to the infite number od ADT operations.
Besides, the relational algebra is far to be complete as a tool for
serving all purposes of processing relations. SQL? Again, this is
wrong - the same arguments, plus updating operations, which act
not on relations, but on _stored_ relations, i.e. database states.

Conclusion 1: The relational model is totatally incompatible with ADT.
Conclusion 2: Date and Darven are demagic, undereducated relational
bigots, please don't believe them.

Kaz

No, it isn't. The algebraic rules for the relational algebra define
relations up to isomorphism. Sure, they are incomplete in several other
ways but so is the usual definition of the Stack ADT.

Quote:> [...] Besides, the relational algebra is far to be complete as
> a tool for serving all purposes of processing relations.

Whether the set of operations is computationally complete or not is
irrelevant.

Quote:> Conclusion 1: The relational model is totatally incompatible with ADT.
> Conclusion 2: Date and Darven are demagic, undereducated relational
> bigots, please don't believe them.

Hmmmm... not exactly. :-)

--
  Jan Hidders

Just out of curiosity, wouldnt:

Empty, Insert, Union, Intersection, Difference, Product, Join, Select and
Project

surve as an ADT for relation?

[...]

/Lennart

Quote:> >> Anything that can be described in terms of the operations that are
> >> allowed upon it and has some kind of user readable representation. This
> >> includes things like numbers, dates and strings but also more complex
> >> things like lists, stacks and ... <drum roll> ... relations.

> >Hmmmmm...not exactly. Relations are not abstract data types up to
> >the time when one would define a complete and exclusive set of
> >operations acting on relations. Stacks - yes, they are abstract data
> >types because can be fully served by four classical operations:
> >push, pop, top and empty. Can we imagine this set of operations for
> >relations?

> Just out of curiosity, wouldnt:

> Empty, Insert, Union, Intersection, Difference, Product, Join, Select and
> Project

then: +, -, *, /, sum, avg, min, max, count, like, distinct, exists, order
by... ?
then: quentifiers, assignments, if...then...else, while...do...?

Unfortunately you are on a wrong way, for two reasons.
First, some of you operations, e.g. select, are indexed by a predicate.
Considering select an ADT operation it must have a predicate as an argument.
Hence at least it is a second-order operator. If the predicate uses
the other ADT operators, it means some unacceptable mix of language and
metalanguage levels. Imagine this practically: you are a programmer
who is trying to implement the select operator as a piece of a program.
Your program takes the predicate text as a parameter, parses and
compiles it, generates its code, executes and then discovers that
this parameter refers to the select operator. Is such a recursion sound?

Unfortunately not.
Gurus from the polymorphic programming languages camp sadly confess
their polymorphisms are not sufficiently powerful to write e.g.
generic procedures for join, select and other relational operators.

The second reason is that in people already dealt with the topic
(see eg. m.Ley's bibliography http://dblp.uni-trier.de/db/ around 1985).
The consequences of this research can be shortly summarised
as an absolute zero in the Kelvin scale.

Of course, in theory everything is possible and the entire programming
langauge such as C++ can be treated as an infinite set of operators
(all of them acting on a one biiiiiiiiig ADT - the program state  :-)).
But such a treatement as dry as Sahara during hot summer.

Cheers
Kaz

No. The +, .., 'count' and 'like' are operation on things you store inside the
relations an should not be in the ADT for the same reason they are
also not in the ADT of stack. The 'distinct' is of course not necessary
because in true relations there are no duplicates. The exists can be
simulated with joins. The 'order by' produces an ordered list and is
therefore also not part of the Relation ADT itself.

Quote:> then: quentifiers, assignments, if...then...else, while...do...?

Like I said, computational completeness is not a requirement for a good
ADT.

Quote:> Unfortunately you are on a wrong way, for two reasons.
> First, some of you operations, e.g. select, are indexed by a predicate.

Not necessarily. You only need the simplest selects and they are only
indexed with either two attribute names or an attribute name and a
constant.

Quote:> Considering select an ADT operation it must have a predicate as an
> argument. Hence at least it is a second-order operator. If the
> predicate uses the other ADT operators, it means some unacceptable
> mix of language and metalanguage levels.

Complex predicates are not expressed with other relational operators
but with the usual AND, OR, NOT, et cetera. So there is
no recursion there and it is not a second-order operator.

And even if it was, that wouldn't be really a problem. Yes, the direct
implementation in C++ would not be easy but in many higher order
languages such as functional programming languages and Smalltalk it is
straightforward. So there is no fundamental problem why you couldn't
implement a database that allows the user to define it's own domains
in terms of higher-order algebras.

So your argument is not only false, it is also irrelevant.

Quote:> The second reason is that in people already dealt with the topic
> (see eg. m.Ley's bibliography http://dblp.uni-trier.de/db/ around 1985).
> The consequences of this research can be shortly summarised
> as an absolute zero in the Kelvin scale.

Try reading someting after 1985. Typing the relational algebra has
never been a problem. Sure, it is difficult to describe the type of
*the* join, but that doesn't mean you cannot have a complete set of
typing rules.

Quote:> Of course, in theory everything is possible and the entire programming
> langauge such as C++ can be treated as an infinite set of operators
> (all of them acting on a one biiiiiiiiig ADT - the program state  :-)).
> But such a treatement as dry as Sahara during hot summer.

Any idea why the words "undereducated demagogue" are lingering in my
mind?

--
  Jan Hidders

  CREATE TABLE Movies (
         Title                Movie_Title        NOT NULL,
         Release           DATE                NOT NULL,
         Showing_For  Period                NOT NULL,
         Cinema           ST_POINT        NOT NULL,
         Clip                Video                 NOT NULL
                    ( PRIMARY KEY ( Title, Release ) )
   );

    Abstract Data Types are things like 'Movie_Title', Period, ST_Point, Video etc.
None of these things is likely to be present in a DBMS product as it installs.
There are likely to be a great many of them (spatial, temporal, mathematical,
document, digital signal, etc) and many are application specific (two strings, "The
Sting" and "Sting, The" are equivalent "movie titles" but are not the same
VARCHAR(64) strings) or algorithmically specialized (geographic projection, compare
finger-prints, etc).

   The idea is that each of these "things" can be modeled (pretty much) as an
object-class. There are already standards for embedding Java classes into modern
DBMS products (SQL-J) and for surfacing the methods implemented in this class as
expressions in the query language. Thus:

   SELECT M.Title, M.Release_Date
       FROM Movies M, Stars S
    WHERE S.Name = new PersonName ("Bergman", "Ingrid")
          AND Face_In_Video ( M.Clip, S.Mug_Shot)
          AND new Circle ( M.Cinema, "10 Miles").Contains( new ST_Point (:X, :Y))
          AND M.Showing_For::Overlaps ( CURRENT )
    ORDER BY 2, 1;

     +--------------+--------+
     |  'Casablanca'  |   1941  |
     +--------------+--------+

   "Show me movie titles and release dates for movies showing currently within 10
miles of lat/long (:X, :Y) where a face like Ingrid Bergman's appears in the clip."

    Queries very like this (syntax varies) actually run efficiently in a least my
company's DBMS, and I'm told can be made to work OK in DB2 and shortly (within a
year) Microsoft's SQL Server.

Quote:

>  CREATE TABLE Movies (
>         Title                Movie_Title        NOT NULL,
>         Release           DATE                NOT NULL,
>         Showing_For  Period                NOT NULL,
>         Cinema           ST_POINT        NOT NULL,
>         Clip                Video                 NOT NULL
>                    ( PRIMARY KEY ( Title, Release ) )
>   );

>    Abstract Data Types are things like 'Movie_Title', Period, ST_Point, Video etc.
>   The idea is that each of these "things" can be modeled (pretty much) as an
>object-class. There are already standards for embedding Java classes into modern
>DBMS products (SQL-J) and for surfacing the methods implemented in this class as
>expressions in the query language. Thus:

>   SELECT M.Title, M.Release_Date
>       FROM Movies M, Stars S
>    WHERE S.Name = new PersonName ("Bergman", "Ingrid")
>          AND Face_In_Video ( M.Clip, S.Mug_Shot)
>          AND new Circle ( M.Cinema, "10 Miles").Contains( new ST_Point (:X, :Y))
>          AND M.Showing_For::Overlaps ( CURRENT )
>    ORDER BY 2, 1;

>     +--------------+--------+
>     |  'Casablanca'  |   1941  |
>     +--------------+--------+

Cool. Is it real Informix sql shell output?

Quote:

>   "Show me movie titles and release dates for movies showing currently within 10
>miles of lat/long (:X, :Y) where a face like Ingrid Bergman's appears in the clip."

>    Queries very like this (syntax varies) actually run efficiently in a least my
>company's DBMS, and I'm told can be made to work OK in DB2 and shortly (within a
>year) Microsoft's SQL Server.

Are you requiring application developer to write custom indexes for Contains and
Overlaps operators, or you reuse R-tree? How about Face_In_Video, is there some
well known technique that you can reuse as well? In general, is writing custom
indexes for abstract datatypes covered by SQL-J standard?

Paul,

Thanks for the succinct explanation.  I've also downloaded the
Extended Relational Technology white paper from the Informix Web site.
This is pretty neat technology.

http://www.informix.com/informix/whitepapers/u2.html

Robert Schiller

  Not quite:

   SELECT M.Title, M.Release_Date
      FROM Movies M, Stars S
    WHERE S.Name = PersonName ("Bergman", "Ingrid")
      AND Contains ( ST_Circle ( M.Cinema, Miles_to_Degrees ( 10 ) ),
                                ST_Point  (:X, :Y))
      AND Overlaps ( M.Showing_For, CURRENT )
    ORDER BY 2, 1;

  Runs just fine. (I know of a couple of "face recognition" extenders, more notably
the "Face It!" technology, but as it does not support an indexing method at this
time it would be kind of crummy for this. The query would run, but it would take
it's sweet time. Watch this space. . .)

  Note also the use of the functional notation, rather than the object dot
notation. I refuse to enter into discussions about which one is "better" and refer
all interested readers to comp.lang.lisp for a good thrashing.

Quote:> Are you requiring application developer to write custom indexes for Contains and
> Overlaps operators, or you reuse R-tree? How about Face_In_Video, is there
> some well known technique that you can reuse as well?
> In general, is writing custom indexes for abstract datatypes covered by
> SQL-J standard?

   No - you use the R-Tree for spatial and temp*overlaps operations.

  Indexing Face_In_Video() is an interesting research problem. Note also that in
the original query, this is a *join* predicate. Nested looping ain't gonna cut it.
There are a number of open ideas in this space. I will get back to you (in a year
or two. . .)

  Yes and no. You can use Java to implement extensions (read: ADTs). And the
methods in your Java classes can be used to specialize a B-Tree (you add a
compare()) or an R-Tree (set of support functions). For example, in the second  I
take a PersonName()  Java class and create a SQL ADT that maps to the one in this
query. The ST_FooBar() functions are taken from the ESRI SQL DataBlade (which is
set up to use the R-Tree) and this language reflects the SQL-3 standard.

  In theory, you could implement a complete access method using Java, but I really
would not recommend it. A GiST interface will be available in the 9.3 release (Hi
Joe!).

  For more information, you might consult either (shameless plug alert) my books,
Jacque Roy's book, or the forthcoming "Open-Source" book several INFORMIX folk are
collaborating on. Look 'em up on http://www.veryComputer.com/

sum,avg,min,max,count,exists <= Reduce
+,-,*,/ <= to use it we need just Map(possibly Project first) on standard
ops in the (presumably)Real domain
I guess why you consider `while...do...' and assignments to belong
to relational ADT spec? (and what is it *really* needed for

Quote:> Unfortunately you are on a wrong way, for two reasons.
> First, some of you operations, e.g. select, are indexed by a predicate.
> Considering select an ADT operation it must have a predicate as an argument.
> Hence at least it is a second-order operator. If the predicate uses
> the other ADT operators, it means some unacceptable mix of language and
> metalanguage levels. Imagine this practically: you are a programmer
> who is trying to implement the select operator as a piece of a program.
> Your program takes the predicate text as a parameter, parses and
> compiles it, generates its code, executes and then discovers that
> this parameter refers to the select operator. Is such a recursion sound?

Usually such `recursions' are not real, e.g. can be eliminated
(for _logical_ purposes) by doing finite number of Joins first,
and computing on the result later on. And what is wrong with ADT whose operators
have functional parameters(predicate is boolean function)?
As a functional programmer I used them often.

Quote:> Unfortunately not.
> Gurus from the polymorphic programming languages camp sadly confess
> their polymorphisms are not sufficiently powerful to write e.g.
> generic procedures for join, select and other relational operators.

For currently used languages you are right. But that's because
they are not usually used for DB programming. Type system for expressing
join and record concatenation is perfectly feasible(ref: A.Ohori, P.Buneman
"Type inference in a database programming language" 1988,
but so many people reinvented similar systems for records,
that interesting idea would be asking Type Theory student to generate
such system "on the fly").

                Greetings :-)
        Michal Gajda

                                *knowledge-hungry student*