You get a bonus - 1 coin for daily activity. Now you have 1 coin

7. Normal forms of higher orders

Lecture



In the previous chapter, normal forms up to the third normal form (3NF) were considered. In most cases, this is quite enough to develop fully functional databases. This chapter discusses the normal forms of higher orders, namely, the normal form of Beuys-Codd (NFBK), the fourth normal form (4NF), the fifth normal form (5NF).

NFBK (Boys-Codd Normal Form)

When reducing relations using the normalization algorithm to relations in 3NF, it was implicitly assumed that all relations contain one potential key. This is not always true. Consider the following example of a relationship containing two keys.

Example 1 Suppose you want to store data on the supply of parts of some suppliers. Suppose that supplier names are unique. In addition, each supplier has its own unique number. Supply data can be stored in the following respect:

Vendor number
PNUM
Supplier name
PNAME
Detail number
DNUM
Quantity supplied
VOLUME
one Firm 1 one 100
one Firm 1 2 200
one Firm 1 3 300
2 Firm 2 one 150
2 Firm 2 2 250
3 Firm 3 one 1000

Table 1 Supply Relationship

This relationship contains two potential keys - { PNUM , DNUM } and { PNAME , DNUM } . It can be seen that the data is stored with respect to redundancy - when changing the name of the supplier, this name needs to be changed in all tuples where it occurs. Is it possible to eliminate this anomaly using the normalization algorithm described in the previous chapter? To do this, it is necessary to identify the existing functional dependencies (as usual, key attributes are italicized):

PNUM   7. Normal forms of higher orders PNAME - the name of the supplier depends on the number of the supplier.

PNAME   7. Normal forms of higher orders PNUM - supplier number depends on the name of the supplier.

{ PNUM , DNUM }   7. Normal forms of higher orders VOLUME - the quantity supplied depends on the first key of the relationship.

{ PNUM , DNUM }   7. Normal forms of higher orders PNAME - supplier name depends on the first key of the relationship.

{ PNAME , DNUM }   7. Normal forms of higher orders VOLUME - the quantity supplied depends on the second key of the relationship.

{ PNAME , DNUM }   7. Normal forms of higher orders PNUM - supplier number depends on the second key of the relationship.

This relationship does not contain non-key attributes, depending on the part of the complex key (see definition 2NF). Indeed, the PNAME and PNUM attributes depend on the part of the complex key, but they themselves are key. Thus, the ratio is in 2NF.

In addition, the relation does not contain non-key attributes that are dependent on each other, since The only non-key attribute is VOLUME (see definition 3NF). Thus, it is shown that the “Supply” relationship is in 3NF.

Thus, the normalization algorithm described earlier is not applicable to this relation. It is obvious, however, that the anomaly of this relationship is eliminated by decomposing it into the following two relations:

Vendor number
PNUM
Supplier name
PNAME
one Firm 1
2 Firm 2
3 Firm 3

Table 2 Relationship "Suppliers"

Vendor number
PNUM
Detail number
DNUM
Quantity supplied
VOLUME
one one 100
one 2 200
one 3 300
2 one 150
2 2 250
3 one 1000

Table 3 Relationship "Supplies-2"

Definition 1 . Attitude   7. Normal forms of higher orders is in Boyce-Codd normal form ( NFBK ) if and only if the determinants of all functional dependencies are potential keys .

Remark If the relation is in the NFBK, then it is automatically located in 3NF. Indeed, this immediately follows from the definition of 3NF.

The “Delivery” relationship is not in the NFBC, since there are dependencies ( PNUM   7. Normal forms of higher orders PNAME and PNAME   7. Normal forms of higher orders PNUM ) whose determinants are not potential keys.

In order to eliminate dependence on determinants that are not potential keys, it is necessary to decompose, bringing these determinants and their dependent parts into a separate relation. Relationship "Suppliers" and "Deliveries-2", obtained as a result of decomposition are in the NFBK.

Remark The given decomposition of the “Supply” relationship into the “Supplier” and “Delivery-2” relations is not the only possible one. Alternative decomposition is decomposition into the following relations:

Vendor number
PNUM
Supplier name
PNAME
one Firm 1
2 Firm 2
3 Firm 3

Table 4 Relationship "Suppliers"

Supplier name
PNAME
Detail number
DNUM
Quantity supplied
VOLUME
Firm 1 one 100
Firm 1 2 200
Firm 1 3 300
Firm 2 one 150
Firm 2 2 250
Firm 3 one 1000

Table 5 Supply-3 Relationship

At first glance, such a decomposition is worse than the first. Indeed, the names of suppliers are still repeated, and when changing the name of the supplier, this name will have to be changed simultaneously in several places (especially in two respects at once!). It seems that the situation has become even worse than it was before decomposition. However, this feeling arises from the fact that we intuitively believe that the names of suppliers can change, but the numbers - not. If we assume that supplier numbers can also change (why not - the director ordered suppliers to be renumbered!), Then the first decomposition turns out to be just as “bad” as the second - duplicate numbers will have to be changed simultaneously in several places and also in two ways at once.

In fact, there is no contradiction here. In the case of Supply-3, the Supplier Name attribute (PNAME) is the foreign key used to communicate with the Suppliers relationship. Therefore, when changing the supplier’s name, this change is made in relation to “Suppliers” and cascadingly (see the referential integrity strategies in Chapter 3) applies to the “Delivery-3” relationship in exactly the same way as changing the supplier’s number in a cascading relationship to -2 ". Therefore, formally both decompositions are completely equal. In real work, the developer chooses, of course, the first decomposition, but it is important to emphasize here that his choice is based entirely on other considerations that are not related to the formal theory of normal forms.

Remark The “Supply-2” relationship obtained as a result of decomposition has only one potential key . Therefore, to analyze the “Supply-2” relationship, it is not required to involve the definition of the NFBK, it is enough to define 3NF. Although the "Suppliers" relationship has two potential keys, but, since there are no other attributes in it; it is already so simply arranged that it cannot be simplified further. The question arises, are there any non-trivial examples of relations in the NFBK that are not in 3NF and are not as simple as the relationship "Suppliers"?

Example 2 Suppose that we still need to consider deliveries, but each delivery deed must have some unique number (let's call it “pass-through delivery number”). Attitude can be as follows:

Vendor number
PNUM
Detail number
DNUM
Quantity supplied
VOLUME
Pass-through delivery number

Nn
one one 100 one
one 2 200 2
one 3 300 3
2 one 150 four
2 2 250 five
3 one 1000 6

Table 6 Relationship "Deliveries-with-number"

One potential key of this relationship is, as before, a pair of attributes { PNUM , DNUM } . Another key, due to the uniqueness of the pass-through number, is the NN attribute. In this respect, there are the following functional dependencies:

Attribute dependence on the first key of the relationship:

{ PNUM , DNUM }   7. Normal forms of higher orders VOLUME ,

{ PNUM , DNUM }   7. Normal forms of higher orders Nn

Attribute dependence on the second key of the relationship:

Nn   7. Normal forms of higher orders PNUM ,

Nn   7. Normal forms of higher orders DNUM ,

Nn   7. Normal forms of higher orders VOLUME ,

Dependencies resulting from dependencies on relation keys:

{ PNUM , DNUM }   7. Normal forms of higher orders { VOLUME, NN } ,

Nn   7. Normal forms of higher orders { PNUM , DNUM } ,

Nn   7. Normal forms of higher orders { PNUM , VOLUME} ,

Nn   7. Normal forms of higher orders { DNUM , VOLUME} ,

Nn   7. Normal forms of higher orders { PNUM , DNUM , VOLUME} .

As you can see, the determinants of all dependencies are potential keys, so this relationship is in the NFBK. A feature of this relationship is that it has two completely independent potential keys.

4NF (Fourth Normal Form)

Consider the following example. Suppose you want to take into account data on applicants entering the university. When analyzing the subject area, the following requirements were identified:

  • Each applicant has the right to take exams at several faculties at the same time.
  • Each faculty has its own list of donated items.
  • The same subject can be surrendered at several faculties.
  • The applicant is obliged to pass all the subjects specified for the faculty to which he enrolls, despite the fact that he may have already passed the same subjects at another faculty.

Suppose that we need to store data about what items each entrant must pass. We will try to store data in one respect "Applicants-Faculties-Subjects":

Enrollee Faculty Thing
Ivanov Mathematical Maths
Ivanov Mathematical Computer science
Ivanov Physical Maths
Ivanov Physical Physics
Petrov Mathematical Maths
Petrov Mathematical Computer science

Table 7 Relationship "Applicants-Faculties-Objects"

At the moment, in relation to the stored information that the applicant Ivanov enters the two faculties (mathematically and physical), and the applicant Petrov - only in mathematics. In addition, it can be concluded that at the Faculty of Mathematics it is necessary to take mathematics and computer science, and on the physical - mathematics and physics.

It seems that in relation to there is an anomaly of the update, due to the fact that duplicates of the names of applicants, the names of faculties and the names of subjects are duplicated. However, this anomaly is easily eliminated in the standard way - by putting all the names into separate relations, leaving only the corresponding numbers in the original relation:

room
Entrant
room
Faculty
room
Subject
one one one
one one 2
one 2 one
one 2 3
2 one one
2 one 2

Table 8 The modified relationship "Applicants-Faculties-Objects"

room
Entrant
Enrollee
one Ivanov
2 Petrov

Table 9 Attitude "Applicants"

room
Faculty
Faculty
one Mathematical
2 Physical

Table 10 Attitude "Faculties"

room
Subject
Thing
one Maths
2 Computer science
3 Physics

Table 11 Attitude "Objects"

Now each name is found only in one place.

And yet, both in the original and in the modified relation, there are update anomalies that occur when you try to insert or delete tuples.

Anomaly insertion . When trying to add a new tuple to the "Applicants-Faculties-Subjects" relation, for example (Sidorov, Mathematical, Mathematics), we must also add a tuple (Sidorov, Mathematical, Computer science), since All applicants of the Faculty of Mathematics are obliged to have the same list of donated items. Accordingly, when trying to insert a tuple (3, 1, 1) into a modified relation, we must also insert a tuple (3, 1, 2) into it.

Anomaly removal. When trying to remove a tuple (Ivanov, Mathematical, Mathematics), we must also remove the tuple (Ivanov, Mathematical, Computer science) for the same reason.

Thus, insertion and deletion of tuples cannot be performed independently of other relation tuples.

In addition, if we remove the tuple (Ivanov, Physical, Mathematics), and with it the tuple (Ivanov, Physical, Physics), then information will be lost about the subjects that should be surrendered at the physics department.

Decomposition of the "Applicants-Faculties-Subjects" relationship to eliminate the indicated anomalies cannot be performed on the basis of functional dependencies, since This relationship does not contain any functional dependencies . This relationship is completely key, i.e. the key of a relationship is the whole set of attributes. But it is clear that there is some kind of relationship between the attributes. This relationship is described by the concept of a multi-valued relationship .

Definition 2 . Let be   7. Normal forms of higher orders - attitude, and   7. Normal forms of higher orders ,   7. Normal forms of higher orders ,   7. Normal forms of higher orders - some of its attributes (or disjoint attribute sets).

Then attributes (attribute sets)   7. Normal forms of higher orders and   7. Normal forms of higher orders depend heavily on   7. Normal forms of higher orders (denoted by   7. Normal forms of higher orders ), if and only if from the fact that with respect to   7. Normal forms of higher orders contain tuples   7. Normal forms of higher orders and   7. Normal forms of higher orders it follows that with respect   7. Normal forms of higher orders there is also a tuple to   7. Normal forms of higher orders .

Remark Swapping tuples   7. Normal forms of higher orders and   7. Normal forms of higher orders in the definition of a multi-valued relationship, we get that in relation to   7. Normal forms of higher orders the tuple must also be contained   7. Normal forms of higher orders . So the attributes   7. Normal forms of higher orders and   7. Normal forms of higher orders dependently on   7. Normal forms of higher orders behave "symmetrically" with respect to the attribute   7. Normal forms of higher orders .

With regard to "Applicants-Faculties-Subjects" there is a significant relationship Faculty   7. Normal forms of higher orders Entrant | Subject.

This can be expressed in words as follows - for each faculty (for each value from   7. Normal forms of higher orders ) each applicant entering him (value from   7. Normal forms of higher orders ) handles the same list of items (set of values ​​from   7. Normal forms of higher orders ), and for each faculty (for each value of   7. Normal forms of higher orders ) each pass on the faculty exam (the value of   7. Normal forms of higher orders ) is submitted by the same list of applicants (a set of values ​​from   7. Normal forms of higher orders ). It is the presence of this dependency that does not allow for independently inserting and deleting tuples. Tuples are required to be inserted and removed simultaneously in whole sets .

Remark If regarding   7. Normal forms of higher orders there are at least three attributes   7. Normal forms of higher orders ,   7. Normal forms of higher orders ,   7. Normal forms of higher orders and there is a functional dependency   7. Normal forms of higher orders , that is, a multiple-valued dependence   7. Normal forms of higher orders .

Indeed, acting formally in accordance with the definition of a multi-valued dependence, suppose that with respect to   7. Normal forms of higher orders contain tuples   7. Normal forms of higher orders and   7. Normal forms of higher orders . Due to functional dependence   7. Normal forms of higher orders it follows that   7. Normal forms of higher orders . But then the tuple   7. Normal forms of higher orders exactly the same as the tuple   7. Normal forms of higher orders and therefore contained in relation   7. Normal forms of higher orders . Thus, there is a multi-valued relationship   7. Normal forms of higher orders .

Thus, the concept of a multivalued dependence is a generalization of the concept of functional dependence .

Definition 3 . Many-valued dependency   7. Normal forms of higher orders is called a non-trivial multivalued dependency , if there are no functional dependencies   7. Normal forms of higher orders and   7. Normal forms of higher orders .

With regard to "Applicants-Faculties-Subjects" there is precisely a nontrivial multivalued dependence Faculty   7. Normal forms of higher orders Entrant | Subject. Due to the nontriviality of this dependence, we cannot use the Hez theorem to decompose the relation. However, Fagin R. [52] proved the following theorem:

Theorem (Fagin) . Let be   7. Normal forms of higher orders ,   7. Normal forms of higher orders ,   7. Normal forms of higher orders - disjoint sets of relation attributes   7. Normal forms of higher orders .

Relation decomposition   7. Normal forms of higher orders on the projection   7. Normal forms of higher orders and   7. Normal forms of higher orders will be lossless decomposition if and only if there is a multi-valued relationship   7. Normal forms of higher orders .

RemarkIf the dependency   7. Normal forms of higher orders is trivial, i.e. there is one of the functional dependencies  7. Normal forms of higher orders or   7. Normal forms of higher orders then we get the Hez theorem.

Proof of the theorem .

Necessity . Let decomposition of a relation  7. Normal forms of higher orders on a projection  7. Normal forms of higher orders and   7. Normal forms of higher orders is lossless decomposition. Prove that  7. Normal forms of higher orders .

Suppose the relation   7. Normal forms of higher orders contains tuples  7. Normal forms of higher orders and   7. Normal forms of higher orders .It is necessary to prove that the tuple is   7. Normal forms of higher orders also contained in  7. Normal forms of higher orders .By the definition of projections, a tuple is   7. Normal forms of higher orders contained in   7. Normal forms of higher orders , and a tuple is   7. Normal forms of higher orders contained in  7. Normal forms of higher orders .Then the tuple is   7. Normal forms of higher orders contained in the natural connection   7. Normal forms of higher orders , and since decomposition is a lossless decomposition, this tuple is contained in  7. Normal forms of higher orders . Necessity is proved .

Sufficiency . Let there be a multi-valued dependence  7. Normal forms of higher orders .Let us prove that the decomposition of a relation   7. Normal forms of higher orders on a projection  7. Normal forms of higher orders and   7. Normal forms of higher orders is lossless decomposition.

As in the proof of the Hez theorem, it is necessary to prove that   7. Normal forms of higher orders for any state of a relation  7. Normal forms of higher orders .

The inclusion is   7. Normal forms of higher orders proved as in the Hez theorem. Such inclusion is always performed for any decomposition of a relation.  7. Normal forms of higher orders .

We prove the inclusion   7. Normal forms of higher orders . Let the tuple   7. Normal forms of higher orders .This means that the projection   7. Normal forms of higher orders contains a tuple   7. Normal forms of higher orders , and the projection   7. Normal forms of higher orders contains a tuple  7. Normal forms of higher orders . По определению проекции, найдется такое значение   7. Normal forms of higher orders атрибута   7. Normal forms of higher orders , что отношение   7. Normal forms of higher orders содержит кортеж   7. Normal forms of higher orders . Аналогично, найдется такое значение   7. Normal forms of higher orders атрибута   7. Normal forms of higher orders , что отношение   7. Normal forms of higher orders содержит кортеж   7. Normal forms of higher orders . Тогда по определению многозначной зависимости кортеж   7. Normal forms of higher orders . Включение доказано. Достаточность доказана . Теорема доказана .

Определение 4 . Отношение   7. Normal forms of higher orders находится в четвертой нормальной форме ( 4НФ ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей .

Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения:

Faculty Абитуриент
Математический Ivanov
Физический Ivanov
Математический Петров

Таблица 12 Отношение "Факультеты-Абитуриенты"

Faculty Thing
Математический Maths
Математический Computer science
Физический Maths
Физический Physics

Таблица 13 Отношение "Факультеты-Предметы"

В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения "Абитуриенты-Факультеты-Предметы".

Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет функциональных зависимостей.

Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему полю, которое не является ключевым ни в одном из отношений . Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых сущностях. В качестве еще одного примера можно привести ситуацию, когда сотрудник может иметь много работ и много детей. Хранение информации о работах и детях в одном отношении приводит к возникновению нетривиальной многозначной зависимости Работник   7. Normal forms of higher orders Работа|Дети.

5НФ (Пятая Нормальная Форма)

Функциональные и многозначные зависимости позволяют произвести декомпозицию исходного отношения без потерь на две проекции. Можно, однако, привести примеры отношений, которые нельзя декомпозировать без потерь ни на какие две проекции.

Example 3 Рассмотрим следующее отношение   7. Normal forms of higher orders :

X Y Z
one one 2
one 2 one
2 one one
one one one

Таблица 14 Отношение R

Всевозможные проекции отношения   7. Normal forms of higher orders , включающие по два атрибута, имеют вид:

X Y
one one
one 2
2 one

Таблица 15 Проекция R1=R[X,Y]

X Z
one 2
one one
2 one

Таблица 16 Проекция R2=R[X,Z]

Y Z
one 2
2 one
one one

Таблица 17 Проекция R3=R[Y,Z]

Как легко заметить, отношение   7. Normal forms of higher orders не восстанавливается ни по одному из попарных соединений   7. Normal forms of higher orders ,   7. Normal forms of higher orders or   7. Normal forms of higher orders . Действительно, соединение   7. Normal forms of higher orders имеет вид:

X Y Z
one one 2
one one one
one 2 2
one 2 one
2 one one

Таблица 18 R1 JOIN R2

Серым цветом выделен лишний кортеж, отсутствующий в отношении   7. Normal forms of higher orders . Аналогично (в силу соображений симметрии) и другие попарные соединения не восстанавливают отношения   7. Normal forms of higher orders .

Однако отношение   7. Normal forms of higher orders восстанавливается соединением всех трех проекций:

  7. Normal forms of higher orders .

Это говорит о том, что между атрибутами этого отношения также имеется некоторая зависимость, но эта зависимость не является ни функциональной, ни многозначной зависимостью.

Определение 5 . Let be   7. Normal forms of higher orders является отношением, а   7. Normal forms of higher orders ,   7. Normal forms of higher orders , ...,   7. Normal forms of higher orders - произвольными (возможно пересекающимися) подмножествами множества атрибутов отношения   7. Normal forms of higher orders . Тогда отношение   7. Normal forms of higher orders удовлетворяет зависимости соединения

  7. Normal forms of higher orders

тогда и только тогда, когда оно равносильно соединению всех своих проекций с подмножествами атрибутов   7. Normal forms of higher orders ,   7. Normal forms of higher orders , ...,   7. Normal forms of higher orders i.e.

  7. Normal forms of higher orders .

Можно предположить , что отношение   7. Normal forms of higher orders в примере 3 удовлетворяет следующей зависимости соединения:

  7. Normal forms of higher orders .

Утверждать, что это именно так мы пока не можем, т.к. определение зависимости соединения должно выполняться для любого состояния отношения   7. Normal forms of higher orders , а не только для состояния, приведенного в примере.

Покажем, что зависимость соединения является обобщением понятия многозначной зависимости. Действительно, согласно теореме Фейджина, отношение   7. Normal forms of higher orders может быть декомпозировано без потерь на проекции   7. Normal forms of higher orders and   7. Normal forms of higher orders тогда и только тогда, когда имеется многозначная зависимость   7. Normal forms of higher orders . Согласно определению зависимости соединения, теорема Фейджина может быть переформулирована следующим образом:

Теорема Фейджина (другая формулировка) . Отношение   7. Normal forms of higher orders удовлетворяет зависимости соединения   7. Normal forms of higher orders тогда и только тогда, когда имеется многозначная зависимость   7. Normal forms of higher orders .

Because теорема Фейджина является взаимно обратной, то ее можно взять в качестве определения многозначной зависимости. Таким образом, многозначная зависимость является частным случаем зависимости соединения, т.е., если в отношении имеется многозначная зависимость, то имеется и зависимость соединения. Обратное, конечно, неверно.

Определение 6 . Зависимость соединения   7. Normal forms of higher orders называется нетривиальной зависимостью соединения , если выполняется два условия:

  • Одно из множеств атрибутов   7. Normal forms of higher orders не содержит потенциального ключа отношения   7. Normal forms of higher orders .

  • Ни одно из множеств атрибутов не совпадает со всем множеством атрибутов отношения   7. Normal forms of higher orders .

Для удобства работы сформулируем это определение так же и в отрицательной форме:

Определение 7 . Зависимость соединения   7. Normal forms of higher orders называется тривиальной зависимостью соединения , если выполняется одно из условий:

  • Либо все множества атрибутов   7. Normal forms of higher orders содержат потенциальный ключ отношения   7. Normal forms of higher orders .
  • Либо одно из множеств атрибутов совпадает со всем множеством атрибутов отношения   7. Normal forms of higher orders .

Определение 8 . Отношение   7. Normal forms of higher orders находится в пятой нормальной форме ( 5НФ ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной .

Определения 5НФ может стать более понятным, если сформулировать его в отрицательной форме:

Определение 9 . Отношение   7. Normal forms of higher orders не находится в 5НФ , если в отношении найдется нетривиальная зависимость соединения .

Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенциальные ключи имеются в отношении и как взаимосвязаны атрибуты, нельзя делать выводы о том, находится ли данное отношение в 5НФ (как, впрочем, и в других нормальных формах). По данному конкретному примеру можно только предположить, что отношение в примере 3 не находится в 5НФ. Предположим, что анализ предметной области позволил выявить следующие зависимости атрибутов в отношении   7. Normal forms of higher orders :

(i) Отношение   7. Normal forms of higher orders является полностью ключевым (т.е. потенциальным ключом отношения является все множество атрибутов).

(ii) Имеется следующая зависимость (довольно странная, с практической точки зрения): если в отношении   7. Normal forms of higher orders содержатся кортежи   7. Normal forms of higher orders ,   7. Normal forms of higher orders and   7. Normal forms of higher orders , то отсюда следует, что в отношении   7. Normal forms of higher orders содержится также и кортеж   7. Normal forms of higher orders .

Утверждение . Докажем, что при наличии ограничений (i) и (ii), отношение находится в 4НФ, но не в 5НФ.

Доказательство . Покажем, что отношение   7. Normal forms of higher orders находится в 4НФ. Согласно определению 4НФ, необходимо показать, что отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей. Because отношение является полностью ключевым, то оно автоматически находится в НФБК. Если бы в отношении имелась многозначная зависимость (необязательно нетривиальная), то, согласно теореме Фейджина, отношение можно было бы декомпозировать без потерь на две проекции. Но пример 3 показывает, что таких декомпозиций нет (здесь мы воспользовались тем, что для доказательства возможности декомпозиции необходимо доказать ее для всех возможных состояний отношения, а для доказательства невозможности достаточно привести один контрпример). Поэтому в отношении нет никаких многозначных зависимостей.

Покажем, что отношение не находится в 5НФ. Для этого нужно привести пример нетривиальной зависимости соединения. Естественным кандидатом на нее является   7. Normal forms of higher orders . Если это действительно зависимость соединения, то она нетривиальна. Действительно, ни одно из множеств атрибутов   7. Normal forms of higher orders ,   7. Normal forms of higher orders and   7. Normal forms of higher orders не совпадает с множеством всех атрибутов отношения   7. Normal forms of higher orders и не содержит потенциального ключа.

Но является ли такая декомпозиция именно зависимостью соединения? Для этого нужно показать, что декомпозиция на три проекции   7. Normal forms of higher orders ,   7. Normal forms of higher orders and   7. Normal forms of higher orders является декомпозицией без потерь для любого состояния отношения   7. Normal forms of higher orders (именно здесь содержится ключевая тонкость, обычно пропускаемая при анализе конкретного состояния отношения   7. Normal forms of higher orders в примере 3, и именно здесь нам понадобятся знания о предметной области, выраженные в утверждении (ii)).

Как и в предыдущих доказательствах, нужно доказать, что   7. Normal forms of higher orders для любого состояния отношения   7. Normal forms of higher orders .

Включение   7. Normal forms of higher orders доказывается как в теореме Хеза. Такое включение выполняется всегда для любой декомпозиции отношения   7. Normal forms of higher orders .

Докажем включение   7. Normal forms of higher orders .

Пусть кортеж   7. Normal forms of higher orders . Это означает, что в проекции   7. Normal forms of higher orders содержится кортеж   7. Normal forms of higher orders , в проекции   7. Normal forms of higher orders содержится кортеж   7. Normal forms of higher orders , а в проекции   7. Normal forms of higher orders содержится кортеж   7. Normal forms of higher orders . По определению проекции, найдутся такие значения   7. Normal forms of higher orders ,   7. Normal forms of higher orders ,   7. Normal forms of higher orders атрибутов   7. Normal forms of higher orders ,   7. Normal forms of higher orders and   7. Normal forms of higher orders соответственно, что отношение   7. Normal forms of higher orders содержит кортежи   7. Normal forms of higher orders ,   7. Normal forms of higher orders and   7. Normal forms of higher orders . Но тогда по условию (ii) в отношении   7. Normal forms of higher orders содержится также и кортеж   7. Normal forms of higher orders . Этим доказано необходимое включение. Утверждение доказано .

Продолжение алгоритма нормализации (приведение к 5НФ)

В предыдущей главе был описан алгоритм нормализации как алгоритм приведения отношений к 3НФ. Теперь мы можем продолжить этот алгоритм, доведя его до алгоритма приведения к 5НФ.

Шаг 4 (Приведение к НФБК) . Если имеются отношения, содержащие несколько потенциальных ключей, то необходимо проверить, имеются ли функциональные зависимости, детерминанты которых не являются потенциальными ключами. Если такие функциональные зависимости имеются, то необходимо провести дальнейшую декомпозицию отношений. Те атрибуты, которые зависят от детерминантов, не являющихся потенциальными ключами выносятся в отдельное отношение вместе с детерминантами.

Шаг 5 (Приведение к 4НФ) . Если в отношениях обнаружены нетривиальные многозначные зависимости, то необходимо провести декомпозицию для исключения таких зависимостей.

Шаг 5 (Приведение к 5НФ) . Если в отношениях обнаружены нетривиальные зависимости соединения, то необходимо провести декомпозицию для исключения и таких зависимостей.

findings

Обобщением 3НФ на случай, когда отношение имеет более одного потенциального ключа, является нормальная форма Бойса-Кодда.

Отношение   7. Normal forms of higher orders находится в нормальной форме Бойса-Кодда ( НФБК ) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами.

Нормализация отношений вплоть до нормальной формы Бойса-Кодда основывалась на понятии функциональной зависимости и теореме Хеза, гарантировавшей, что декомпозиция будет происходить без потерь информации.

Дальнейшая нормализация связана уже с обобщением понятия функциональной зависимости.

Атрибуты (множества атрибутов)   7. Normal forms of higher orders and   7. Normal forms of higher orders многозначно зависят от   7. Normal forms of higher orders , (   7. Normal forms of higher orders ), тогда и только тогда, когда из того, что в отношении   7. Normal forms of higher orders содержатся кортежи   7. Normal forms of higher orders and   7. Normal forms of higher orders следует, что в отношении   7. Normal forms of higher orders содержится также и кортеж к   7. Normal forms of higher orders .

Корректность дальнейшей декомпозиции основывается на теореме Фейджина, которая говорит о том, что декомпозиция отношения на две проекции является декомпозицией без потерь тогда и только тогда, когда в отношении имеется некоторая многозначная зависимость.

Если в отношении имеется функциональная зависимость, то автоматически имеется и тривиальная многозначная зависимость, определяемая этой функциональной зависимостью.

Многозначная зависимость   7. Normal forms of higher orders называется нетривиальной многозначной зависимостью , если не существует функциональных зависимостей   7. Normal forms of higher orders and   7. Normal forms of higher orders .

Отношение   7. Normal forms of higher orders находится в четвертой нормальной форме ( 4НФ ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.

Имеют место зависимости специального вида, когда отношение не может быть подвергнуто декомпозиции без потерь на две проекции, но может быть декомпозировано на большее число проекций. Такие зависимости называются зависимостями соединения и являются обобщением понятия многозначной зависимости.

A relation   7. Normal forms of higher orders is in the fifth normal form ( 5NF ) if and only if any existing dependence of the compound is trivial .


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Databases, knowledge and data warehousing. Big data, DBMS and SQL and noSQL

Terms: Databases, knowledge and data warehousing. Big data, DBMS and SQL and noSQL