Re: Abstract Data Types

Kazimierz Subieta wrote:
>
> > >> 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... ?

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.

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

Like I said, computational completeness is not a requirement for a good ADT.
> 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.

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

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

> 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