Primary key in resulting relation from union operation in relational algebra

Question

I have a question regarding the resulting table/relation from a union operation in relational algebra. Does the resulting relation not have a primary key? Or does it return a table with a hidden primary key?

Example: Suppose we take the union of the following two tables:

R1:
id | name
----------
1    a
2    b
3    c

R2:
id | name
----------
1    b
2    c
3    d

Where the attribute "id" is primary key in both relation R1 and R2, now the union of those two will be:

id | name
------------
1     a
1     b
2     b
2     c
3     c
3     d

Now none of the attributes in the resulting relation can be primary key since both id and name contain duplicates. How is this resolved by the DBMS?

Answer 1

By definition the union of two relation contains no duplicates. So it contains at least one candidate key, the composition of all attributes. In your example (id, name) is a candidate key.

DBMS do not "resolve" the issue by assigning a primary key because in almost all DBMS (at least those that use SQL), the union of two tables is a derived table (or a view or a CTE but not a base table) and primary keys⁽¹⁾ can be defined only for base tables (not for views, not for derived tables and not for common table expressions).

Still, the DBMS optimizer is often aware that the derived table that results from a union has no duplicates and that the composition of all attributes uniquely defines a row and may use this fact in subsequent operations on the table (e.g. in a more complex query where the union is joined to or unioned with other tables).

^{(1) : and constraints in general. There is an generalized SQL constraint construction (CREATE ASSERTION) that allows constraints across several tables that could be used for creating a unique constraint on a union but assertions have not been implemented by any major DBMS - probably because it's a very complicated issue. Firebird claims to have them but not sure how well or what the restrictions are.}

Answer 2

It is a bit of a tricky question, because SQL (if that is what you mean by DBMS) deviates a bit from relational algebra. In SQL it is valid to declare a table without any keys:

create table T ( x int );
insert into T(x) values (1),(1);

In R.A. we would not allow such construction. SQL is based on bags, not sets, so there is a number of peculiar phenomena that appears. For example, the union of two tables may have less cardinality than both tables:

select x from T 
union 
select x from T

Therefor it is difficult to use SQL to reason about relational algebra.

That said, a relation by definition always have at least one candidate key, namely all attributes. Since relational operations such as union is closed ( i.e. the result is a new relation), the result of the union always have at least one candidate key, in your case {id, name}. In SQL this is not true.

I can't recall any algorithm that determines a minimal candidate key given two relations and a relational operation, perhaps someone else can?

Answer 3

In theory every relation should have one or more candidate keys. In implemented RDBMSs, however, there are no requirements to declare any keys at all. As the result of any query, such as your UNION example, is just another table it follows that the system need not create a key for the result-table.

Take for an example the query

select order_date from orders;

It is likely that there will be at least one day with more than one order and hence no candidate key. And yet the output of this query is a perfectly good table. It can be persisted, joined to or selected from as any other table could.

When the optimiser is creating the execution plan it is most likely that it is considering whether available indexes are unique and the order specified in those indexes (depending on DBMS and options set). As the plan is executed rows are processed one-at-a-time so uniqueness is not an issue. Any intermediate results sets are just treated as a bucket of rows. (There's lots of complexity in there; it's very interesting; much good information in blogs.) Although temporary structures may be created to facilitate processing none make it through to the end result set returned to the client.

Note that sometimes rows will be made unique on disk as a processing optimisation. For example SQL Server will add a uniquifier (love that word) to a non-unique clustered index. This is to do with how they have implemented other indexes on the same table and not a requirement of relational theory per se.