Search code examples
relational-algebra

How to find tuples in a table if and only if the tuple appears once?


I have a table:

x | y | z
------------
1 | 1 | *
1 | 1 | *
1 | 3 | *
2 | 2 | *
2 | 3 | *
3 | 4 | *
3 | 4 | * 
3 | 3 | *

What is a relational algebra expression to find tuples in a table if and only if the tuple appears once?

For example, I would like the following (x,y) tuples returned for the table above: (1,3), (2,2), (2,3), and (3,3).

If we imagine the X to be an ID, y to be some date, and z to be some event. I want the (id, date) tuples for people who only went to one event on that date.


Solution

    1. Rename R to S

      S := ρS/R(R)

    2. Join R and S on x,y

      D := R ⋈S.x = R.x ∧ S.y = R.y S

      This squares the number of tuples with a particular value for (x,y). Particularly, if a value for (x,y) appears only once in R, it appears only once in D.

    3. Join R and S on x,y,z

      E := R ⋈S.x = R.x ∧ S.y = R.y ∧ S.z = R.z S

      This basically adds some columns to R. It does not add or remove tuples.

    4. Subtract E from D and project to the attributes of R

      F := πx,y,z(D\E)

      This removes the tuples from D, that where created by joining a tuple from R to the corresponding tuple in S. The remaining tuples are the ones that where created by joining a tuple in R to a different tuple in S. Particularly, if a value for (x,y) appears only once in R, no tuple in F exists with that value.

    5. Remove the tuples in F from R

      R\F