"Exactly one" in Relational Algebra

Question

Assume relational database schema

PEOPLE = {ID, Lastname, Firstname}
CAR = {PID, Color}
FK PID ⊆ PEOPLE{ID}

The relational algebra I used is from Fundamentals of Database Systems, 7th Edition (Global Edition), R. Elmasri and S. Navathe, 2017.

I want to query that the Lastname and Firstname of people who have exactly one Car in Blue.

It should be something like

π FirstName,LastName (
    σ (Color =′Blue′)∧(Count=1) (
        PEOPLE ⋈ (ID=PID) CAR
        )
    )

I don't know whether there is Count in Relational Algebra.

Answer 1

I don't know whether there is Count in Relational Algebra.

Let's start from here.

Relational Algebra (RA) as originally defined by Codd (basically, what is shown in the Table 8.1 you've posted—plus renaming) is as expressive as First-Order Logic (FOL). That's one of Codd's fundamental contributions (Relational Completeness of Data Base Sublanguages, 1972).

It is known that FOL has limited counting capabilities. Without entering into too many formal details, it is enough to know that in FOL (with equality) you can say “there are up to k elements…” and “there are at least k elements…” for a fixed k. Let's see a couple of examples of the latter, which is easier to grasp:

• “there is (at least) one element in the domain” is ∃x.x=x
• “there are at least two (distinct) elements in the domain”: ∃x∃y.x≠y
• “there are at least three (distinct) elements in the domain”: ∃x∃y∃w.x≠y ∧ y≠w ∧ w≠x

etc. “There are at most k elements” is then equivalent to “It is not true that there at least k+1 elements” (i.e., the negation of one of the formulas above).

You can then express that “there are exactly k elements”, because that's equivalent to “there are at least k elements and it is not true that there are at least k+1 elements”.

Note that k is fixed priori: different k require writing different formulas (note that the higher the count the more quantifiers you need). The same phenomenon happens in RA (see below): the higher the count, the more (copies of) relations you need.

Incidentally, you cannot count arbitrarily in FOL. You cannot express something like “the domain has even cardinality” or “the number of elements with property P is the same as the number of elements with property Q (no matter how many of them there are)”.

Given Codd's result, if something can be expressed in FOL then it can be expressed in Codd's RA. And if something cannot be expressed in FOL, then it cannot be expressed in Codd's RA.

So, since you can express “there is exactly one element” in FOL, then you can definitely do so in RA. How? In the same way: “there is at least one… and there do not exist two or more…”.

Let's see how all that applies to your example: we need to find the names of people of have at least one car, but who do not have at least two cars. First, finding the names of people who have at least one car is easy (in what follows, I use <- as assignment to split the query into simpler steps, and assign arbitrary names A, B, etc. to the intermediate relations):

A <- п FirstName,LastName (PEOPLE ⨝{ID = PID} CAR)

Next, how do we find people that do not have at least two cars? When a query has a condition with a negation or a universal (“…such that there are not…”, “…such that for all…”), you'd better answer the query with the negated, existential, condition (“…such that there are…”, “such that there exists… not…”) and then take a difference.

So, we first solve: “people who do have at least two cars”. This is an existential statement, and pretty easy to express with joins in RA:

CAR' <- RENAME {C_PK -> C_PK', PID -> PID', Color -> Color'}(CAR)  # CAR' is a copy of CAR with primed attributes
B    <- CAR ⨝{C_PK ≠ C_PK' ∧ PID = PID'} CAR'                      # People with at least two cars
C    <- п FirstName,LastName (PEOPLE ⨝{ID = PID} B)                # Names of people with at least two cars

Note that I have added an attribute C_PK to CAR playing the role of the primary key. Every relation must have a primary key, and {PID, Color} obviously doesn't work for CAR (how would someone own two red cars, otherwise?). I won't comment further on that, to focus on the specific question.

Note also that it would be trivial to change the above query to find people who own at least three/four/five… cars: just make more copies of CAR and join them as in B (look carefully at the parallel between the inequalities in B and the inequalities in the FOL formulas for “there are at least k…” above).

Now, the people who do not have at least two cars are all the people except those who own at least two cars. That's now trivial to compute (RA difference plays the role of logical negation):

D <- (п FirstName,LastName (PEOPLE)) - C

Therefore, the people who own exactly one car are those in A ∩ D (people who own at least one car and do not own two cars or more—intersection plays the role of logical conjunction).

This query can be optimized, but that's left as an exercise.

To wrap it up:

I don't know whether there is Count in Relational Algebra.

Not in RA as originally defined by Codd (the algebra we have used in this exercise). You can still count to some extent, as I hope I have clarified above.

But RA can be extended to increase its expressivity, and many theoreticians and books have done so (the book you cite does so, IIRC). Hence, you will find descriptions of RA which include count() functions, group-by operators, etc. The extensions are mostly motivated by the desire to study the theoretical properties of practical languages such as SQL. For instance, in SQL you can build a (one row by one column) table whose content is the number of records in some table. You cannot do that in Codd's RA. But you can do it in a version of RA extended with the equivalent of SQL count().