Re: Abstract Data Types

> >> 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 Received on Sun Apr 22 2001 - 01:28:34 CEST