Lecture number 9. Functional dependencies

1. Restriction of functional dependence

The uniqueness constraint imposed by the primary and candidate key declarations of a relation is a special case of the constraint associated with the notion functional dependencies.

To explain the concept of functional dependency, consider the following example.

Let us be given a relation containing data on the results of a particular session. The schema of this relationship looks like this:

Session (record book number, Full Name, Subject, Grade);

The attributes "Gradebook number" and "Subject" form a composite (since two attributes are declared as a key) primary key of this relation. Indeed, these two attributes can uniquely determine the values ​​of all other attributes.

However, in addition to the uniqueness constraint associated with this key, the relation must necessarily be subject to the condition that one grade book is issued to one specific person and, therefore, in this respect, tuples with the same grade book number must contain the same values ​​of the "Last Name" attributes , "First and middle name".

If we have the following fragment of a certain database of students of an educational institution after a certain session, then in tuples with a gradebook number of 100, the attributes "Last name", "First name" and "Patronymic" are the same, and the attributes "Subject" and "Evaluation" - do not match (which is understandable, because they are talking about different subjects and performance in them). This means that the attributes "Last Name", "First Name" and "Patronymic" functionally dependent on the attribute "Gradebook number", while the attributes "Subject" and "Evaluation" are functionally independent.

In this way, functional dependency is a one-to-one dependency tabulated in database management systems.

We now give a rigorous definition of functional dependence.

Definition: let X, Y be subschemes of the scheme of the relation S, defining over the scheme S functional dependency diagram X → Y (read "X arrow Y"). Let's define functional dependency constraints inv<X → Y> as a statement that, in relation to schema S, any two tuples that match in projection onto subschema X must also match in projection to subschema Y.

Let's write the same definition in formula form:

Inv<X → Y> r(S) = t₁, T₂ ∈ r(t₁[X] = t₂[X] ⇒ t₁[Y]=t₂ [Y]), X, Y ⊆ S;

Curiously, this definition uses the concept of a unary projection operation, which we encountered earlier. Indeed, if you do not use this operation, how else can you show the equality of two columns of the relationship table, and not rows? Therefore, in terms of this operation, we wrote down that the coincidence of tuples in the projection onto some attribute or several attributes (subschema X) necessarily entails the coincidence of the same tuple columns on subschema Y in the event that Y is functionally dependent on X .

It is interesting to note that in the case of a functional dependence of Y on X, one also says that X functionally defines Y or what Y functionally dependent on X. In the X → Y functional dependency scheme, subcircuit X is called the left side, and subcircuit Y is called the right side.

In database design practice, functional dependency schema is commonly referred to as functional dependency for brevity.

End of definition.

In a particular case, when the right side of the functional dependency, i.e., the Y subschema, matches the entire relation schema, the functional dependency constraint becomes a primary or candidate key uniqueness constraint. Really:

inv r(S) = ∀ t₁, T₂ ∈ r(t₁[K]=t₂ [K] → t₁(S) = t₂(S)), K ⊆ S;

It’s just that in the definition of a functional dependence, instead of the subscheme X, you need to take the designation of the key K, and instead of the right side of the functional dependence, the subscheme Y, take the entire scheme of relations S, i.e., indeed, the restriction on the uniqueness of the keys of the relations is a special case of the restriction of the functional dependence when the right side is equal schemes of functional dependence throughout the relationship scheme.

Here are examples of the image of functional dependence:

{Account book number} → {Surname, First name, Patronymic};

{Gradebook No., Subject} → {Grade};

2. Armstrong's inference rules

If any basic relation satisfies vector-defined functional dependencies, then with the help of various special inference rules it is possible to obtain other functional dependencies that this basic relation will certainly satisfy.

A good example of such special rules are Armstrong's inference rules.

But before proceeding to the analysis of the Armstrong inference rules themselves, let us introduce a new metalinguistic symbol "├", which is called derivability meta-assertion symbol. This symbol, when formulating rules, is written between two syntactic expressions and indicates that the formula to the right of it is derived from the formula to the left of it.

Let us now formulate the Armstrong inference rules themselves in the form of the following theorem.

Theorem. The following rules are valid, called Armstrong's inference rules.

Inference Rule 1. ├ X → X;

Inference Rule 2. X → Y├ X ∪ Z → Y;

Inference Rule 3. X → Y, Y ∪ W → Z ├ X ∪ W → Z;

Here X, Y, Z, W are arbitrary subschemes of the scheme of relation S. The derivability metastatement symbol separates lists of premises and lists of assertions (conclusions).

1. The first inference rule is called "reflexivity" and reads as follows: "the rule is deduced:" X functionally entails X "". This is the simplest of Armstrong's inference rules. It is derived literally from thin air.

It is interesting to note that a functional dependence that has both left and right parts is called reflexive. According to the reflexivity rule, the constraint of reflexive dependence is performed automatically.

2. The second inference rule is called "replenishment" and reads as follows: "if X functionally determines Y, then the rule is derived: "the union of subcircuits X and Z functionally entails Y"". The replenishment rule allows you to expand the left side of the restriction of functional dependencies.

3. The third inference rule is called "pseudotransitivity" and reads as follows: "if subcircuit X functionally entails subcircuit Y, and the union of subcircuits Y and W functionally entails Z, then the rule is derived: "the union of subcircuits X and W functionally determines subcircuit Z"".

The pseudo-transitivity rule generalizes the transitivity rule corresponding to the special case W: = 0. Let us give a formal notation of this rule:

X→Y, Y→Z ├X→Z.

It should be noted that the premises and conclusions given earlier were presented in an abbreviated form by the designations of functional dependence schemes. In extended form, they correspond to the following functional dependency constraints.

Inference Rule 1. inv r(S);

Inference Rule 2. inv r(S) ⇒ inv r(S);

Inference Rule 3. inv r(S) & inv r(S) ⇒ inv r(S);

Draw proof of these inference rules.

1. Proof of the rule reflexivity follows directly from the definition of the functional dependence constraint when subscheme X is replaced by subcircuit Y.

Indeed, take the functional dependence constraint:

inv r(S) and substitute X instead of Y into it, we get:

inv r(S), and this is the reflexivity rule.

The reflexivity rule is proved.

2. Proof of the rule replenishment Let's illustrate on diagrams of functional dependence.

The first diagram is the package diagram:

premise: X → Y

Second diagram:

conclusion: X ∪ Z → Y

Let the tuples be equal on X ∪ Z. Then they are equal on X. According to the premise, they will be equal on Y as well.

The replenishment rule is proven.

3. Proof of the rule pseudo-transitivity we will also illustrate on diagrams, which in this particular case will be three.

The first diagram is the first premise:

premise 1: X → Y

premise 2: Y ∪ W → Z

And finally, the third diagram is the conclusion diagram:

conclusion: X ∪ W → Z

Let the tuples be equal on X ∪ W. Then they are equal on both X and W. According to Premise 1, they will be equal on Y as well. Hence, according to Premise 2, they will be equal on Z as well.

The pseudotransitivity rule is proved.

All rules are proven.

3. Derived inference rules

Another example of rules by which one can, if necessary, derive new rules of functional dependence are the so-called derived inference rules.

What are these rules, how are they obtained?

It is known that if others are deduced from some already existing rules by legitimate logical methods, then these new rules, called derivatives, can be used along with the original rules.

It should be specially noted that these very arbitrary rules are "derived" precisely from the Armstrong's inference rules that we have gone through earlier.

Let us formulate the derived rules for deriving functional dependencies in the form of the following theorem.

Theorem.

The following rules are derived from Armstrong's inference rules.

Inference Rule 1. ├ X ∪ Z → X;

Inference Rule 2. X → Y, X → Z ├ X ∪ Y → Z;

Inference Rule 3. X → Y ∪ Z ├ X → Y, X → Z;

Here X, Y, Z, W, as in the previous case, are arbitrary subschemes of the scheme of relation S.

1. The first derived rule is called triviality rule and reads like this:

"The rule is derived: 'the union of subcircuits X and Z functionally entails X'".

A functional dependency with the left side being a subset of the right side is called trivial. According to the triviality rule, trivial dependency constraints are automatically satisfied.

Interestingly, the triviality rule is a generalization of the reflexivity rule and, like the latter, could be derived directly from the definition of the functional dependency constraint. The fact that this rule is derived is not accidental and is related to the completeness of Armstrong's system of rules. We will talk more about the completeness of Armstrong's system of rules a little later.

2. The second derived rule is called additivity rule and reads as follows: "If subcircuit X functionally determines subcircuit Y, and X simultaneously functionally determines Z, then the following rule is deduced from these rules: "X functionally determines the union of subcircuits Y and Z"".

3. The third derived rule is called projectivity rule or the ruleadditivity reversal". It reads as follows: "If the subcircuit X functionally determines the union of the subcircuits Y and Z, then the following rule is deduced from this rule: "X functionally determines the subcircuit Y and at the same time X functionally determines the subcircuit Z"", i.e., indeed, this the derived rule is the reversed additivity rule.

It is curious that the rules of additivity and projectivity as applied to functional dependencies with the same left parts allow one to combine or, conversely, split the right parts of the dependency.

When constructing inference chains, after formulating all the premises, the rule of transitivity is applied in order to include a functional dependence with the right side in the conclusion.

Draw proof of listed arbitrary inference rules.

1. Proof of the rule trivialities.

Let us carry it out, like all subsequent proofs, step by step:

1) we have: X → X (from Armstrong's rule of reflexivity of inference);

2) further we have: X ∪ Z → X (obtained by first applying Armstrong's inference completion rule, and then as a consequence of the first step of the proof).

The triviality rule has been proven.

2. We carry out a step-by-step proof of the rule additivity:

1) we have: X → Y (this is premise 1);

2) we have: X → Z (this is premise 2);

3) we have: Y ∪ Z → Y ∪ Z (from Armstrong's rule of reflexivity of inference);

4) we have: X ∪ Z → Y ∪ Z (obtained by applying the rule of pseudotransitivity of Armstrong's inference, and then as a consequence of the first and third steps of the proof);

5) we have: X ∪ X → Y ∪ Z (obtained by applying Armstrong's rule of pseudo-transitivity of inference, and then follows from the second and fourth steps);

6) we have X → Y ∪ Z (follows from the fifth step).

The additivity rule is proved.

3. And finally, we will construct a proof of the rule projectivity:

1) we have: X → Y ∪ Z, X → Y ∪ Z (this is a premise);

2) we have: Y → Y, Z → Z (derived using Armstrong's rule of reflexivity of inference);

3) we have: Y ∪ z → y, Y ∪ z → Z (obtained from Armstrong's inference completion rule and the corollary from the second step of the proof);

4) we have: X → Y, X → Z (obtained by applying the rule of pseudo-transitivity of Armstrong's inference, and then as a consequence of the first and third steps of the proof).

The projectivity rule is proved.

All derivative inference rules are proven.

4. Completeness of the system of Armstrong rules

Let F(S) be a given set of functional dependencies defined over the relation scheme S.

Denote by inv the constraint imposed by this set of functional dependencies. Let's write it down:

inv r(S) = ∀X → Y ∈F(S) [inv r(S)].

So, this set of restrictions imposed by functional dependencies is deciphered as follows: for any rule from the system of functional dependencies X → Y belonging to the set of functional dependencies F(S), the restriction of functional dependencies inv r(S) defined over the set of relation r(S).

Let some relation r(S) satisfy this constraint.

By applying Armstrong's inference rules to the functional dependencies defined for the set F(S), one can obtain new functional dependencies, as we have already said and proved before. And, which is indicative, the relation F(S) will automatically satisfy the restrictions of these functional dependencies, as can be seen from the extended form of writing Armstrong's inference rules. Recall the general form of these extended inference rules:

Inference Rule 1. inv r(S);

Inference Rule 2. inv r(S) ⇒ inv<X ∪ Z → Y> r(S);

Inference Rule 3. inv r(S) & inv ∪ W → Z> r(S) ⇒ inv<X ∪ W→Z>;

Returning to our reasoning, let us replenish the set F(S) with new dependencies derived from it using Armstrong's rules. We will use this replenishment procedure until we no longer get new functional dependencies. As a result of this construction, we will get a new set of functional dependencies, called closure set F(S) and denoted F⁺(S).

Indeed, such a name is quite logical, because we personally, through a long construction, "closed" the set of existing functional dependencies on itself, adding (hence the "+") all the new functional dependencies resulting from the existing ones.

It should be noted that this process of constructing a closure is finite, because the relation scheme itself, on which all these constructions are carried out, is finite.

It goes without saying that a closure is a superset of the set being closed (indeed, it is larger!) and does not change in any way when it is closed again.

If we write what has just been said in a formulaic form, we get:

F(S) ⊆ F⁺(S), [F⁺(S)]⁺= F⁺(S);

Further, from the proved truth (i.e., legality, legitimacy) of Armstrong's inference rules and the definition of closure, it follows that any relation that satisfies the constraints of a given set of functional dependencies will satisfy the constraint of the dependency belonging to the closure.

X → Y ∈ F⁺(S) ⇒ ∀r(S) [inv r(S) ⇒ inv r(S)];

So, Armstrong's completeness theorem for the system of inference rules states that the external implication can be quite legitimately and justifiably replaced by an equivalence.

(We will not consider the proof of this theorem, since the process of proof itself is not so important in our particular course of lectures.)

<< Back: Creating Basic Relationships (Metalinguistic symbols. An example of creating a base relation in a pseudocode record. Stateful integrity constraints. Referential integrity constraints. The concept of indexes. Modification of base relations)

>> Forward: Normal forms (The meaning of normalizing database schemas. First normal form (1NF). Second normal form (2NF). Third normal form (3NF). Boyce-Codd normal form (NFBC). Nesting of normal forms)

We recommend interesting articles Section Lecture notes, cheat sheets:

▪ General and clinical immunology. Crib

▪ Advertising. Crib

▪ Economics and sociology of labor. Crib

See other articles Section Lecture notes, cheat sheets.

Read and write useful comments on this article.

<< Back

Latest news of science and technology, new electronics:

The existence of an entropy rule for quantum entanglement has been proven 09.05.2024

Quantum mechanics continues to amaze us with its mysterious phenomena and unexpected discoveries. Recently, Bartosz Regula from the RIKEN Center for Quantum Computing and Ludovico Lamy from the University of Amsterdam presented a new discovery that concerns quantum entanglement and its relation to entropy. Quantum entanglement plays an important role in modern quantum information science and technology. However, the complexity of its structure makes understanding and managing it challenging. Regulus and Lamy's discovery shows that quantum entanglement follows an entropy rule similar to that for classical systems. This discovery opens new perspectives in the field of quantum information science and technology, deepening our understanding of quantum entanglement and its connection to thermodynamics. The results of the study indicate the possibility of reversibility of entanglement transformations, which could greatly simplify their use in various quantum technologies. Opening a new rule ... >>

Mini air conditioner Sony Reon Pocket 5 09.05.2024

Summer is a time for relaxation and travel, but often the heat can turn this time into an unbearable torment. Meet a new product from Sony - the Reon Pocket 5 mini-air conditioner, which promises to make summer more comfortable for its users. Sony has introduced a unique device - the Reon Pocket 5 mini-conditioner, which provides body cooling on hot days. With it, users can enjoy coolness anytime, anywhere by simply wearing it around their neck. This mini air conditioner is equipped with automatic adjustment of operating modes, as well as temperature and humidity sensors. Thanks to innovative technologies, Reon Pocket 5 adjusts its operation depending on the user's activity and environmental conditions. Users can easily adjust the temperature using a dedicated mobile app connected via Bluetooth. Additionally, specially designed T-shirts and shorts are available for convenience, to which a mini air conditioner can be attached. The device can oh ... >>

Energy from space for Starship 08.05.2024

Producing solar energy in space is becoming more feasible with the advent of new technologies and the development of space programs. The head of the startup Virtus Solis shared his vision of using SpaceX's Starship to create orbital power plants capable of powering the Earth. Startup Virtus Solis has unveiled an ambitious project to create orbital power plants using SpaceX's Starship. This idea could significantly change the field of solar energy production, making it more accessible and cheaper. The core of the startup's plan is to reduce the cost of launching satellites into space using Starship. This technological breakthrough is expected to make solar energy production in space more competitive with traditional energy sources. Virtual Solis plans to build large photovoltaic panels in orbit, using Starship to deliver the necessary equipment. However, one of the key challenges ... >>

Random news from the Archive Dogs, like people, can experience anxiety. 22.03.2022 Dogs, just like humans, can experience mental health issues, and that four-legged dogs can be a model for the study of human psychopathology and personality. Research scientists have shown that people have only 5 main personality traits ("big five"): extraversion, agreeableness, conscientiousness, neuroticism and openness to experience. These characteristics can be used to predict mental health, with neuroticism in particular being strongly associated with anxiety and other forms of psychopathology, and conscientiousness being negatively correlated with attention deficit disorders. Meanwhile, dogs are considered to have seven personality traits: insecure, energetic, learning-oriented, aggressive/dominant, sociable with people, sociable with dogs, and assertive. Dogs are said to have seven personality traits: insecure, energetic, learning-oriented, aggressive/dominant, sociable with people, sociable with dogs, and assertive. Scientists have found that dog personality traits resemble human personality traits and that similarities between dogs and humans suggest that common genetic and neurobiological factors may underlie these behavioral traits in both dogs and humans.

Other interesting news:

▪ New Generation of 14nm Intel Processors

▪ Powerful antibiotic produced in human nose

▪ truck x-ray

▪ Artificial intelligence got a nose

▪ Phone guide

News feed of science and technology, new electronics

Interesting materials of the Free Technical Library:

▪ site section Spectacular tricks and their clues. Article selection

▪ article From whom do they paint portraits? Where are these conversations being heard? Popular expression

▪ Where Does the Smell of Wet Earth Come From? Detailed answer

▪ article Butterbur hybrid. Legends, cultivation, methods of application

▪ article Serial and parallel connection of speakers. Encyclopedia of radio electronics and electrical engineering

▪ article Surprising numbers. Focus Secret

Leave your comment on this article:

All languages ​​of this page

Arabic	Hebrew	Polish
Bengali	Hindi	Portuguese
Chinese	Italian	Spanish
English	Japanese	Turkish
French	Korean	Ukrainian
German	Malay	Vietnamese

Home page | Library | Articles | Website map | Site Reviews

www.diagram.com.ua
2000-2024