Re: header part of the value?

From: Tegiri Nenashi <>
Date: Thu, 28 Feb 2008 12:58:45 -0800 (PST)
Message-ID: <>

On Feb 28, 11:35 am, Tegiri Nenashi <> 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.

Anyway, returning to the example

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! We have to consider it as a finite unary relation

x + ... = y


if we ever hope to be able to operate it in practice. Again, it is challenging to define operations for such relations, this is why I limited the scope to one variable in the attribute and inequality as an operation. Consequently, both the classic relation {x: x>5} and generalized relation



are both unary relations. The difference is that one is finitely representable, and the other is not. The second bonus point of generalized relations is that one can express aggregate operations without artificial constructions like aggregate functions and grouping. Next, generalized relation algebra satisfies relational lattice axioms, so it can be considered as yet another model. And the final observation is that the (total) order on the domain of numbers is consistent with the relation order. Received on Thu Feb 28 2008 - 21:58:45 CET

Original text of this message