Re: database design method

From: Jan Hidders <hidders_at_REMOVE.THIS.uia.ua.ac.be>
Date: 9 Nov 2002 15:59:11 +0100
Message-ID: <3dcd22bf$1_at_news.uia.ac.be>


Alfredo Novoa wrote:
>On 8 Nov 2002 22:22:30 +0100, hidders_at_hcoss.uia.ac.be (Jan Hidders)
>wrote:
>
>>Not all imperative extensions make it computationally complete.
>
>I thougth you only need a if-then and while-do instructions.

That is not always enough. For example, if you just take the relational algebra (select, project, join, union, difference) and add a while construct (you can simulate the if-then-else with that) it is easy to see that you can only compute queries that can be computed in polynomial space. Morever, it can also be shown that there are some very simple queries, like does this relation contain an even number of tuples, that cannot be expressed in it.

There's a very big and very interesting body of research literature on this subject, and to get an impression of that you might want to take a look at the chapters 16, 17 and 18 from "the Alice book":

  Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases.   Addison-Wesley 1995, ISBN 0-201-53771-0

  http://www.informatik.uni-trier.de/~ley/db/books/dbtext/abiteboul95.html

Note that the book assumes a pretty good formal background in computer science from its readers.

>I always heard that a Turing machine is an example of computationally
>complete "language".

Yes it is, but for computations over strings. If you change your domain of computation to relational databases and you show that you can simulate a Turing machine then you only have shown that on a certain subset of your domain (the part you use to simulate the Turing tape) you are computationally complete, but "computationally complete" means of course that you are complete on the *whole* of your domain. For more information and a formal treatment see chapter 2 of "the Alice book".

  • Jan Hidders
Received on Sat Nov 09 2002 - 15:59:11 CET

Original text of this message