Re: Question on Structuring Product Attributes

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.

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

Coming back to Codd's quote, the point is that he expected, and most probably encouraged, the development of different (and, it is fair to assume, not expressively equivalent) query languages. So, in no way that quote can be interpreted as “first-order logic is all we need (for normalized databases)”.

Nicola Received on Sat Oct 05 2013 - 17:48:36 CEST