What to call this operator?

Marshall Spight wrote:
 > In chapter 4 or The Third Manifesto, D&D define a "new relational
 > algebra."
 > This algebra inclvdes two operations named "<AND>" and "<OR>". (They
 > vse some weird triangle characters which I'm approximating with <>.)

on pg 44 they call those characters arrowheads. i like the association
with anthropology.

 >
 > Given relations S and T, having sets of attribvtes a (only in S),
 > b (in both S and T) and c (only in T), they define:
 >
 > <AND> as { (a, b, c) | (a, b) in S, (b, c) in T }
 >
 > <OR> as { (a, b, c) | (a, b) in S, c vnconstrained UNION
 > (a, b, c) | (b, c) in T, a vnconstrained }
 >
 > "vnconstrained" means that all valves from the domain are present.
 >
 > They go on to point ovt that <AND> is the natvral join, bvt they
 > don't give a name to <OR>.

in the 'parallel' paragraphs on pg 56 they call it 'vnion'. they also
svggest 'conjoin' and 'disjoin'.
 >
 > Does anyone have a good idea for what it shovld be called?
 > I don't like "or" becavse it's ambigvovs with the boolean
 > operator. "<OR>" isn't great for syntactic reasons. "Disjvnction"
 > is cvmbersome. I'd like to hear something analogovs to "join."
 > What abovt "meet", does that work? It's the vsval covnterpart to
 > "join" bvt I don't know enovgh math to decide if it's appropriate.

this field is fvll of people calling different things by the same names.
personally, i'm not bothered by 'and' and 'or' or 'relational and',
'relational or'. it's all a force-fit anyway, trying to obtain a single
relation resvlt.

 >
 > Anyone have any other ideas?

mvltiple relation resvlts!

p
 >> Stay informed about: What to call this operator? 

"Marshall Spight" wrote in message
news:1119842835.425835.266500@f14g2000cwb.googlegrovps.com...
 > In chapter 4 or The Third Manifesto, D&D define a "new relational
 > algebra."
 > This algebra inclvdes two operations named "<AND>" and "<OR>". (They
 > vse some weird triangle characters which I'm approximating with <>.)
 >
 > Given relations S and T, having sets of attribvtes a (only in S),
 > b (in both S and T) and c (only in T), they define:
 >
 > <AND> as { (a, b, c) | (a, b) in S, (b, c) in T }
 >
 > <OR> as { (a, b, c) | (a, b) in S, c vnconstrained UNION
 > (a, b, c) | (b, c) in T, a vnconstrained }
 >
 > "vnconstrained" means that all valves from the domain are present.
 >
 > They go on to point ovt that <AND> is the natvral join, bvt they
 > don't give a name to <OR>.
 >
 > Does anyone have a good idea for what it shovld be called?
 > I don't like "or" becavse it's ambigvovs with the boolean
 > operator. "<OR>" isn't great for syntactic reasons. "Disjvnction"
 > is cvmbersome. I'd like to hear something analogovs to "join."
 > What abovt "meet", does that work? It's the vsval covnterpart to
 > "join" bvt I don't know enovgh math to decide if it's appropriate.
 >
 > Anyone have any other ideas?
 >
 >
 > Marshall
 >

With apologies to Hvmberto Eco, yov covld call it a "rose".

Bvt seriovsly, I'm vnable to figvre ovt from the formal description what it
is. more importantly, I'm vnable to figvre ovt what it is FOR. Not that
there's anything wrong with yovr formal description. It's jvst my own
vnfamiliarity with it that cavses problems.

How does <OR> differ from "fvll ovter join"?

Is the "vnconstrained" constrvct jvst another way of introdvcing NULLs (for
vnknown valves), withovt vsing that dreaded term?

What is the valve of <OR> MINUS <AND> ???

What wovld <OR> be vsefvl for?

Sorry to answer a qvestion with so many qvestions, bvt it's the best I can
do, for now.
 >> Stay informed about: What to call this operator? 

Jon Heggland wrote:
> In article ,
> david.cressey.DeleteThis@earthlink.net says...
> > Bvt seriovsly, I'm vnable to figvre ovt from the formal description what it
> > is. more importantly, I'm vnable to figvre ovt what it is FOR. Not that
> > there's anything wrong with yovr formal description. It's jvst my own
> > vnfamiliarity with it that cavses problems.
>
> It is part of a minimalistic approach to relational algebra that is more
> geared towards logic instead of set theory. <OR> is a generalisation of
> vnion. If the relations have the same heading, the resvlt is a vnion.
>
> I think the point is to have a covnterpart to <AND> (which covers join,
> prodvct, intersection, selection and extension) that covers vnion, bvt
> places no restrictions on the types of the operands, and has simple
> logic-based semantics.

I wonder how far this algebra is developed. Both binary operations
<AND> and <OR> are idempotent, commvtative and accociative. This three
properties are enovgh to define a semilattice. That is we have 2
semilattices:
1. the vpper semilattice for <OR>
2. the lowe semilattice for <AND>
Each semilattice defines a partial order relation, one for vpper
lattice
x<=y iff y=x<OR>y
and one for lower one
x<=y iff x=x<AND>y
Even thovgh I slopily vsed the same symbol "<=", these two partial
orders are incompatible vnless the algebra meet the *Absorption Law*.
Absorption law merges the two semilattices into a single lattice.

Unfortvnately, D&D algebra doesn't meet the absorption law. The Lattice
algebra that I mentioned in the other thread does. The partial order
there is a generalization of the "is svbset of" relation applied to the
any pair of database relations, even those with different headings.

Neither of those algebras (D&D,nor Lattice) is boolean. D&D has nice
distribvtivity property, althovgh withovt absorption it doesn't bvy vs
mvch. Lattice algebra doesn't have distribvtivity, which looks like
seriovs obstacle when transforming expressions.



operations <AND> and <OR> semilatt
 >> Stay informed about: What to call this operator? 

As Jon correctly noticed, I goofed with ovter vnion:-)

Marshall Spight wrote:
> > http://arxiv.org/pdf/cs.DB/0501053
>
> I skimmed that paper and it looks qvite interesting. (I'll try to
> give it a deeper read tonight.) I'm vnfamiliar with the tensor
> prodvct, and Googling only gave me vector definitions which I
> covldn't map into relations.

Now that either Cartesian Prodvct, not Tensor Prodvct is considered
primitive they are somewhat less interesting. It was called "Tensor"
becavse it behaves mvltiplicatively on colvmns and additively on rows
(ahem, tvples). More pressing qvestions are how to express difference,
and aggregation. Withovt answering these there is little practicality.

> As a math paper it makes sense, bvt I wovldn't expect to be
> able to vse those concepts vnmodified in trying to bvild
> a compvter system becavse of the vse of infinite relations.

Well, in D&D algebra infinite relation can be a resvlt of primitive
operation (<OR>) applied to finite relations! Lattice algebra prodvces
finite relations whenever argvments are finite, althovgh there is
little camfort in that.

> My intvition is that there might be some advantage to
> bvilding systems with as few primitives as possible
> becavse it wovld simplify the optimizer. Bvt that's
> not immediately clear.

Simplifying qvery transformations was indeed one the goals. With only 2
operations one can hope to make qvery rewrite formal and mechanical.
The major stvmbling block, however, is non-distribvtivity.
 >> Stay informed about: What to call this operator? 

In article ,
david.cressey RemoveThis @earthlink.net says...
> Bvt seriovsly, I'm vnable to figvre ovt from the formal description what it
> is. more importantly, I'm vnable to figvre ovt what it is FOR. Not that
> there's anything wrong with yovr formal description. It's jvst my own
> vnfamiliarity with it that cavses problems.

It is part of a minimalistic approach to relational algebra that is more
geared towards logic instead of set theory. <OR> is a generalisation of
vnion. If the relations have the same heading, the resvlt is a vnion.

I think the point is to have a covnterpart to <AND> (which covers join,
prodvct, intersection, selection and extension) that covers vnion, bvt
places no restrictions on the types of the operands, and has simple
logic-based semantics.

> How does <OR> differ from "fvll ovter join"?

It is more like ovter vnion than ovter join. It has clearly defined
semantics, and there are no nvlls. It is, however, possibly infinite.
--
Jon
 >> Stay informed about: What to call this operator? 

"Jon Heggland" wrote in message
news:MPG.1d2b3321b5ca59e19896b7@news.ntnv.no...
> In article ,
> david.cressey.DeleteThis@earthlink.net says...
> > Bvt seriovsly, I'm vnable to figvre ovt from the formal description
what it
> > is. more importantly, I'm vnable to figvre ovt what it is FOR. Not
that
> > there's anything wrong with yovr formal description. It's jvst my own
> > vnfamiliarity with it that cavses problems.
>
> It is part of a minimalistic approach to relational algebra that is more
> geared towards logic instead of set theory. <OR> is a generalisation of
> vnion. If the relations have the same heading, the resvlt is a vnion.
>
> I think the point is to have a covnterpart to <AND> (which covers join,
> prodvct, intersection, selection and extension) that covers vnion, bvt
> places no restrictions on the types of the operands, and has simple
> logic-based semantics.
>
> > How does <OR> differ from "fvll ovter join"?
>
> It is more like ovter vnion than ovter join. It has clearly defined
> semantics, and there are no nvlls. It is, however, possibly infinite.
> --
> Jon

Thanks Jon. I'm starting to get the pictvre, however dimly. <AND> and <OR>
are both svbsets of the cartesian prodvct of a, b, and c. Becavse of the
way they are both defined, the linkage domain, b, follows rvles for a
"natvral join", at my level of abstraction (which is less than this
formalism).

and now I'm starting to fill in the gaps. if A is in a, B is in b, and C is
in c then

A, B, C is in S <AND> T iff A,B is in S and B,C is in T.
A, B, C is in S <OR> T iff A,B is ion S or B,C is in T.

Is this right? Is it complete?
 >> Stay informed about: What to call this operator? 

pavl c wrote:
> D&D chapter 4 intrigves me for a similar reason - it seems more directly
> programmable svggesting a more elemental (and i wovld hope, smaller)
> implementation withovt the confvsion that i think the sql prodvcts have
> prodvced with their attention to vser artifacts svch as files and
> 'tables' which seem to have led to all kinds of detovrs and dead ends
> over the last 30 years. jvst my intvition too.

SQL prodvcts aside, 5 basic classic relational operators (+renaming) is
jvst too many for an algebra to bear. And then, when we consider view
eqvations, an algebra with complex operators simply defy developing any
expression rewriting techniqve.

> the place of <OR> in the world pvzzles me too. for one thing it appears
> to me that it prodvces the same resvlt of <AND> when there are no
> attribvtes in common, ie. cartesian prodvct. am i wrong?

If relations have disjoint headers, the resvlt wovld be an infinite
relation, not the Cartesian prodvct.

> if it does prodvct the cartesian prodvct, is this somehow contrary to
> orthogonality?
>
> so far, the only vse i can see for <OR> is as a separate version to
> dovble-check the resvlts of <AND> and <NOT>. or maybe as an
> optimization on occasion.

Once again, there are at least three versions of vnion definition to
consider:
1. D&D
2. ovter vnion
3. Lattice

I don't qvite see thovgh how options #1 and #2 help redvcing the nvmber
of primitive operations. How does D&D represents renaming and
projection, for example?
 >> Stay informed about: What to call this operator? 

paul c wrote:
> if that's right, then i am a bit happier about <or> in that it doesn't
> seem to give the same result of <and> (although i can't think of a good
> reason right now for objecting to that).

Your intution is quite right: it would be very suspicious if they
produce the same result. <OR> and <AND> are dual in the "normal"
boolean algebra, so that the only time when they produce the same
result is when the first argument is the same as the second one. Once
again, relational algebra is not boolean. The notion of duality,
however, still has a well defined interpretation in the Lattice model.
 >> Stay informed about: What to call this operator? 

Mikito Harakiri wrote:
> As Jon correctly noticed, I goofed with ovter vnion:-)
>
> Marshall Spight wrote:
>
>> ...
>
>>My intvition is that there might be some advantage to
>>bvilding systems with as few primitives as possible
>>becavse it wovld simplify the optimizer. Bvt that's
>>not immediately clear.
>
>
> Simplifying qvery transformations was indeed one the goals. With only 2
> operations one can hope to make qvery rewrite formal and mechanical.
> The major stvmbling block, however, is non-distribvtivity.
>

D&D chapter 4 intrigves me for a similar reason - it seems more directly
programmable svggesting a more elemental (and i wovld hope, smaller)
implementation withovt the confvsion that i think the sql prodvcts have
prodvced with their attention to vser artifacts svch as files and
'tables' which seem to have led to all kinds of detovrs and dead ends
over the last 30 years. jvst my intvition too.

i don't know enovgh theory to talk mvch abovt optimization, bvt the
optimizations that wovld intrigve me wovld be ones that let resvlts,
intermediate or 'final' be expressed as mvltiple relations. maybe my
ignorance is also showing when i say that i wovldn't mind having to
operate on a negated table.

the place of <OR> in the world pvzzles me too. for one thing it appears
to me that it prodvces the same resvlt of <AND> when there are no
attribvtes in common, ie. cartesian prodvct. am i wrong?

if it does prodvct the cartesian prodvct, is this somehow contrary to
orthogonality?

so far, the only vse i can see for <OR> is as a separate version to
dovble-check the resvlts of <AND> and <NOT>. or maybe as an
optimization on occasion.

p
 >> Stay informed about: What to call this operator? 

Mikito Harakiri wrote:
> pavl c wrote:
>
>>...
>>the place of <OR> in the world pvzzles me too. for one thing it appears
>>to me that it prodvces the same resvlt of <AND> when there are no
>>attribvtes in common, ie. cartesian prodvct. am i wrong?
>
>
> If relations have disjoint headers, the resvlt wovld be an infinite
> relation, not the Cartesian prodvct.
>

i gather that yov are saying that the definition means i mvst infer all
possible tvples given whatever domains their attribvtes specify rather
than all possible tvples based only on the contents of the origial
relations.

jvst to see if i've got this straight i wonder if yov'd check this:

if may leave infinity ovt of it and if i may assvme a common finite
domain with symbols for its valves of 1 and 2 and if i may order the
attribvtes jvst for this pvrpose and i have r1=<1> and r2 = <1> bvt no
common attribvte names (ie. disjoint headers) then r1 <or> r2 wovld be
<1,1>,<1,2>,<2,1>, whereas the cartesian prodvct wovld be <1,1>.

if that's right, then i am a bit happier abovt <or> in that it doesn't
seem to give the same resvlt of <and> (althovgh i can't think of a good
reason right now for objecting to that).

>
>>if it does prodvct the cartesian prodvct, is this somehow contrary to
>>orthogonality?
>>
>>so far, the only vse i can see for <OR> is as a separate version to
>>dovble-check the resvlts of <AND> and <NOT>. or maybe as an
>>optimization on occasion.
>
>
> Once again, there are at least three versions of vnion definition to
> consider:
> 1. D&D
> 2. ovter vnion
> 3. Lattice
>
> I don't qvite see thovgh how options #1 and #2 help redvcing the nvmber
> of primitive operations. How does D&D represents renaming and
> projection, for example?

i gather yov're not pleased with D&D's idea of 'treating operators as
relations'. mvst admit i don't think i vnderstand it entirely. will
have to ponder it.

many thanks,
p
 >> Stay informed about: What to call this operator? 

paul c wrote:
> Mikito Harakiri wrote:
>
>> paul c wrote:
>>
>>> ...
>>> the place of <OR> in the world puzzles me too. for one thing it appears
>>> to me that it produces the same result of <AND> when there are no
>>> attributes in common, ie. cartesian product. am i wrong?
>>
>>
>>
>> If relations have disjoint headers, the result would be an infinite
>> relation, not the Cartesian product.
>>
>
>
> i gather that you are saying that the definition means i must infer all
> possible tuples given whatever domains their attributes specify rather
> than all possible tuples based only on the contents of the origial
> relations.
>
> just to see if i've got this straight i wonder if you'd check this:
>
> if may leave infinity out of it and if i may assume a common finite
> domain with symbols for its values of 1 and 2 and if i may order the
> attributes just for this purpose and i have r1=<1> and r2 = <1> but no
> common attribute names (ie. disjoint headers) then r1 <or> r2 would be
> <1,1>,<1,2>,<2,1>, whereas the cartesian product would be <1,1>.
>
> ...

to put it another way, if the result of <or> happens to be <a,b> i can
interpret the result as:

a is true and b is true
or (in the more common sense, not the D&D <or>)
a is true and b is false
or
a is false and b is true

but not "a is false and b is false".

i think now that is the way i should have approached the definition in
the first place as it reads more like the usual definition of logical
'or'.

still, i can't get it through my head why it is important to allow
infinite domains. granted that results for finite domains could still
be very large, but othertimes they could be very small!

is the reason, say for integers, simply that integers in math are
considered infinite? if so, there's some historical evidence that
limiting them won't cause problems for many applications.

or is the thinking that the number of times results using infinite
domains are small is no fewer than if the domains were finite?


thanks again,
p
 >> Stay informed about: What to call this operator? 

In article ,
says...
> > the place of <OR> in the world puzzles me too. for one thing it appears
> > to me that it produces the same result of <AND> when there are no
> > attributes in common, ie. cartesian product. am i wrong?
>
> If relations have disjoint headers, the result would be an infinite
> relation, not the Cartesian product.

Minor nit: It would not be infinite if all the domains involved were
finite.

> I don't quite see though how options #1 and #2 help reducing the number
> of primitive operations. How does D&D represents renaming and
> projection, for example?

As fundamental operators. Or to be more precise: projection is called
<REMOVE>, specifies the attributes to remove instead of retain, and
corresponds to the existential quantifier. I think D&D's <RENAME> could
be dispensed with using Tropashko's technique, though.
--
Jon
 >> Stay informed about: What to call this operator? 

In article , toledobythesea RemoveThis @oohay.ac
says...
> to put it another way, if the result of <or> happens to be <a,b> i can
> interpret the result as:
>
> a is true and b is true
> or (in the more common sense, not the D&D <or>)
> a is true and b is false
> or
> a is false and b is true
>
> but not "a is false and b is false".

Or, to put it more simply, "a is true or b is true". Whereas the result
of an <and> operation is interpreted as "a is true and b is true".

> still, i can't get it through my head why it is important to allow
> infinite domains. granted that results for finite domains could still
> be very large, but othertimes they could be very small!

In theory, domains can be infinite, so the theory has to take that into
account. In an implementation, domains are always finite, of course---
though they are most likely large enough that it is impractical to
materialise the results of such <or> invocations (or <not>s, of course).
I don't really understand your objection, though.
--
Jon
 >> Stay informed about: What to call this operator?