CODEWITHSUNDEEP
databasefunctional-dependencies
Tomwa
Tomwa

Reputation: 196

Maximal Number of Functional Dependencies (including trivial)

In a relationship R of N attributes how many functional dependencies are there (including trivial)?

I know that trivial dependencies are those where the right hand side is a subset of the left hand side but I'm not sure how to calculate the upper bound on the dependencies.

Any information regarding the answer and the approach to it would be greatly appreciated.

Upvotes: 1

Views: 2699

Answers (1)

Mike Sherrill 'Cat Recall'
Mike Sherrill 'Cat Recall'

Reputation: 95612

The maximum possible number of functional dependencies is

  • the number of possible left-hand sides * the number of possible right-hand sides

We're including trivial functional dependencies, so the number of possible left-hand sides equals the number of possible right-hand sides. So this simplifies to

  • (the number of possible left-hand sides)2

Let's say you have R{∅AB}. There are three attributes.1 The number of possible left-hand sides is

  • combinations of 3 attributes taken 1 at a time, plus
  • combinations of 3 attributes taken 2 at a time, plus
  • combinations of 3 attributes taken 3 at a time

which equals 3+3+1, or 7. So there are at most 72 possible functional dependencies for any R having three attributes: 49. The order of attributes doesn't matter, so we use formulas for combinations, not for permutations.

If you start with R{∅ABC}, you have

  • combinations of 4 attributes taken 1 at a time, plus
  • combinations of 4 attributes taken 2 at a time, plus
  • combinations of 4 attributes taken 3 at a time, plus
  • combinations of 4 attributes taken 4 at a time

which equals 4+6+4+1, or 15. So there are at most 152 possible functional dependencies for any R having four attributes: 225.

Once you know this formula, these calculations are simple using a spreadsheet. It's also pretty easy to write a program to generate every possible functional dependency using a scripting language like Ruby or Python.

The Wikipedia article on combinations has examples of how to count the combinations, with and without using factorials.

All possible combinations from R{∅AB}:

A->A A->B A->∅ A->AB A->A∅ A->B∅ A->AB∅ 
B->A B->B B->∅ B->AB B->A∅ B->B∅ B->AB∅ 
∅->A ∅->B ∅->∅ ∅->AB ∅->A∅ ∅->B∅ ∅->AB∅ 
AB->A AB->B AB->∅ AB->AB AB->A∅ AB->B∅ AB->AB∅ 
A∅->A A∅->B A∅->∅ A∅->AB A∅->A∅ A∅->B∅ A∅->AB∅ 
B∅->A B∅->B B∅->∅ B∅->AB B∅->A∅ B∅->B∅ B∅->AB∅ 
AB∅->A AB∅->B AB∅->∅ AB∅->AB AB∅->A∅ AB∅->B∅ AB∅->AB∅
  1. Most people ignore the empty set. They'd say R{∅AB} has only two attributes, A and B, and they'd write it as R{AB}.

Upvotes: 0

Related Questions