Re: relational algrabra division?

On Sunday, December 21, 2014 1:53:15 PM UTC-8, James K. Lowden wrote:
> On Sun, 21 Dec 2014 00:25:14 -0800 (PST)
> compdb wrote:
>
> > the whole idea of relational division is a bit dubious and it is much
> > better to approach queries of the kind that it is used for plus
> > queries of a more general kind via relation inequalities and "image
> > relations".
>
> How "dubious", exactly?

It turns out that there are many special cases of "division", ie "forall/forsome/forno" queries that can reasonably be called "division", with two, three and four operands. However they are not all special cases of one operator. It turns out that it is simpler to construct such queries from (in)equalities, semiijoin and projection, and particulary from image relations.

(Eg: Elmasri & Navathe's DIVIDE is actually Date's (unintentionally) abridged (special case) version of Codd's DIVIDE.)

See the Chapter 12 A Brief History of the Relational Divide Operator & Chapter 14 Image Relations (both with appendices) of http://www.dcs.warwick.ac.uk/~hugh/TTM/Database-Explorations-revision-2.pdf :

> The only references to "image relation" I've
> been able to find come from CJ Date.

I put it in quotes because it is Date's term for certain relations with id.

> So far as I understand them, image relations are *defined* as
> relational dividends.

No. An image relation is what is reasonably described as the image of a tuple in a relation. For division queries the tuple and relation are in a certain context.

Date happens to have special syntax "!!s" inside the wff of r-WHERE-wff for the image of a tuple of r in s. The fact that he has special notation is beside the point. It is short for (s JOIN RELATION{<r1 r1,...>}) PROJECT_OUT {r1,...}. He used to have a special syntax "MATCHING s" for s SEMIJOIN RELATION{<r1 r1,...>} but it turns out not to be as useful/clear. The idea is that s maps <r1 r1,...> to (a relation containing) some subtuples in s.

> If anything, it's more a case
> for set-equality as a language feature.

Having relation (in)equality does not of itself suggest that

> > the whole idea of relational division is a bit dubious and it is much
> > better to approach queries of the kind that it is used for plus
> > queries of a more general kind via relation inequalities and "image
> > relations".

philip Received on Mon Dec 22 2014 - 08:02:15 CET