- 6. Normal forms of relationships. Database Design, Types of

Это окончание невероятной информации про нормальные формы.

...

the data on the employees who participated in the project remain in the relationship PROJECTS and EMPLOYEES .

However, part of the anomalies could not be resolved.

The remaining insertion anomalies (INSERT)

In relation to EMPLOYEES_DEPARTMENTS, you cannot insert a tuple (4, Pushnikov, 1, 33-22-11), because at the same time, it turns out that two employees from the 1st Division (Ivanov and Pushnikov) have different telephone numbers, and this contradicts the domain model. In this situation, two solutions can be proposed, depending on what really happened in the subject area. Another phone number can be entered for two reasons - by mistake of the person entering the data about the new employee, or because the number in the department has really changed. Then you can write a trigger that, when inserting an employee record, checks whether the phone matches the already existing phone from another employee of the same department. If the numbers are different, the system should ask the question whether to leave the old number in the department or replace it with a new one. If you need to leave the old number (the new number is entered incorrectly), then the tuple with the data about the new employee will be inserted, but the phone number will be the one that already exists in the department (in this case, 11-22-33). If the number in the department has really changed, then the tuple will be inserted with the new number, and at the same time the phone numbers of all employees of the same department will be changed. And in that and in other case not to do without development of the bulky trigger.

The reason for the anomaly is data redundancy, due to the fact that in one respect heterogeneous information is stored (about employees and about departments).

Conclusion - increases the complexity of database development. A database based on such a model will work correctly only if there is additional program code in the form of triggers.

UPDATE Remaining Anomalies

The same phone numbers are repeated in many tuples of a relationship. Therefore, if a telephone number changes in a department, then such changes must be made simultaneously in all places where this telephone number is found, otherwise the attitude will become incorrect. Thus, updating the database with one action is impossible to implement. You need to write a trigger that, when updating one entry, correctly corrects phone numbers in other places.

The reason for the anomaly is data redundancy, also generated by the fact that heterogeneous information is stored in one respect.

Conclusion - increases the complexity of database development. A database based on such a model will work correctly only if there is additional program code in the form of triggers.

The remaining deletion anomalies (DELETE)

When deleting some data, other information may still be lost. For example, if you delete the employee Sidorov, you will lose the information that in the section number 2 is the telephone 33-22-11.

The reason for the anomaly is storing in one respect heterogeneous information (both about employees and about departments).

The conclusion is that the logical data model is inadequate to the domain model. A database based on this model will not work correctly.

Note that in the transition to the second normal form of the relationship became almost adequate subject area. There are also difficulties in developing a database associated with the need to write triggers that maintain the integrity of the database. These difficulties are now associated with only one relationship EMPLOYEES_DEPARTMENTS .

3NF (Third Normal Form)

Definition 4 . Attributes are called mutually independent if neither of them is functionally dependent on the other.

Definition 5 . Attitude is in the third normal form ( 3NF ) if and only if the relation is in 2NF and all non-key attributes are mutually independent .

The ratio EMPLOYEES_DESIGNS is not in 3NF, because there is a functional dependence of non-key attributes (the dependence of a telephone number on a department number):

N_OTD TEL

In order to eliminate the dependence of non-key attributes, it is necessary to decompose the relationship into several relations. In this case, those non-key attributes that are dependent, are taken out in a separate relationship.

Attitudes EMPLOYEES_DESETS we decompose into two relations - EMPLOYEES , DEPARTMENTS .

Attitude EMPLOYEES ( H_COTR , FAM , H_OTD ):

Functional dependencies:

The dependence of the attributes characterizing the employee from the employee's employee number:

H_SOTR FAM

H_SOTR N_OTD

H_SOTR TEL

H_SOTR	FAM	N_OTD
one	Ivanov	one
2	Petrov	one
3	Sidorov	2

Table 5 Attitude EMPLOYEES

Attitude DEPARTMENTS ( N_OTD , TEL ):

Functional dependencies:

Dependence of the telephone number on the department number:

N_OTD TEL

N_OTD	TEL
one	11-22-33
2	33-22-11

Table 6 Attitudes DEPARTMENTS

Note that the N_OTD attribute, which was not the key for EMPLOYEES , has become a potential key for the DEPARTMENT . This is due to this eliminated redundancy associated with multiple storage of the same phone numbers.

Conclusion. Thus, all detected update anomalies are eliminated. The relational model consisting of four relations EMPLOYEES , DEPARTMENTS , PROJECTS , TASKS , which are in the third normal form, is adequate to the described domain model, and requires only those triggers that maintain referential integrity. Such triggers are standard and do not require much effort in development.

Algorithm of normalization (reduction to 3NF)

So, the normalization algorithm (i.e., the algorithm for reducing relations to 3NF) is described as follows.

Step 1 (Reduction to 1NF) . In the first step, one or more relations are defined that reflect the concepts of the domain. According to the domain model (not in appearance of the obtained relationships!), The detected functional dependencies are written out. All relationships are automatically in 1NF.

Step 2 (Reduction to 2NF) . If in some respects the dependence of attributes on the part of a complex key is found, then we decompose these relations into several relations as follows: those attributes that depend on the part of the complex key are put into a separate relationship with this part of the key. In the original relationship, all key attributes remain:

Initial relationship: .

Key: - complicated.

Functional dependencies:

- dependence of all attributes on the relation key.

- dependence of some attributes on a part of a complex key.

Decomposed relationships:

- the remainder of the original relationship. Key .

- attributes removed from the original relationship along with a part of a complex key. Key .

Step 3 (Reduction to 3NF) . If in some respects the dependence of some non-key attributes of other non-key attributes is detected, then we decompose these relations as follows: those non-key attributes that depend on other non-key attributes are taken to a separate relation. In the new relation, the determinant of functional dependence becomes the key:

Initial relationship: .

Key: .

Functional dependencies:

- dependence of all attributes on the relation key.

- dependence of some non-key attributes of other non-key attributes.

Decomposed relationships:

- the remainder of the original relationship. Key .

- attributes removed from the original relationship along with the determinant of functional dependency. Key .

Comment. In practice, when creating a logical data model, as a rule, they do not directly follow the normalization algorithm. Experienced developers usually build relationships in 3NF right away. In addition, the main means of developing logical data models are various variants of ER-diagrams. The peculiarity of these diagrams is that they immediately allow you to create relationships in 3NF. However, the above algorithm is important for two reasons. First , this algorithm shows what problems arise when developing weakly normalized relations. Secondly , as a rule, the domain model is never properly developed from the first step. The domain experts may forget about something, the developer may misunderstand the expert, the rules adopted in the domain may change during the development, etc. All this may lead to the emergence of new dependencies that were absent in the original domain model. Here it is just necessary to use the normalization algorithm at least in order to make sure that the relations remain in 3NF and the logical model has not deteriorated.

Criteria Analysis for Normalized and Unnormalized Data Models

Comparison of normalized and non-normalized models

Let us put together the results of the analysis of the criteria by which we wanted to evaluate the impact of logical data modeling on the quality of physical data models and database performance:

Criterion	Relationships are poorly normalized. (1NF, 2NF)	Relationships are strongly normalized. (3NF)
Adequacy of the domain database	WORSE (-)	BETTER (+)
Ease of database development and maintenance	MORE DIFFICULT (-)	EASIER (+)
The speed of the insert, update, delete	SLOWER (-)	FASTER (+)
The speed of data sampling	FASTER (+)	SLOWER (-)

As can be seen from the table, the more strongly normalized relations turn out to be better designed (three pluses, one minus). They are more relevant to the subject area, easier to develop, for them faster database modification operations are performed. True, this is achieved at the cost of some deceleration of data sampling operations.

For weakly normalized relations, the only advantage is that if the database is addressed only with requests for data sampling, then for weakly normalized relations such requests are executed faster. This is due to the fact that in such a relationship the connection of the relations has already been made, and time is not wasted on sampling the data.

Thus, the choice of the degree of normalization of relations depends on the nature of the requests that are most often addressed to the database.

OLTP and OLAP systems

There are some classes of systems for which strongly or weakly normalized data models are more suitable.

Strongly normalized data models are well suited for so-called OLTP applications ( On-Line Transaction Processing ( OLTP ) - online transaction processing ). Typical examples of OLTP applications are warehouse accounting systems, ticket booking systems, banking systems that perform money transfer operations, etc. The main function of such systems is to perform a large number of short transactions. The transactions themselves look relatively simple, for example, "withdraw the amount of money from account A, add this amount to account B". The problem is that, firstly, there are a lot of transactions, secondly, they are executed simultaneously (several thousand concurrent users can be connected to the system), thirdly, if an error occurs, the transaction must completely roll back and return the system to the state that was before the start of the transaction (there should not be a situation when money is withdrawn from account A, but not credited to account B). Almost all database queries in OLTP applications consist of insert, update, delete commands. Sampling requests are primarily intended to allow users to select from various directories. Most requests are thus known in advance at the stage of system design. Thus, the speed and reliability of short data update operations is critical for OLTP applications. The higher the level of data normalization in an OLTP application, so it is usually faster and more reliable. Deviations from this rule can occur when, even at the development stage, some frequently occurring queries are known that require connection of relations and the performance of which depends greatly on the performance of applications. In this case, you can sacrifice normalization to speed up the execution of such requests.

Another type of application is the so-called OLAP-applications ( On-Line Analitical Processing ( OLAP ) - operational analytical data processing ). This is a generic term describing the principles of building decision support systems ( DSS ), data warehouses, data mining systems . Such systems are designed to find the dependencies between the data (for example, you can try to determine how the sales of goods are related to the characteristics of potential buyers), to conduct a what-if analysis. OLAP applications operate on large amounts of data already accumulated in OLTP applications, taken from spreadsheets or from other data sources. Such systems are characterized by the following features:

• Adding new data to the system occurs relatively rarely in large blocks (for example, once a quarter, data on the results of quarterly sales are loaded from an OLTP application).
• Data added to the system is usually never deleted.
• Before downloading, data undergo various “cleanup” procedures related to the fact that data from many sources that have different presentation formats for the same concepts can flow into one system, the data may be incorrect or erroneous.
• Requests to the system are ad hoc and, as a rule, quite complex. Very often a new query is formulated by an analyst to clarify the result obtained as a result of a previous query.
• The speed of query execution is important, but not critical.

The data of OLAP applications are usually represented as one or several hypercubes, the measurements of which are reference data, and the data itself is stored in the cells of the hypercube itself. For example, you can build a hypercube, the dimensions of which are: time (in quarters, years), the type of product and the separation of the company, and sales volumes are stored in cells. Such a hypercube will contain data on sales of various types of goods by quarters and divisions. Based on this data, you can answer questions like "which division has the best sales volumes in the current year?", Or "what are the sales trends of the South-West regions in the current year compared to the previous year?"

Physically, a hypercube can be built on the basis of a special multidimensional data model ( MOLAP - Multidimensional OLAP ) or built by means of a relational data model ( ROLAP - Relational OLAP ).

Возвращаясь к проблеме нормализации данных, можно сказать, что в системах OLAP, использующих реляционную модель данных (ROLAP), данные целесообразно хранить в виде слабо нормализованных отношений, содержащих заранее вычисленные основные итоговые данные. Большая избыточность и связанные с ней проблемы тут не страшны, т.к. обновление происходит только в момент загрузки новой порции данных. При этом происходит как добавление новых данных, так и пересчет итогов.

Корректность процедуры нормализации - декомпозиция без потерь. Теорема Хеза

Как было показано выше, алгоритм нормализации состоит в выявлении функциональных зависимостей предметной области и соответствующей декомпозиции отношений. Предположим, что мы уже имеем работающую систему, в которой накоплены данные. Пусть данных корректны в текущий момент, т.е. факты предметной области правильно отражаются текущим состоянием базы данных. Если в предметной области обнаружена новая функциональная зависимость (либо она была пропущена на этапе моделирования предметной области, либо просто изменилась предметная область), то возникает необходимость заново нормализовать данные. При этом некоторые отношения придется декомпозировать в соответствии с алгоритмом нормализации. Возникают естественные вопросы - что произойдет с уже накопленными данными? Не будут ли данные потеряны в ходе декомпозиции? Можно ли вернуться обратно к исходным отношениям, если будет принято решение отказаться от декомпозиции, восстановятся ли при этом данные?

Для ответов на эти вопросы нужно ответить на вопрос - что же представляет собой декомпозиция отношений с точки зрения операций реляционной алгебры? При декомпозиции мы из одного отношения получаем два или более отношений, каждое из которых содержит часть атрибутов исходного отношения. В полученных новых отношениях необходимо удалить дубликаты строк, если таковые возникли. Это в точности означает, что декомпозиция отношения есть не что иное, как взятие одной или нескольких проекций исходного отношения так, чтобы эти проекции в совокупности содержали (возможно, с повторениями) все атрибуты исходного отношения. Т.е., при декомпозиции не должны теряться атрибуты отношений. Но при декомпозиции также не должны потеряться и сами данные. Данные можно считать не потерянными в том случае, если возможна обратная операция - по декомпозированным отношениям можно восстановить исходное отношение в точности в прежнем виде . Операцией, обратной операции проекции, является операция соединения отношений. Имеется большое количество видов операции соединения (см. гл. 4). Because при восстановлении исходного отношения путем соединения проекций не должны появиться новые атрибуты, то необходимо использовать естественное соединение .

Определение 6 . Projection relations на множество атрибутов называется собственной , если множество атрибутов является собственным подмножеством множества атрибутов отношения (т.е. множество атрибутов не совпадает с множеством всех атрибутов отношения ).

Определение 7 . Собственные проекции and relations называются декомпозицией без потерь , если отношение точно восстанавливается из них при помощи естественного соединения для любого состояния отношения :

.

Рассмотрим пример, показывающий, что декомпозиция без потерь происходит не всегда.

Пример 2 . Пусть дано отношение :

НОМЕР	ФАМИЛИЯ	ЗАРПЛАТА
one	Ivanov	1000
2	Петров	1000

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

Рассмотрим первый вариант декомпозиции отношения на два отношения:

НОМЕР	ЗАРПЛАТА
one	1000
2	1000

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

ФАМИЛИЯ	ЗАРПЛАТА
Ivanov	1000
Петров	1000

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

Естественное соединение этих проекций, имеющих общий атрибут "ЗАРПЛАТА", очевидно, будет следующим (каждая строка одной проекции соединится с каждой строкой другой проекции):

НОМЕР	ФАМИЛИЯ	ЗАРПЛАТА
one	Ivanov	1000
one	Петров	1000
2	Ivanov	1000
2	Петров	1000

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

Итак, данная декомпозиция не является декомпозицией без потерь, т.к. исходное отношение не восстанавливается в точном виде по проекциям (серым цветом выделены лишние кортежи).

Рассмотрим другой вариант декомпозиции:

НОМЕР	ФАМИЛИЯ
one	Ivanov
2	Петров

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

НОМЕР	ЗАРПЛАТА
one	1000
2	1000

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

По данным проекциям, имеющие общий атрибут "НОМЕР", исходное отношение восстанавливается в точном виде. Тем не менее, нельзя сказать, что данная декомпозиция является декомпозицией без потерь, т.к. мы рассмотрели только одно конкретное состояние отношения , и не можем сказать, будет ли и в других состояниях отношение восстанавливаться точно. Например, предположим, что отношение перешло в состояние:

НОМЕР	ФАМИЛИЯ	ЗАРПЛАТА
one	Ivanov	1000
2	Петров	1000
2	Сидоров	2000

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

Кажется, что этого не может быть, т.к. значения в атрибуте "НОМЕР" повторяются. Но мы же ничего не говорили о ключе этого отношения! Сейчас проекции будут иметь вид:

НОМЕР	ФАМИЛИЯ
one	Ivanov
2	Петров
2	Сидоров

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

НОМЕР	ЗАРПЛАТА
one	1000
2	1000
2	2000

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

Естественное соединение этих проекций будет содержать лишние кортежи:

НОМЕР	ФАМИЛИЯ	ЗАРПЛАТА
one	Ivanov	1000
2	Петров	1000
2	Петров	2000
2	Сидоров	1000
2	Сидоров	2000

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

Conclusion. Таким образом, без дополнительных ограничений на отношение нельзя говорить о декомпозиции без потерь.

Такими дополнительными ограничениями и являются функциональные зависимости. Имеет место следующая теорема Хеза [54]:

Теорема (Хеза) . Let be является отношением, и - атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость , то проекции and образуют декомпозицию без потерь.

Proof . Необходимо доказать, что для любого состояния отношения . В левой и правой части равенства стоят множества кортежей, поэтому для доказательства достаточно доказать два включения для двух множеств кортежей: and .

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

Докажем обратное включение . Возьмем произвольный кортеж . Докажем, что он включается также и в . По определению естественного соединения получим, что в имеются кортежи and . Because , то существует некоторое значение , такое что кортеж . Аналогично, существует некоторое значение , такое что кортеж . Кортежи and имеют одинаковое значение атрибута , равное . Из этого, в силу функциональной зависимости , следует, что . Таким образом, кортеж . Обратное включение доказано. Теорема доказана .

Comment. В доказательстве теоремы Хеза наличие функциональной зависимости не использовалось при доказательстве включения . Это означает, что при выполнении декомпозиции и последующем восстановлении отношения при помощи естественного соединения, кортежи исходного отношения не будут потеряны . Основной смысл теоремы Хеза заключается в доказательстве того, что при этом не появятся новые кортежи , отсутствовавшие в исходном отношении.

Because алгоритм нормализации (приведения отношений к 3НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т.е. в ходе нормализации не происходит потери информации .

findings

При разработке базы данных можно выделить несколько уровней моделирования:

• Сама предметная область
• Модель предметной области
• Логическая модель данных
• Физическая модель данных
• Собственно база данных и приложения

Ключевые решения, определяющие качество будущей базы данных закладываются на этапе разработки логической модели данных. "Хорошие" модели данных должны удовлетворять определенным критериям:

• Адекватность базы данных предметной области
• Легкость разработки и сопровождения базы данных
• Скорость выполнения операций обновления данных (вставка, обновление, удаление)
• Скорость выполнения операций выборки данных

Первая нормальная форма ( 1НФ ) - это обычное отношение. Отношение в 1НФ обладает следующими свойствами:

• В отношении нет одинаковых кортежей.
• Кортежи не упорядочены.
• Атрибуты не упорядочены.
• Все значения атрибутов атомарны.

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

Отношение находится во второй нормальной форме ( 2НФ ) тогда и только тогда, когда отношение находится в 1НФ и нет неключевых атрибутов, зависящих от части сложного ключа.

Отношения в 2НФ "лучше", чем в 1НФ, но еще недостаточно "хороши" - остается часть аномалий обновления, по-прежнему требуются триггеры, поддерживающие целостность базы данных.

Отношение находится в третьей нормальной форме ( 3НФ ) тогда и только тогда, когда отношение находится в 2НФ и все неключевые атрибуты взаимно независимы.

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

Переход от ненормализованных отношений к отношениям в 3НФ может быть выполнен при помощи алгоритма нормализации . Алгоритм нормализации заключается в последовательной декомпозиции отношений для устранения функциональных зависимостей атрибутов от части сложного ключа (приведение к 2НФ) и устранения функциональных зависимостей неключевых атрибутов друг от друга (приведение к 3НФ).

Корректность процедуры нормализации (декомпозиция без потери информации) доказывается теоремой Хеза .

Продолжение:

Часть 1 6. Normal forms of relationships. Database Design, Types of Normal Forms
Часть 2 - 6. Normal forms of relationships. Database Design, Types of