НАУКА и ОБРАЗОВАНИЕ

УДК 681.3.07

                                                                           А.В. Брешенков, В.В. Белоус

Отношения (реляционные таблицы) приведены к 4-й нормальной форме, если в них отсутствуют многозначные зависимости [1, 2].

Для формулировки и пояснения цели работы рассмотрим пример, приведенный в форме табл. 1.

                                                                                  Т а б л и ц а  1

Для компактности примера при записи значений атрибутов использованы мнемонические обозначения.

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

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

При проектировании реляционных таблиц  в соответствии с требованиями их нормализации [2] множественные зависимости не допускаются. В случае же заполненных таблиц, которые импортируются или задействованы в базе данных,  зависимости такого рода вполне могут быть и от них необходимо избавляться.

Предлагается следующий способ избавления от многозначных зависимостей.

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

Прежде, чем предложить формальный алгоритм, проиллюстрируем алгоритм на примере.

После сканирования таблицы и анализа всех возможных кортежей атрибутов выявляются две группы кортежей атрибутов, конкатенации значений которых повторяются. Эти таблицы (отношения) R1 и R2, представлены ниже. Отношение R1 приведено в табл. 2.  Отношение R2 приведено в табл. 3.

                     Т а б л и ц а  2                                                        Т а б л и ц а  3

В отношениях R1 и R2 исключаем дублирование записей. В результате получаем новые отношения  R1' и R2’ (табл. 4 и табл. 5).

                            Т а б л и ц а  4                                                         Т а б л и ц а  5

Приписываем к отношениям  R₁’ и R₂’ ключевые столбцы типа COUNTER. В результате таблицы примут вид табл. 6 и табл. 7.

                          Т а б л и ц а  6                                                   Т а б л и ц а  7

Теперь перебираем все записи отношения R1. Для каждой записи ищем ее позицию   в R1’, запоминаем ее в K1. В R2 выбираем соответствующую запись, ищем ее позицию в R2’, запоминаем ее в K2. Формируем новую запись отношения R3 = (K1, K2). Записываем K1, K2 в  соответствующие поля отношения R3.

Например, 1-я запись в R1 находится в 1-й позиции R1’.  K1 =1. Соответствующая запись в R2 находится в  1-й позиции R2’.  K2 =1.

В результате перебора всех записей R1  и выполнения описанных действий  будет сформировано отношение R3 вида (табл. 8).

Т а б л и ц а  8

Полученное отношение обеспечивает связь “¥ : ¥” между отношениями R1’ и R2’.

При необходимости можно сформировать запрос на основе таблиц R1’, R2’ и R3’, который позволит сформировать исходное отношение.

Даже в этом небольшом примере очевидна экономия памяти. В R задействовано 54 поля, в  R1’, R2’ и R3 – 39 полей. На основе изложенного предлагается следующий формализованный алгоритм приведения заполненных таблиц к 4-й нормальной форме.

П1: Выявление групп кортежей атрибутов, конкатенации значений которых повторяются

FOR r = 1   то  k–1, k ¹ NK 

     A = A_r

     F = 0

     FOR q = r + 1 то k-1, k ¹ NK

         A = concat (A, A_q)

         C = SELECT A FROM R GROUP BY A;

         IF C = 1 THEN

              A = A - A_q

         ELSE

              F = 1

         END IF

     NEXT q

     IF F = 1  THEN PRINT(A)

NEXT r

Здесь:  k – степень R.

NK – номер ключевого атрибута;

Выражение SELECT A FROM R GROUP BY A; - SQL–подобная команда, позволяющая подсчитать количество повторяющихся значений с набором атрибутов А. Результат его выполнения – множество чисел. Каждое число соответствует количеству повторений какого–либо набора значений атрибутов.

С – множество этих чисел.

Выражение С = 1 означает, что повторений значений атрибутов нет. (С – единичное множество).

Выражение A = A - A_q означает исключение из конкатенации атрибутов атрибута A_q.

П2: Формирование таблиц без внутренних зависимостей.

R1 = Проекция A из R.

A1 = AR – A

R2 = Проекция A’ из R.

Исключение дублирования.

R1’ = SELECT A FROM R1 GROUP BY A

R2’ = SELECT A FROM R2 GROUP BY A’

Здесь проекция A из R означает операцию реляционной алгебры – проекцию, которая выполняется над отношением R. Атрибуты проекции составляют множество A. Ограничений при выборе нет. Другими словами, формируется таблица со столбцами из множества А.

AR – множество атрибутов R;

Строго говоря, при выполнении команды ”Проекция” дублирование записей исключается. Однако для большей прозрачности алгоритма и удобства его реализации приведены две последние команды.

Назначение R1’ и R2’ ключевых атрибутов

 A = A + N1

 A’ = A’ + N2,

где N1 – ключевой атрибут типа COUNTER для отношения R2', N2 – ключевой атрибут типа COUNTER для отношения R2’.

П3: Формирование таблицы для организации связей между R1’ и R2’.

FOR f = 1 то m

     C1  = 0

     FOR f1 =1 то m1

            C1 = C1 + 1

            IF S_f(R1) = S_f1(R1’) THEN GOTO M1

     NEXT f1

     M1: C2 = 0

     FOR f2 = 1 то m2

           C2  = C2 + 1    

           IF S_f (R2) = S_f2 (R2’) THEN GOTO M2

      NEXT f2

      M2: r3_f,1 = C1

      r3_f,2 = C2

NEXT f

Здесь m - мощность R1, R2;

m1 – мощность R1’;

m2 – мощность R2’;

S_f (R2) – список значений f-й строки отношения R1.

S_f1(R1’) - список значений строки f₁ отношения R1’ (из списка исключено значение ключевого атрибута).

Аналогично S_f (R2) и S_f2 (R2’).

r3_f,1 – значение 1-го атрибута f-й строки отношения R3.

r3_f,2 – значение 2-го атрибута f-й строки отношения R3.

Важно отметить, что предложенный алгоритм позволяет исключить одну множественную зависимость в отношении R. Не исключено, что в  отношениях R1' и R2' могут также быть множественные зависимости, хотя это случается редко. Прерогатива разработчика – проверить R1' и R2' на наличие множественных зависимостей.

В случае необходимости с помощью соответствующего запроса из полученных 3-х отношений легко получить нужную информацию.

Выполним попытку нормализовать таблицу 1 стандартными средствами СУБД Microsoft Access. В формате Microsoft Access она представлена на рис.1

Рис. 1. Исходная таблица в формате Microsoft Access

После запуска мастера (меню Сервис/Анализ/таблица) и выбора данной таблицы Microsoft Access сформирует следующее сообщение (рис. 2).

Рис. 2. Сообщение Acces

Т.е. использование мастера не позволяет выполнить действия по приведению таблицы к 4-й нормальной форме. Мастер рекомендует использование средств самостоятельного разделения. Далеко не всегда в реальных таблицах с большим числом столбцов и записей разработчик может выделить поля, которые можно сгруппировать. Однако можно попытаться нормализовать таблицу посредством предлагаемых средств. Включение соответствующего мастера приведет к формированию окна мастера, приведенного на рис. 3.

Рис.  3. Окно мастера анализа таблиц

Если разработчик сможет догадаться, что поля “Исполнитель” и “Звание исполнителя” должны принадлежать отдельной таблице, то он может перетащить эти поля в новую таблицу. Результат преобразования представлен на рис. 4.

Рис. 4. Результат преобразования

К сожалению, если разработчик подозревает о наличии связи многие - ко многим, с использованием рассматриваемых средств он не сможет создать третью объединяющую таблицу. Поэтому будет сформировано две таблицы (рис. 5 и рис. 6).

Рис. 5. Вид Таблицы1

Рис. 6. Вид Таблицы2

Некоторое улучшение состояния дел произошло в таблице Таблица2, в ней значительно меньше записей, чем в исходной таблице. Однако от связи многие - ко многим избавиться не удалось.

Выполним манипуляции в рамках Microsoft Access, которые необходимы для приведения  отношения,  представленного на рис. 1 к 4-й нормальной форме.

Посредством следующего запроса сформируем новую таблицу на базе исходной таблицы:

SELECT Песни.Песня, Песни.Слова, Песни.Музыка INTO Песня

FROM Песни;

Здесь создается новая таблица “Песня’. Она формируется на основе полей “Песня”, “Слова” и “Музыка” из таблицы “Песни”. В результате выполнения запроса сформируется таблица, представленная на рис 7.

Рис. 7.  Таблица песен, сформированная на базе исходного отношения

Для исключения дублирования записей в таблице,  приведенной на рис.7 и создания таблицы без дублирования используется следующий запрос:

SELECT DISTINCT Песня.Песня, Песня.Слова, Песня.Музыка INTO Песня1

FROM Песня;

В данном запросе на базе таблицы “Песня” формируется таблица “Песня1”. Конструкция DISTINCT позволяет передать записи в новую таблицу без дублирования. В результате выполнения данного запроса сформируется таблица, приведенная на рис. 8.

Рис. 8. Таблица без дублирования записей

Теперь для полученной таблицы сформируем ключевое поле типа “Счетчик”. Для этого откроем данную таблицу в режиме Конструктора и добавим к списку ее полей нужное поле. На рис. 9 приведена модифицированная таблица в режиме Конструктора.

Рис. 9. Модифицированная таблица в режиме Конструктора

Вид модифицированной таблицы в режиме Просмотра показан на рис. 10. Следует обратить внимание на то, что в свойстве ”Индексированное поле” нового поля ”Код поля” выбрана опция “Да (Совпадения не допускаются)”. Это обеспечивает уникальность поля ”Код поля”.

Рис. 10. Вид модифицированной таблицы в режиме Просмотра

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

Эта другая таблица включает в себя поля ”Исполнитель” и ”Звание исполнителя”. Выполнив манипуляции с исходной таблицей, подобные манипуляциям, проделанным выше, получим новую таблицу, которая представлена на рис. 11.

Рис. 11. Вид полученной таблицы исполнителей в режиме Просмотра

Следующим шагом приведения исходного отношения к 4-й нормальной форме является создание таблицы из ключевых полей построенных таблиц, которые приведены на рис. 10 и 11.

В режиме Конструктора данная таблица выглядит в соответствии с рис.12.

Рис. 12. Таблица для организации связей, представленная в режиме Конструктора

Следует обратить внимание на то, что типы полей выбраны  ”Длинное целое”. Так сделано в связи с тем, что эти поля предполагается использовать для связывания с соответствующими полями таблиц, которые приведены на рис. 10 и 11. Типы полей для связывания должны совпадать. А в таблицах, которые приведены на рис. 10 и 11, соответствующие поля имеют тип ”Счетчик”. Для формирования значения поля типа ”Счетчик” используется тип данных ”Длинное целое”.

В свойствах полей “Индексированное поле” выбраны значения ”Да (Допускаются совпадения)”. Это сделано в связи с тем, что по данным полям могут сортироваться  записи, кроме того, значения данных полей могут повторяться.

Следующим шагом приведения исходного отношения к 4-й нормальной форме является построение схемы данных из 3-х сформированных таблиц.

Очередным шагом приведения исходного отношения к 4-й нормальной форме является заполнение таблицы ”Связи”, которая связывает таблицы ”Песня1” и ”Исполнитель1”. Для этого можно вывести на экран содержимое 4-х таблиц: исходной, ”Песня1”, ”Исполнитель1” и таблицы ”Связи”. Затем в соответствии с ранее изложенным алгоритмом вручную заполнить таблицу ”Связи”.

На рис. 13 приведена соответствующая экранная форма.

Рис. 13. Экранная форма с 4-я таблицами, открытыми в режиме Просмотра, редактирования и ввода данных

После заполнения таблицы ”Связи” в соответствии с предложенным алгоритмом она примет вид, приведенной на рис. 14.

Рис. 14. Экранная форма с 4-я таблицами и заполненной  таблицей ”Связи”

Собрать данные в одну таблицу из 3-х теперь можно с помощью запроса, бланк которого приведен на рис. 15.

Рис. 15. Бланк запроса для сбора данных из трех таблиц

В формате SQL данный запрос выглядит следующим образом:

SELECT Песня1.Песня, Песня1.Слова, Песня1.Музыка, Исполнитель1.Исполнитель, Исполнитель1.[Звание исполнителя]

FROM Песня1 INNER JOIN (Исполнитель1 INNER JOIN Связи ON Исполнитель1.[Код исполнителя] = Связи.[Код исполнителя]) ON Песня1.[Код песни] = Связи.[Код песни]

ORDER BY Песня1.Песня;

Посредством этого запроса из  двух таблиц выбирается пять полей. Первая конструкция  INNER JOIN позволяет выбирать данные, в которых ключевые поля совпадают  ( Исполнитель1.[Код исполнителя] = Связи.[Код исполнителя]). Вторая конструкция  INNER JOIN позволяет выбирать данные, в которых другие ключевые поля совпадают (Песня1.[Код песни] = Связи.[Код песни]). Посредством конструкции “ORDER BY Песня1.Песня” выполняется сортировка выводимых данных по полю “Песня” таблицы ”Песня1”.

Результат выполнения данного запроса представлен на рис. 16.

Рис. 16. Результат выполнения запроса, сформированного для сборки данных из трех таблиц

Как видно из рисунка результат выполнения запроса полностью совпадает с исходной таблицей.

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

Список литературы.

1.    Codd E.F. Further normalization of the database relational model, in data­ base systems (R. Rustin, ed.). Prentice Hall, Endlewood Cliffs, NJ, 1972.

2.    Дейт К., Дж. Введение в системы баз данных. 8-е изд.: Пер. с англ.- М.: Вильямс, 2005. - 1328 с.

3.    Брешенков А.В. Неформальная постановка проблемы преобразования   информации  табличного вида в файлы баз данных.  Сб. трудов АУ МВД  России "Актуальные вопросы технологий в деятельности органов внутренних дел". - М.: 2004. – 20 с.