Decomposing tables where some attributes aren't in any minimal, non-trivial functional dependency

Question

While writing a library to automatically decompose a given table, I came across some special cases where the first steps of Bernstein's synthesis for 3NF (ACM 1976) give me results I don't expect.

Take this simple case:

a b
---
1 1
2 1
1 2
2 2

By my understanding, this is the full set of functional dependencies:

{} -> {}
a -> {}
a -> a
b -> {}
b -> b
ab -> {}
ab -> a
ab -> b
ab -> ab

By eye, we can see that both attributes together form a candidate key, and there's no normalisation to be done. However, suppose we take the full FD set above, and try to apply Bernstein to decompose the table. We expect to get the same table back.

Bernstein has the following first steps:

1. Eliminate extraneous attributes. We simplify to

{} -> {} (repeated)
a -> a (repeated)
b -> b (repeated)
ab -> ab

2. Find a non-redundant covering. ab -> ab is redundant by augmentation, so we have

{} -> {}
a -> a
b -> b

I'd say the latter two are redundant as well, by reflexivity. If we keep them, the remaining steps give two non-equivalent keys, which result in two separate relations after applying the rest of Bernstein synthesis. If we don't keep them, there's nothing to work with, so the remaining steps give no tables.

Where is the problem in the above?

Answer 1

This appears to be solved by an addendum to Bernstein's synthesis, that I came across in lecture videos from Gary Boeticcher, then at UHCL: if the decomposition does not contain a table containing one of the original table's candidate keys, then adding an additional table with one of those candidate keys will make the decomposition lossless. In this case, after applying Bernstein's synthesis, and getting no tables in return, we could add a table with both attributes a and b. This gives us back the original table, as we'd expect.