1
$\begingroup$

I read that all binary relations are associative. i.e (p.q).r = p.(q.r). However, I was curious that does this hold if p,q, and r are ternary relationships. I tried several examples, such as the one below, but could not prove that ternary relationaships are NOT associate. So, are they associative or not

p = {(a,b,c) , (f,o,x)} q = { (f,d,e), (x,o,c) } r = { (e,t,o), (c,t,s)} 

The output for (p.q).r and p.(q.r) in both cases is {(f,o,o,t,s)}

  • 0
    So. How did you get this 5-tuple $(f,o,o,t,s)$?2012-11-02

2 Answers 2

1

If you want to talk about associativity, then probably what you are interested in is binary operators rather than binary relations.

Recall that a binary operator is something that takes in two inputs, and gives out a single output. Note that this must all be done with a particular set in mind.

For example, if your set is the natural numbers $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$, then addition, $+$, is a binary operator: given two natural numbers, $m$ and $n$, their sum, $m+n$, is also a natural number.

It is not true, however, that all binary operators are associative. For example, subtraction is a binary operator on the integers, but it is not associative: $10-(9-8) \neq (10-9)-8$, since the left hand side is $9$ and the right hand side is $-7$ (and clearly $9 \neq -7$).

Similarly, one can define a ternary operator that takes in three inputs, and gives out a single output. As with binary operators, there is no guarantee that a ternary operator will be associative.

If the above does not answer your question and, in fact, you have other restrictions in mind when you refer to "ternary relationships," please make them explicit.

0

For ternary relations, you can either use indexed or named perspective. Indexed perspective is the standard math where attributes are indexed with consecutive integer numbers. Unfortunately, it is not obvious what is the analog of composition operation (aka relative multiplication). However, one logic application -- namely, database theory -- has developed alternative, quite compelling perspective. There each attribute is equipped with name. Relational join projected to the set of distinct relation attributes is generalization from binary case. The associativity counterexample is the following:

z = [p  r  s]      0  0  s      0  1  s      0  2  s      1  2  l      2  0  s      2  2  s      3  2  l  y = [p  q  s]      0  c  s      1  c  l      2  b  s      3  a  l  x = [p  q  r]      0  a  0      0  a  1      1  c  0      1  c  1      2  a  0 

Intermediate evaluations:

x;y=[r  s]      0  l      1  l  (x;y);z=[p]  y;z=[q  r]      a  2      b  0      b  2      c  0      c  1      c  2  x;(y;z)=[p]          1 

Yes, composition of ternary relations in database theory is not closed (it doesn't produce a ternary relation). Relational algebra is algebra of relations with mixed dimensions.