# Re: header part of the value?

Date: Thu, 28 Feb 2008 13:38:54 -0800 (PST)

Message-ID: <efac66c1-e277-4b02-83df-8b6da6d95fa7_at_d4g2000prg.googlegroups.com>

On 28 feb, 22:27, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:

> On Feb 28, 1:16 pm, Jan Hidders <hidd..._at_gmail.com> wrote:

*>
**>
**>
**> > On 28 feb, 21:58, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
**>
**> > > On Feb 28, 11:35 am, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
**>
**> > > > Let me reiterate the generalized relation idea one more time, on a
**> > > > level perhaps more digestable for wider audience. Consider classic
**> > > > relation
**>
**> > > > "The person first name is ..."
**>
**> > > > Normally, we don't write the whole sentence in the relation header (we
**> > > > focus exclusively on named perspective, of course) and abbreviate it
**> > > > to just
**>
**> > > > Name
**> > > > -----
**> > > > Scott
**> > > > Mike
**>
**> > > > The concept of domain has been introduced to resolve questions weather
**> > > > this relation is allowed to be joined with something like
**>
**> > > > "The ship name is ..."
**>
**> > > > All we do when allowing generalized relations is admitting predicates
**> > > > like this:
**>
**> > > > "The variable x is greater or equal than ..."
**>
**> > > > and insisting that the whole sentence matters as a relation header.
**>
**> > > Here is little more background. The inspirational paper is Grumbach&Su
**> > > "Finitely Representable Databases". They introduced the concept of
**> > > finite representativity, for example the relation {x:x>=0} is not
**> > > finitely representable as a classic relation on infinite domain, but
**> > > is finitely representable in more general sense. However, after few
**> > > pages they lost me: I can't understand where are they heading with
**> > > this idea, why compactness theorem, Ehrenfeuht-Frausse gaimse and
**> > > PTIME matter. From practical perspective, one would think the first
**> > > thing they should discuss is an algebra to conveniently operate these
**> > > finite representations.
**>
**> > The complexity and computability results indicate to which extent such
**> > an algebra is possible and/or useful. Besides, why do you think such
**> > an algebra is necessary? What is necessary is that you can ask queries
**> > and that there are algorithms to compute them. An algebra is just one
**> > possible solution for that.
**>
**> > > Anyway, returning to the example
**>
**> > > Q:
**> > > x + 3 = y \/
**> > > x + 5 = y
**>
**> > > Is it binary or unary relation? Sure it is a binary relation Q(x,y) in
**> > > classic sense, but it is not finitely representable!
**>
**> > Why do you think it is not finitely representable?
**>
**> Sure, there is infinite number of tuples in
**>
**> Q(x,y) = {(x,y) | exists t in N such that x = t and (y = t + 3 or y =
**> t + 5)}
*

That does not mean it is not finitely representable. Or are you using a different definition than Grumbach and Su?

- Jan Hidders