0

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
  1. 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?

Accidental Statistician
  • 350
  • 1
  • 8
  • Your "I have these FDs" doesn't make sense. "These are all the FDs that hold"?--Not possible. "These are all the non-trivial FDs that hold"?--Not possible. "These are some FDs that hold"?--Question can't be answered. Find out what a *cover* is & what the exact conditions are to apply a particular definition/rule/algorithm. To determine CKs & NFs we must be given FDs that form a cover. Sometimes a minimal/irreducible cover. And the set of all attributes must be given. [See this answer.](https://stackoverflow.com/a/53386492/3404097) – philipxy Aug 23 '22 at 11:36
  • When some FDs hold all the ones implied by them per Armstrong's axioms hold. (Including trivial FDs.) PS Look at the exact input of the algorithm. "functional dependencies can't take the form {a, b} -> {}, with an empty dependent set" They can & do, although that happens to be a trivial FD since it is of the form S->{}, {} being a subset of every set. Please quote your version of the algorithm & show justified steps following it until you are stuck so we can show you where you went wrong (& right). There's no point in trying to address your options, the question assumes wrong things. – philipxy Aug 23 '22 at 11:43
  • "this is the set of all the functional dependencies" Again: not possible. Again: **Quote any algorithms and definitions of any non-standard terms**.--Like "minimal FK". (And your paper apparently talks about an algorithm that is not Bernstein's.) We are not reading that paper, and posts need to be self-contained. Again: Justify your claims per published reference! Like what "this is the set of all the functional dependencies". Say why. You have left out the FDs determining {} & other trivial FDs. Talk about FDs holding or not. Again: Please reread & act on everything in my comments. – philipxy Aug 23 '22 at 13:21
  • I've cut the question down to be about the steps for a single simple case, hope this is clearer now. – Accidental Statistician Aug 23 '22 at 17:05

1 Answers1

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.

Accidental Statistician
  • 350
  • 1
  • 8