Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Wed, 18 May 2005 17:36:22 GMT
Message-ID: <q2Lie.94559$FU6.5599349_at_phobos.telenet-ops.be>
>>Simon Taylor wrote:
>>>In article <1116283418.903814.273940_at_f14g2000cwb.googlegroups.com>, Mikito Harakiri wrote:
>>>>Jan Hidders wrote:
>>>>
>>>>>The way that function symbols are interpreted in Prolog and what gives
>>>>>them their expressive power in combination with recursion is more like
>>>>>what you would call a tuple constructor. So a term like f(x,y)
>>>>>represents a binary tuple with fields x and y and a label f that
>>>>>distinguishes it from g(x,y). So a better analogue would be user-defined
>>>>>record types where the type system allows arbitrary deep nesting or
>>>>>recursive types.
>>>>
>>>>I'm not sure I see the significance of nesting, although I seem to get
>>>>a feeling why genericity of record type is a big deal.
>>>
>>>Nesting is not significant; it's allowing data structures to express
>>>choice that increases the expressive power.
>>
>>I tend to disagree. Choice by itself can always be flattened, but
>>arbitrary deep nesting cannot, so it does matter for the expressive
>>power of the query language.
Date: Wed, 18 May 2005 17:36:22 GMT
Message-ID: <q2Lie.94559$FU6.5599349_at_phobos.telenet-ops.be>
Simon Taylor wrote:
> In article <30pie.93684$yc.5551208_at_phobos.telenet-ops.be>, Jan Hidders wrote:
>>Simon Taylor wrote:
>>>In article <1116283418.903814.273940_at_f14g2000cwb.googlegroups.com>, Mikito Harakiri wrote:
>>>>Jan Hidders wrote:
>>>>
>>>>>The way that function symbols are interpreted in Prolog and what gives
>>>>>them their expressive power in combination with recursion is more like
>>>>>what you would call a tuple constructor. So a term like f(x,y)
>>>>>represents a binary tuple with fields x and y and a label f that
>>>>>distinguishes it from g(x,y). So a better analogue would be user-defined
>>>>>record types where the type system allows arbitrary deep nesting or
>>>>>recursive types.
>>>>
>>>>I'm not sure I see the significance of nesting, although I seem to get
>>>>a feeling why genericity of record type is a big deal.
>>>
>>>Nesting is not significant; it's allowing data structures to express
>>>choice that increases the expressive power.
>>
>>I tend to disagree. Choice by itself can always be flattened, but
>>arbitrary deep nesting cannot, so it does matter for the expressive
>>power of the query language.
> > How can you have arbitrarily deep nesting without choice? > At some point you have to choose to stop nesting.
You don't need variant records for that, if you have a set-type you can at some point decide to have an empty set, but I suppose that if you stretch the concept a little you could argue that his is also some form of "choice". Anyway, you seemed to imply (and I denied) that just having choice is *sufficient* to increase the expressive power which is of course not the same as claiming that it is *necessary*.
- Jan Hidders