Candidate and Superkey

Question

Given a relation schema R with n attributes R(A1, A2, ..., An). What’s the maximum number of possible super-keys for R? Please justify your answer.

Given a relation schema R with n attributes R(A1, A2, ..., An). What’s the maximum number of possible candidate keys for R? Please justify your answer.

I am still wondering on how to answer both of these questions. What I have thought as answer for the first question would be (2^n) - 1 because empty set is not included.

As for the second question. My answer would be n atrributes.

What do you guys think?

Manlike

For the second question, consider the definition of a candidate key: it is a subset of the attributes (any subset), such that you cannot remove an attribute from it and still have that the resulting attributes determine all the attributes of the relation. Here the important words for your question are: “any subset”. So, how many (non-empty) subset of attributes there are in R? Instead, the first question is not clear. How many different superkeys? Or the total of the number of possible superkeys for each possible candidate key? – Hypnotic

@Hypnotic i believe that the question is referring to how many different superkeys are there – Manlike

In this case, considering that a superkey is a subset of attributes that datermines all the other attributes, the number of superkeys is equal to the number of candidate keys. – Hypnotic

Candidate key is a minimal superkey. For any relation therefore the number of superkeys must be greater than the number of candidate keys unless there only happens to be one superkey. – Schenck

Answer 1

Maximum number of superkeys on relation with n attributes would be number of all possible combinations of attributes. This turns out to be (2^n)-1.

This is nothing but taking

1 attribute from n (nC1) + 2 attributes from n (nC2) + ... + nCn = (2^n)-1

Or we can simply think it as follows: we have each of n attributes represented as a bit. We can put 1 when an attribute has to be a part of superkey or 0 otherwise. So this will be (2^n), because we have two choices (1 or 0) for each of the n bits/attributes. We subtract 1 to avoid all 0's, that is considering 'no-attribute' as a superkey. So (2^n)-1.

This situation can occur when all attributes can functionally determine all other attributes. This occurs when there is a cycle of functional dependencies among attributes. For example if there is a relation R(A,B,C,D), then the FD cycle would be:

A->B
B->C
C->D
D->A

The superkeys would are A,B,C,D,(AB),(AC),(AD),(BC),(BD),(CD),(ABC),(ACD),(ABD),(BCD),(ABCD), total (2^4)-1=15

The maximum possible number of candidate keys will occur for size-r keys where nCr is biggest. Or in other words, when all size-r combinations of attributes are candidate keys, maximum number of candidate keys occur.

This can be seen from above example. Above A,B,C,D are all candidate keys, so none of their superkeys (say (AB), or (BCD) or (ABCD)) are candidate keys. Similarly if, in any relation (AB) is a candidate key, then none of its superkey (say ABC or ABD) can be a candidate key.

In general, nCfloor(n/2) is the maximum number of possible candidate key for relation on n attributes.

PS: this considers the definition that candidate key is a minimal superkey (one from which no attribute can be removed while still leaving it capable to uniquely identify / functionally determine all other attributes)

Pesce

Good explanations but the answer to the first question is 2^n, not 2^n-1. The empty set of attributes may be a superkey (and by definition a candidate key as well). – Schenck

"The empty set of attributes may be a superkey"!!! How? Can you explain logically and demonstrate technically/practically? – Pesce

∅ is a superkey for any singleton relation. e.g. constant{pi,e,planck}. In practice singleton tables are used for parameters or configuration values, i.e. scalar values that are not dependent on any other value. There are also the two relations DUM and DEE which have no attributes at all and therefore have a key of ∅. – Schenck

So you mean to say (singleton relation = relation without attribute = scalar value) and have ∅ as a superkey? – Pesce

No, @sqlvogel means singleton = with 1 row, empty = without rows & niladic = without attributes. Niladic is singleton/DEE or empty/DUM. DEE's row is the row without attributes. ∅ is a CK iff there is at most one row. If ∅ is a CK it is the sole CK. So all 3 have sole CK ∅. A value's or variable's rows satisfy a predicate (statement template)--A>2. So a singleton's has one solution--A=2; no rows satisfy an empty's --"A <> A"; a niladic's is true-or-false--a proposition (statement)--7>2, 7<2. A variable with at most one row (singleton or empty) has CK ∅--A=2; the door is open. – Atworth

Answer 2

The maximum number of superkeys for R with n attributes is 2^n, which is the size of the power set of R's attributes. This is obvious when you realise that ∅ (the empty set) may be a candidate key and that ∅ is a subset of every set of attributes.

The maximum number of candidate keys is given by nC(n/2) (binomial coefficient).

Schenck