Re: Question on Structuring Product Attributes
Date: Mon, 7 Oct 2013 00:10:55 +0200
Message-ID: <5251dfef$0$574$e4fe514c_at_dreader34.news.xs4all.nl>
On 2013-10-05 15:48:36 +0000, Nicola said:
> In article <524d7370$0$618$e4fe514c_at_dreader34.news.xs4all.nl>,
> Jan Hidders <hidders_at_gmail.com> wrote:
>
>> On 2013-10-02 18:55:36 +0000, Nicola said:
>>
>>> In article <1601143370402385874.040013hidders-gmail.com_at_news.xs4all.nl>,
>>> Jan Hidders <hidders_at_gmail.com> wrote:
>>>
>>>> Derek Asirvadem <derek.asirvadem_at_gmail.com> wrote:
>>>>> This one should not pass unnoticed.
>>>>>
>>>>> On Monday, 18 February 2013 09:09:15 UTC+11, Eric wrote:
>>>>>>
>>>>>> To quote from Codd[1970]:
>>>>>>
>>>>>> "A firstorder predicate calculus suffices
>>>>>> if the collection of relations is in normal form."
>>>>>
>>>>> Codd specifies what that Normal Form is, that reference is not merely a
>>>>> generic or general term.
>>>>
>>>> Indeed. Also note that Codd's claim is not unproblematic. Even if you
>>>> restrict yourself to the flat relational model, first order logic cannot
>>>> express many practical queries. So what exactly does he mean by
>>>> "sufficient" here?
>>>
>>> I interpret that quote as follows: "If we allow relations as attribute
>>> values,
>>> we need (at least) a second-order relational calculus". In this sense,
>>> first-order logic "suffices" when relations are "flat" (we don't need to
>>> quantify over relations). Of course I agree with you, many interesting
>>> queries
>>> cannot be expressed in FOL, but you can always design a query language with
>>> additional power (SQL is an example).
>>
>> Agreed, that is indeed probably what he meant. But I guess I'm trying
>> to argue how weak that argument actually is. Sure, keeping things
>> first-order looks like something that keeps it simple, but does it
>> really? If you need extensions anyway, how bad then, relatively
>> speaking, is it to move to a higher-order setting?
>
> Loosely speaking, the complexity, measured as a function of the size of the
> database (the so-called “data complexity”), of answering a query of relational
> calculus is in L (solvable in deterministic logarithmic space), so it is
> tractable. If the query language is extended with existential second-order
> quantification, the problem becomes NP-complete. Adding only transitive
> closures
> makes the problem complete for NL (still in P). These results (and others) can
> be found in “The complexity of relational query languages” by M. Vardi. This
> should partially answer your latter question.
I'm a little bit insulted that you think I did not know that. :-) There are similar results for the Nested Relational Calculus, so I do not see that as a very convincing reason to stick to a first order data model. But maybe that's not what you meant.
> As for the former, one may argue, for example, that modal logics usually have a
> better balance between expressivity and good computational properties, compared
> to first-order logic. But I don't know how far the argument can be carried in
> the context of databases (there is some work by Reiter, however, using some
> modal logic to express integrity constraints).
Computational complexity is not the only thing that determines where a database query or integrity language is an effective one. I'm not saying these results do not matter or should not be taken into account when desiging these languages, but ultimately the proof of the pudding is in the eating, not in theorizing about it.
- Jan Hidders