Re: database design method
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.
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