Re: header part of the value?

On 28 feb, 22:50, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
> On Feb 28, 1:16 pm, Jan Hidders <hidd..._at_gmail.com> wrote:
>
> > The complexity and computability results indicate to which extent such
> > an algebra is possible and/or useful.
>
> I was always skeptical of such work; maybe, the reason is that NP
> completeness is not a part of standard math curriculum? NP complete
> problems are all over the place in theoretic world, yet often a tiny
> practically meaningful restriction of the model creates a wholly
> different situation.

Sure, and lots of research goes into finding those special cases. The point is that algebras like the standard flat relational algebra stay well within LOGSPACE. So if the queries you want to deal with are NP hard or harder then it is very unlikely that you can come up with a similar simple and effective algebra. If you want to do more complex stuff, there is a price to pay. That is one of the reasons why the complexity analysis is important. It tells you whether the usual approach is likely to be effective or not.

• Jan Hidders