Candidate and Superbook

Given the pattern of relations R with n attributes R (A1, A2, ..., An). What is the maximum number of possible super keys for R? Please confirm your answer.

Given the pattern of relations R with n attributes R (A1, A2, ..., An). What is the maximum number of possible candidate keys for R? Please confirm your answer.

I'm still wondering how to answer both of these questions. What I considered the answer to the first question would be (2 ^ n) - 1, because an empty set is not included.

Regarding the second question. My answer would be n attributes.

What do you guys think?

+5
source share
2 answers

The maximum number of superglue in relation to n attributes will be the number of all possible combinations of attributes. This turns out to be (2 ^ n) -1.

It is nothing but acceptance

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

Or we can just think of it this way: we have each of the n attributes represented as bits. We can supply 1 when the attribute should be part of the supercline or 0 otherwise. So it will be (2 ^ n), because we have two options (1 or 0) for each of n bits / attributes. We subtract 1 to avoid all 0, which treats the "no-attribute" as a superkey. So, (2 ^ n) -1.

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

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

The superclasses would be 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 keys of size -r, where nCr is the largest. Or, in other words, when all combinations of size-r attributes are candidate keys, the maximum number of potential keys occurs.

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

In general, nCfloor (n / 2) is the maximum number of candidate keys for a relationship with respect to n attributes.

PS: this considers the definition that a candidate key is a minimal superkey (one of which cannot be removed by any attribute, while leaving it possible to uniquely identify / functionally determine all other attributes)

+1
source

The maximum number of superglue for R with n attributes is 2 ^ n, which is the size of the attribute power set of R. This is obvious when you realize that ∅ (an empty set) can be a candidate key and that ∅ is a subset of each attribute set.

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

+1
source

Source: https://habr.com/ru/post/1245411/


All Articles