Графическое представление реинжиниринга концептуальной схемы реляционной базы данных на основе требований нормализации

Размещено на http://www.allbest.ru/

Графическое представление реинжиниринга концептуальной схемы реляционной базы данных на основе требований нормализации

Россия, г. Орёл

Annotation

In this article discussed the problem of reengineering of the initial conceptual scheme of a relational database is considered in view of requirements of normalization. Basically approaches to the normalization, the schemes of a database connected to designing are considered on the basis of initial set of functional dependencies. It is shown, that it is possible to represent initial set of functional dependencies as conceptual scheme. It is shown how graphically to define in conceptual scheme the places breaking normalization. Such approach besides allows to proceed from designing to reengineering.

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

При построении нормализованной реляционной схемы БД на основе множества функциональных зависимостей обычно используют два известных подхода. Один из них состоит в декомпозиции универсального отношения (УО), другой - в синтезе схемы БД.

Процесс декомпозиции на входе имеет универсальное отношение и множество функциональных зависимостей (ФЗ), на выходе - реляционную схему в к.-л. нормальной форме (НФ), например, третьей НФ (3НФ), нормальной форме Бойса-Кодда (НФБК). Декомпозиция последовательно разбивает к.-л. отношение из множества имеющихся (вначале в этом множестве будет находиться одно УО) в том случае, если это отношение нарушает заданную НФ благодаря к.-л. ФЗ. Метод декомпозиции имеет множество недостатков /1,2/, в частности, незавершённость в смысле удовлетворения НФ (в силу возможности присутствия скрытых ФЗ), излишнее количество отношений, чувствительность к порядку декомпозиции (что означает своего роду субъективность процесса). Что касается УО, то оно служит для запуска всего процесса. По сути в нём находятся все атрибуты предметной области. Иногда можно положить, что УО подразумевается множеством ФЗ, т.е. если «собрать» все атрибуты, имеющиеся во всех ФЗ, получим УО. Иногда это не так, т.е. присутствуют атрибуты, не участвующие ни в одной ФЗ.

Обычно полагается (в классической постановке), что процесс синтеза на входе имеет только множество ФЗ. Каждая такая ФЗ служит своего рода атомарным отношением, поэтому и говорят о процессе синтеза, т.е. эти отношения последовательно объединяются, пока не получится макет, удовлетворяющий заданной ФЗ. Кстати, обычно в качестве ФЗ используется 3НФ. Это связано с тем, что для 3НФ можно построить макет БД, по многим критериям являющийся оптимальным /2/. Причём он будет лишён всех недостатков, характерных для схемы, полученной в результате декомпозиции, да и сам алгоритм во временном отношении выигрывает. Как только же речь заходит о НФБК, приходится выбирать компромиссы /3/. Дело в том, что два желательных свойства конечного макета БД - сохранение без потерь и сохранение исходного множества ФЗ - действуют здесь в противоположных направлениях /4/. Ситуация осложняется тем, что для удовлетворения НФБК приходится прибегать к методу декомпозиции со всеми связанными с ним недостатками, такими, как «субъективность» и избыточность, не говоря уже о временной сложности алгоритма. Поэтому в рамках этой статьи мы ограничимся 3НФ.

Существует модификация алгоритма синтеза - известный алгоритм Бернштейна. Модификация состоит в том, что в дело вводится новая ФЗ, которая в качестве детерминанта имеет, по сути, УО, а в качестве зависимого атрибута вводится новый атрибут, не входящий в состав УО, который затем исключается из того отношения, в какое он попал ( в качестве варианта используется та версия алгоритма, где справа и слева в новой ФЗ присутствует УО). Этим сразу достигается две цели. Во-первых, в дело вводятся те атрибуты, которые могли не присутствовать в исходном множестве ФЗ (МФЗ). Во-вторых, этим шагом обеспечивается выполнение требование сохранения без потерь. Но на практике часто оказывается, что этот шаг вводит в действие новую сущность (именно в ней будет в конце присутствовать суррогатный атрибут; назовём эту сущность сущностью Бернштейна), которая совершенно не нужна. Дело в том, что зачастую в предметной области содержится многозначная ФЗ, наличие которой и обеспечивает свойство сохранения без потерь. Введённая же сущность Бернштейна таким образом содержит в себе повторяющиеся группы атрибутов /3/. Во всём остальном алгоритм Бернштейна превосходен /2/.

Приведённые выше алгоритмы исходят из того, что мы имеем МФЗ и начинаем проектировать реляционную схему предметной области. По сути, реляционная схема есть взгляд на предметную область. Более того, с помощью реляционных схем бывает достаточно удобно «смотреть» на предметную область. И хотя стандартом проектирования является сначала выделение бизнес-процессов, их декомпозиция, а затем - выделение отсюда реляционной схемы (что отражает известная связка BPWin ERWin), обычно проектировщик БД заранее представляет предметную область в виде реляционной схемы. Это можно сравнить с программированием. Вряд ли сегодня найдётся хоть один стоящий и уважающий себя программист, который станет старательно согласно ГОСТ вырисовывать блок-схему, а затем приступать к программе. Как известно, блок-схемы давно изжили себя и заменены более оптимальными инструментами, например, методом пошаговой детализации псевдокода. Здесь дело в том, что псевдокод - естественная модель, естественный взгляд программиста на процессы. Аналогично, как видится автору данной статьи, естественным взглядом проектировщика БД на предметную область будет именно концептуальная схема, а не бизнес-процессы или даже ФЗ.

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

За счёт такого представления исходных данных на самом деле автоматически расширяется круг решаемых задач. На самом деле, теперь можно уже говорить не о проектировании КС, а о реинжиниринге КС, т.е., имея на входе некоторую исходную КС, на выходе создаём нормализованную. Таким образом, во-первых, мы способны не только проектировать, но и корректировать к.-л. имеющуюся КС с учётом требований нормализации, а во-вторых, мы свели проектирование к реинжинирингу.

Переименование

На самом деле это не совсем так. Для того, чтобы перейти к реинжинирингу, необходимо решить некоторую промежуточную задачу. Алгоритмы нормализации пока работают только с МФЗ. Как можно представить КС в виде МФЗ? Ответ напрашивается следующий: необходимо переименовать атрибуты, входящие в состав КС. Это необходимо для того, чтобы задать одинаковые имена атрибутам, служащими внешним ключом, и соответствующим атрибутам, составляющими (если их несколько) ключ отношения-родителя. Кстати, все остальные атрибуты должны иметь различные имена, хотя, понятное дело, в исходной КС они могут именоваться совершенно одинаково.

Каков должен быть алгоритм переименования? Казалось бы, всё просто: встречаем два отношения, связанные между собой ограничениями целостности, и осуществляем переименование, и так по всем связям. Однако не всё так просто. Иногда встречаются ситуации, когда приходится идти по цепочке, т.к. в результате предыдущих переименований атрибутов некоторые атрибуты в разных отношениях стали именоваться одинаково. Может даже показаться следующее. Отношения могут образовывать цикл с помощью связей (никто же не запрещал подобного, во всяком случае, в исходном макете). Не придётся ли нам ходить по кругу в процессе переименования и тем самым зациклиться?

Ответ на этот вопрос следующий: нет, не придётся. Нам достаточно один раз рассматривать каждую связь и достаточно один раз переименовать каждый атрибут, участвующий в связи с одной стороны, правда, придётся переименовать его во всех отношениях, где он имеется. Таким образом, выяснился алгоритм. Для каждого атрибута храним информацию обо всех отношениях, где он встречается, эту информацию динамически используем и изменяем. Временная сложность составляет порядка n*m, где n - количество связей, m - количество отношений.

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

Вопрос о соответствии ФМЗ и КС

Казалось бы, всё - теперь можно запускать любой алгоритм нормализации, например, алгоритм Бернштейна, и получаем готовый макет! Однако не всё так просто. После нам придётся решать обратную задачу - из МФЗ придётся конструировать макет. Поэтому неизбежно возникает вопрос следующего характера: существует ли взаимно однозначное соответствие МФЗ и КС? Ответ на этот вопрос может показаться печальным: такое взаимно однозначное соответствие в общем случае не соблюдается. Это не трудно определить, если взять какой-нибудь цикл поинтереснее и погонять по нему алгоритм переименования.

Однако можно доказать следующее. Если макет определённого вида, то такое соответствие существует.

Заменим КС графом, узлам которого соответствуют отношения, а дугам - связи. Назовём его КС-орграф. Если КС-орграф, не содержит двух различных путей от одной вершины к другой, то такое взаимно однозначное соответствие существует.

Это нетрудно доказать (что, к сожалению, выходит за рамки объёма данной статьи). Действительно, если подумать, для такого графа нетрудно по МФЗ восстановить ключи в КС.

Назовём КС-орграф, не содержит двух различных путей от одной вершины к другой, правильным (ПКС-орграф), а соответствующую КС - ПКС (аналогично).

Нарушение ПКС

Может возникнуть закономерный вопрос: а что делать, если ПКС нарушается? Ответ следующий: нормализованный макет - обязательно ПКС, т.е. нарушения не происходит. Т.е. если перед нами МФЗ, полученное в результате нормализации, реинжиниринга, то МФЗ определяет КС путём несложного алгоритма.

Дело в том, что может существовать всего два нарушения ПКС: цикл и сросшиеся ветви. Оба они недопустимы в МФЗ.

Цикл

Давайте рассмотрим цикл в КС-орграфе. Нетрудно признать следующее: каждая дуга в КС-орграфе соответствует ФЗ, детерминантом которой служит выделенный ключ отношения-потомка, а зависимой частью выступает выделенный ключ отношения-родителя.

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

Сросшиеся ветви

Это самый интересный случай.

Интуитивно понятно, что двойное определение ФЗ несёт в себе семантическую избыточность. Так оно и оказывается.

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

Рассмотрим несколько вариантов.

1) На рисунке 1 первая сущность определяет вторую и транзитивно по тому же ключу - третью сущность.

Рисунок 1 - Пример слияния сущностей (до и после переименования)

Видно, что вторая и третья сущности сливаются в одну. После слияния останутся две сущности и одна связь между ними.

Рисунок 2 - Пример удаления связи (до и после переименования)

Здесь первая сущность определяет третью по одному ключу, а транзитивно - по другому ключу. Нетрудно догадаться, что после нормализации из первой сущности пропадёт атрибут G, в результате чего связь от первой сущности до третьей исчезнет.

Рассмотрим ещё один интересный случай, представленный на рисунке 3. Здесь имеет место непосредственная определяемость атрибутами AB атрибута C. В результате соответствующие сущности сольются в одну определяемую, в результате чего получим ПКС.

Рисунок 3 - Пример непосредственной определяемости (после переименования)

Можно доказать, что слияние по непосредственной определяемости может иметь место только в сущностях - началах и концах разветвления.

Резюме

1. Можно перейти сразу от рассмотрения МФЗ к рассмотрению КС.

2. Для этого сначала необходимо выполнить процедуру переименования и обратную процедуру после нормализации (что возможно).

3. Графическое представление позволяет сразу же наглядно увидеть места, в которых происходит нарушение НФ. Это возможно в двух случаях: циклы и сросшиеся ветви.

4. Такой подход позволяет автоматически рассматривать проблемы реинжиниринга КС.

P.S.

Дополнительные преимущества

Возможно более широко рассматривать проблему реинжиниринга, где на входе имеется КС и дополнительное МФЗ.

Проблемы

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

Литература

1. Ульман Д.Д. Введение в системы баз данных. -М.:Лори,2000.-374с.

2. Мейер Д. Теория реляционных баз данных: Пер. с англ. - М.: Мир, 1987.

3. Шелаев А.И. ПРОБЛЕМЫ СИНТЕЗА СХЕМ БАЗ ДАННЫХ В НФБК //Материалы первой Международной научно-практической интернет-конференции "ЭНЕРГО- И РЕСУРСОСБЕРЕЖЕНИЕ - XXI ВЕК". Орел, 2002 (http://www.ostu.ru/conf/ers2002/sect3/shelaev.html).

4. Дейт К. Введение в системы баз данных (6-е изд.). М.: Диалектика, 1998.

5. Тиори Т., Фрай Дж. Проектирование структур баз данных. М.: Мир, 1985.

Размещено на Allbest.ru