Сегодня, в эпоху быстро меняющегося цифрового мира оставаться в темпе событий сложно. Чтобы успеть все, необходимо правильно ставить задачи, цели, распределять и делегировать полномочия. Логика и анализ - лучшие помощники в решении сложных задач. Одним из инструментов логического построения является декомпозиция. Рассмотрим ее подробно.

Определение

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

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

Особенности

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

1) Всегда должна быть соблюдена уровневая система.

Метод декомпозиции основан на подчинении более низкого уровня более высокому. Это достигается путем построения иерархической структуры с помощью так называемых «деревьев».

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

Руководствуясь простой формальной алгеброй и логикой можно также строить «деревья И» и «деревья ИЛИ».

2) Расчленение целого на части должно происходить только по одному признаку.

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

В качестве признака можно использовать также временные рамки (сроки), предметные характеристики, структурные признаки, технологические характеристики и другие.

3) Все подсистемы декомпозиции должны раскрывать суть системы.

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

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

4) Глубина декомпозиционной проработки должна быть определена на начальном этапе.

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

Классификация

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

Как правило, все перечисленные процессы взаимосвязаны и в целом представляют полную декомпозиционную структуру.

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

Анализ действий

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

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

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

Классический прием

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

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

Применение в бизнесе

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

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

В качестве примера рассмотрим проект строительства объекта капстроительства. Разработка осуществляется в 2 стадии: рабочая документация и проектная документация. Это будут подзадачи первого уровня. На работы будут представлены сметными проработками и проектами. На рабочей стадии так же. Это подзадачи второго уровня. К примеру, проект обычно представлен в виде следующих частей:

• общая пояснительная записка;
• архитектурные решения;
• конструктивные и объемно-планировочные решения.

• система электроснабжения;
• система водоснабжения;
• система водоотведения;
• отопление, вентиляция и кондиционирование воздуха, тепловые сети;
• сети связи;
• система газоснабжения;
• технологические решения.

Разделы и подразделы проектной и рабочей документации - это подзадачи третьего уровня.

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

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

Коротко о главном

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

Декомпозицией схемы отношения R = {А 1 , А 2 , ...,А n } называется замена ее совокупностью подмножеств R , таких, что их объединение дает R . При этом допускается, чтобы подмножества были пересекающимися .

Алгоритм декомпозиции основан на следующей теореме.

Теорема о декомпозиции . Пусть R(A, B, C) – отношение , A, B, C – атрибуты .

Если R удовлетворяет зависимости A->B , то R равно соединению его проекций A, B и A, C

R(A, B, C) = R(A, B), R(A, C)

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

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

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

8.4 .Выбор рационального набора схем отношений путем нормализации

Вторая нормальная форма (2НФ)

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

Для перевода отношения в 2НФ необходимо, используя операцию проекции , разложить его на несколько отношений следующим образом:

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

Третья нормальная форма (3НФ)

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

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

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

Мотивировка третьей нормальной формы

Третья нормальная форма исключает избыточность и аномалии включения и удаления .

К сожалению, 3НФ не предотвращает все возможные аномалии.

Нормальная форма Бойса-Кодда (НФБК)

Если в R для каждой зависимости X->A , где А не принадлежит X, X включает в себя некоторый ключ, то говорят, что данное отношение находится в нормальной форме Бойса-Кодда .

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

Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом .

НФБК является более строгой версией 3НФ. Иными словами, любое отношение, находящееся в НФБК, находится в 3НФ. Обратное неверно .

Мотивировка нормальной формы Бойса-Кодда

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

8.5. Пример нормализации до 3НФ

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

Продолжим рассмотрение примера с отношением ЭКЗАМЕНАЦИОННАЯ ВЕДОМОСТЬ

В начале этой лекции мы привели отношение к первой нормальной форме .

Код студента	Фамилия	Код экзамена	Предмет	Дата	Оценка
1	Сергеев	1	Математика	5.08.03	4
2	Иванов	1	Математика	5.08.03	5
1	Сергеев	2	Физика	9.08.03	5
2	Иванов	2	Физика	9.08.03	5

Ключом данного отношения будет совокупность атрибутов – Код студента и Код экзамена.

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

КС – код студента, КЭ – код экзамена, Ф – фамилия, П – предмет, Д – дата, О - оценка.

Выпишем функциональные зависимости

КС, КЭ -> Ф, П, Д, О КС, КЭ -> Ф КС, КЭ -> П КС, КЭ -> Д КС, КЭ -> О КЭ -> П КЭ -> Д КС -> Ф

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

Имеем отношение R(КС, Ф, КЭ, П, Д, О) . Возьмем зависимость КС -> Ф в соответствии с формулировкой теоремы исходное отношение равно соединению его проекций R1(КС, Ф) и R2(КС, КЭ, П, Д, О) .

В отношении R1(КС, Ф) существует функциональная зависимость КС -> Ф , ключ КС – составной, не ключевой атрибут Ф не зависит от части ключа. Это отношение находится в 2НФ. Так как в этом отношении нет транзитивных зависимостей, отношение R(КС, Ф) находится в 3НФ, что и требовалось.

Рассмотрим отношение R2(КС, КЭ, П, Д, О) с составным ключом КС, КЭ . Здесь есть зависимость КЭ -> П, КЭ -> Д, КЭ -> П, Д . Атрибуты П,Д зависят от части ключа, следовательно

Декомпозиция отношений

Построение SADT-модели начинается с представления всей системы в виде простейшего компонента – одного блока и дуг, изображающих интерфейсы с функциями вне системы. Поскольку единственный блок отражает систему как единое целое, имя, указанное в блоке, является общим. Это верно и для интерфейсных дуг – они также соответствуют полному набору внешних интерфейсов системы в целом. Затем блок, который представляет систему в качестве единого модуля, детализируется на другой диаграмме с помощью нескольких блоков, соединенных интерфейсными дугами. Эти блоки определяют основные подфункции исходной функции. Данная декомпозиция выявляет полный набор подфункций, каждая из которых показана как блок, границы которого определены интерфейсными дугами. Каждая из этих подфункций может быть декомпозирована подобным образом в целях большей детализации.

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

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

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

Рисунок 13 - Функциональная модель предметной области «Мебельный салон». Диаграмма 0-го уровня

Рисунок 14 - Функциональная модель предметной области «Мебельный салон». Диаграмма 1-го уровня

Рисунок 15 - Функциональная модель предметной области «Мебельный салон». Диаграмма 2-го уровня

7.2.2 Проектирование с использованием метода «сущность-связь»

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

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

Базовыми понятиями проектирования с использованием метода «сущность-связь» являются: сущность, связь, атрибут.

Сущность (Entity) – реальный либо воображаемый объект, имеющий существенное значение для рассматриваемой предметной области. Необходимо различать такие понятия, как тип сущности и экземпляр сущности. Понятие «тип сущности» относится к набору однородных личностей, предметов, событий или идей, выступающих как целое. Экземпляр сущности относится к конкретной вещи в наборе. Например, типом сущности может быть ГОРОД, а экземпляром – Москва, Киев и т.д. Предметная область информационной системы - это совокупность реальных объектов (сущностей), которые представляют интерес для пользователей.

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

· иметь уникальное имя; к одному и тому же имени должна применяться одна и та же интерпретация; одна и та же интерпретация не может применяться к различным именам, если только они не являются псевдонимами;

· обладать одним или несколькими атрибутами, которые либо принадлежат сущности, либо наследуются через связь;

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

Каждая сущность может обладать любым количеством связей с другими сущностями модели.

Связь (Relationship) – поименованная ассоциация между двумя сущностями, значимая для рассматриваемой предметной области. Связь – это ассоциация между сущностями, при которой каждый экземпляр этой сущности ассоциирован с произвольным (в том числе нулевым) количеством экземпляров второй сущности, и наоборот.

Сущности, охваченные некоторой связью, называются участниками этой связи. Количество участников связи определяет степень типа связи. Типы связи по степени разделяют на:

· двухсторонние – связь, в которой участвуют две сущности;

· трехсторонние – относятся к сложным связям, в ней участвуют три сущности;

· четырехсторонние – относятся к сложным связям, в ней участвуют четыре сущности;

· рекурсивные – связь, в которой одни и те же сущности участвуют несколько раз в разных ролях. В этих случаях связям могут присваиваться ролевые имена.

Самой распространенной связью является двухсторонняя. Двухсторонние связи обычно обозначаются как «один к одному» (1:1), «один ко многим» (1:М), «многие ко многим» (М:М).

1:1 – взаимно однозначная связь, т.е. по обе стороны связи для любого значения в связующем аргументе имеется только одна запись. Например: один представитель администрации управляет одним отделением.

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

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

Связь может дополнительно определяться с помощью указания степени или мощности связи (количества экземпляров сущности–потомка, которое может существовать для каждого экземпляра сущности–родителя). При проектировании с использованием метода «сущность-связь» могут быть выражены следующие мощности связей:

· каждый экземпляр сущности–родителя может иметь ноль, один или более одного связанного с ним экземпляра сущности – потомка;

· каждый экземпляр сущности–родителя должен иметь не менее одного связанного с ним экземпляра сущности–потомка;

· каждый экземпляр сущности–родителя должен иметь не более одного связанного с ним экземпляра сущности–потомка;

· каждый экземпляр сущности–родителя связан с некоторым фиксированным числом экземпляров сущности–потомка.

Атрибут (Attribute) – любая характеристика сущности, значимая для рассматриваемой предметной области и предназначенная для квалификации, идентификации, классификации, количественной характеристики или выражение состояния сущности. Атрибут представляет тип характеристик или свойств, ассоциированных с множеством реальных или абстрактных объектов (людей, мест, событий, состояний, идей, предметов и т.д.). Экземпляр атрибута – это определенная характеристика отдельного элемента множества. Экземпляр атрибута определяется типом характеристики и ее значением, называемым значением атрибута. На диаграмме «сущность – связь» атрибуты ассоциируются с конкретными сущностями. Таким образом, экземпляр сущности должен обладать единственным определенным значением для ассоциированного атрибута.

Домен атрибута – набор допустимых значений одного или нескольких атрибутов. Например: домен адрес можно использовать для определения адреса сотрудника, поставщика, потребителя продукции.

Атрибуты можно разделить на:

· простой – атрибут, состоящий из одного компонента с независимым существованием. Простые или элементарные атрибуты не могут быть разделены на более мелкие компоненты. Например: оклад, фамилия, должность;

· составной – атрибут, состоящий из нескольких компонентов, каждый из которых характеризуется независимым существованием. Например: адрес;

· однозначный – атрибут, который содержит одно значение для каждого экземпляра сущности определенного типа. Например: дата рождения;

· многозначный – атрибут, который содержит несколько значений для каждого экземпляра сущности определенного типа. Например: телефоны, по которым можно связаться с сотрудником;

· производный – атрибут, который представляет значение, производное от значения связанного с ним атрибута или некоторого множества атрибутов, принадлежащих некоторому (не обязательно данному) типу сущности. Например: расчет по месяцам выплаты по ссуде.

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

· потенциальный ключ – атрибут или минимальный набор атрибутов, который однозначно идентифицирует каждый экземпляр сущности. Потенциальный ключ должен содержать значения, которые уникальны для каждого отдельного экземпляра сущности данного типа и не может содержать NULL. Например: Код должности в сущности Должности;

· первичный ключ – потенциальный ключ, который выбран для однозначной идентификации каждого экземпляра сущности определенного типа. Например: каждый сотрудник имеет уникальный табельный номер, а так-же уникальный номер карточки государственного страхования (ИНН). Первичным ключом может быть выбран любой из этих атрибутов, оставшийся можно рассматривать альтернативным ключом;

· составной ключ – потенциальный ключ, который состоит из одного или нескольких атрибутов. Например: сущность Приход товара можно идентифицировать атрибутом Код товара и Дата прихода.

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

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

7.2.3 Переход от ER–модели к реляционной

В настоящее время два последних этапа проектирования существенно сокращаются за счет использования автоматизированных средств проектирования. Переход к инфологической модели БД, а затем к физической схеме БД позволяет осуществить различные программные средства: IDEF0, ERWin, UML.

Правила преобразования моделей:

1. Каждая простая сущность превращается в таблицу. Простая сущность - сущность, не являющаяся подтипом и не имеющая подтипов. Имя сущности становится именем таблицы.

2. Каждый атрибут становится возможным столбцом с тем же именем; может выбираться более точный формат. Столбцы, соответствующие необязательным атрибутам, могут содержать неопределенные значения; столбцы, соответствующие обязательным атрибутам, - не могут.

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

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

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

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

7. Имеется два способа работы при наличии исключающих связей: общий домен (а) и явные внешние ключи (б). Если остающиеся внешние ключи все в одном домене, т.е. имеют общий формат (а), то создаются два столбца: идентификатор связи и идентификатор сущности. Столбец идентификатора связи используется для различения связей, покрываемых дугой исключения. Столбец идентификатора сущности используется для хранения значений уникального идентификатора сущности на дальнем конце соответствующей связи. Если результирующие внешние ключи не относятся к одному домену, то для каждой связи, покрываемой дугой исключения, создаются явные столбцы внешних ключей; все эти столбцы могут содержать неопределенные значения.

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

Введем определение декомпозиции схемы отношения .

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

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

Пример. Декомпозиция с потерей информации

Атрибуты А и В не зависят функционально от атрибута С .

Говорят, что декомпозиция схемы отношения r обладает свойством соединения без потерь относительно множества ФЗ D , если каждое отношение R , удовлетворяющее D , может быть представлено в виде:

Пусть Тогда для отображений проекции-соединения справедливы следующие свойства:

Эти свойства следуют из определения естественного соединения. Первое свойство используется при проверке, обладает ли декомпозиция свойством соединения без потерь относительно некоторого множества ФЗ.

Рассмотрим алгоритм проверки свойства соединения без потерь.

Алгоритм. Проверка декомпозиции на свойство соединения без потерь

input: схема отношения R(A 1 , A 2 , ..., A k), множество ФЗ F, декомпозиция d={R 1 , R 2 , ..., R k }. output: Булева переменная истина или ложь.

Алгоритм

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

Рассмотрим пример применения алгоритма, используя отношение ПОСТАВКИ (Поставщик, Адрес, Товар, Стоимость). Обозначим его атрибуты как: А - поставщик, В - адрес, C - товар, D - стоимость, при этом имеют место ФЗ

Пример. Проверка декомпозиции на свойство соединения без потерь

Схема отношения

Поскольку имеет место и две строки совпадают по А , то можно отождествить их символы для А: b 22 на a 2 . В итоге имеем таблицу

A	B	C	D
a 1	a 2	b 13	b 14
a 1	a 2	a 3	a 4

Вывод. Декомпозиция d обладает свойством соединения без потерь.

При декомпозиции одной схемы отношения на две другие схемы отношений используется более простая проверка: декомпозиция обладает свойством соединения без потерь, если только Такая ФЗ должна принадлежать F + .

Свойство соединения без потерь гарантирует, что любое отношение может быть восстановлено из его проекций. Понятно, что при декомпозиции ФЗ исходной схемы отношения распределяются по новым отношениям. Поэтому важно, чтобы при декомпозиции множество ФЗ F для схемы отношения r было выводимым из проекций на схемы R i .

Введем следующее определение.

Определение 2. Проекцией множества ФЗ F на множество атрибутов Х , обозначаемой называется множество ФЗ в F+ , таких, что

Говорят, что декомпозиция обладает свойством сохранения ФЗ, если из объединения всех ФЗ, принадлежащих логически следуют все зависимости из F .

Рассмотрим отношение (Город, Адрес, Почтовый_индекс). Обозначим его атрибуты как: А - город, В - адрес, C - почтовый индекс, при этом имеют место ФЗ Декомпозиция схемы этого отношения ABC на AC и BC обладает свойством соединения без потерь, поскольку верна ФЗ Однако проекция на BC дает только тривиальные зависимости, проекция на АС дает ФЗ и тривиальные ФЗ. Из ФЗ не следует зависимость Поэтому данная декомпозиция не сохраняет ФЗ, хотя и обладает свойством соединения без потерь.

Рассмотрим пример отношения, содержащего данные о студенте университета Иванове (таблица 7.1).

Таблица 7.1. Данные о студенте
Номер	Фамилия	Курсовые проекты	Предметы	Оценка	Комната	тел.
1000	Иванов		Математика		417	51-11
		Компиляторы	Системное программирование	5/4
			Физика
		Окисление серы	Химия	5/5

Пример. Универсальное отношение.

Видно, что данные содержат множественные поля, т.е. атрибуты неатомарны. Дублирование данных в атрибутах позволяет представить данные о студенте в форме отношения (таблица 7.2).

Таблица 7.2. Отношение СТУДЕНТ
Номер	Фамилия	Курсовые проекты	Предметы	Оценка	Комната	Тел.
1000	Иванов	Нет	Математика		417	51-11
1000	Иванов	Компиляторы	Системное программирование	5/4	417	51-11
1000	Иванов	Нет	Физика		417	51-11
1000	Иванов	Окисление серы	Химия	5/5	417	51-11

Если в отношение включены все атрибуты из предметной области базы данных, то его называют универсальным отношением . Универсальное отношение находится в 1НФ. Как известно, отношением в 1НФ порождается множество аномалий в обработке данных (обновление, удаление, добавление, избыточность). Для того чтобы поместить универсальное отношение в базу данных, его необходимо нормализовать - разбить на совокупность более мелких отношений. При этом возникают следующие три вопроса:

1. распознать отношения, подлежащие разбиению?

2. Как осуществлять разбиение?

3. Когда окончить процесс разбиения?

Анализ аномалий в обработке данных показывает, что решение двух первых вопросов тесно связано с определением первичного ключа, распознавания явлений дублирования и избыточности, дублирования и неизбыточности данных. В основе всех этих явлений лежит концепция ФЗ. С практической точки зрения смысл ФЗ заключается в следующем: если имеет место, то каждый из кортежей, имеющих одно и то же значение А , должен иметь одно и то же значение В. Изменение значений А и В во времени не должно нарушать ФЗ.

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

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

Декомпозиция схем отношений, свойства соединения без потерь и сохранения ФЗ

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

Введем определение декомпозиции схемы отношения .

Определение 1. Декомпозицией схемы отношений называется замена ее совокупностью подмножества R .

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

Рассмотрим алгоритм проверки свойства соединения без потерь.

Алгоритм. Проверка декомпозиции на свойство соединения без потерь

input: схема отношения R(A 1 , A 2 , ..., A k), множество ФЗ F,

декомпозиция d={R 1 , R 2 , ..., R k }.

output: Булева переменная истина или ложь.

Алгоритм

1. Построим таблицу с n столбцами и k строками, где столбец j соответствует атрибуту А j , а строка i - схеме отношения R i . На пересечении строки i и столбца j поместим символ aj , если атрибут A j принадлежит R i . В противном случае поместим символ b ij .

2. Многократно просматриваем каждую ФЗ из F , до тех пор, пока внесение изменений в таблицу станет невозможным. Просматривая зависимость, ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам из Х . При обнаружении таких строк отождествляем их символы в столбцах, соответствующих атрибутам из Y , по правилу a j в a j , b ij в b ij .

3. Если после модификации строк таблицы оказывается, что некоторая строка равна a 1 , a 2 , ..., a k , то декомпозиция d обладает свойством соединения без потерь. В противном случае декомпозиция d таким свойством не обладает.

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

Рассмотрим пример применения алгоритма, используя отношение ПОСТАВКИ (Поставщик, Адрес, Товар, Стоимость). Обозначим его атрибуты как: А - поставщик, В - адрес, C - товар, D - стоимость, при этом имеют место ФЗ.

При декомпозиции одной схемы отношения на две другие схемы отношений используется более простая проверка: декомпозиция обладает свойством соединения без потерь, если только. Такая ФЗ должна принадлежать F + .

Свойство соединения без потерь гарантирует, что любое отношение может быть восстановлено из его проекций. Понятно, что при декомпозиции ФЗ исходной схемы отношения распределяются по новым отношениям. Поэтому важно, чтобы при декомпозиции множество ФЗ F для схемы отношения r было выводимым из проекций на схемы R i .

Введем следующее определение.

Определение 2. Проекцией множества ФЗ F на множество атрибутов Х , обозначаемой, называется множество ФЗ в F+ , таких, что.

Говорят, что декомпозиция обладает свойством сохранения ФЗ, если из объединения всех ФЗ, принадлежащих, логически следуют все зависимости из F .

Рассмотрим отношение (Город, Адрес, Почтовый_индекс). Обозначим его атрибуты как: А - город, В - адрес, C - почтовый индекс, при этом имеют место ФЗ. Декомпозиция схемы этого отношения ABC на AC и BC обладает свойством соединения без потерь, поскольку верна ФЗ. Однако проекция на BC дает только тривиальные зависимости, проекция на АС дает ФЗ и тривиальные ФЗ. Из ФЗ не следует зависимость. Поэтому данная декомпозиция не сохраняет ФЗ, хотя и обладает свойством соединения без потерь.

Рассмотрим пример нарушения ФЗ при декомпозиции.

Пример. Нарушение ФЗ при декомпозиции

R 1 (B, C) R 2 (A, C)

Лесная, 6 132432 Черноголовка, МО 132432

Лесная, 6 132431 Черноголовка, МО 132431

R(A, B, C)

Черноголовка, МО 132432 Лесная, 6

Черноголовка, МО 132431 Лесная, 6

R = R 1 >< R 2 , для R 2 справедлива С \to А, для R не справедлива АВ \ to С.

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

· исключать избыточное дублирование;

· исключать потенциальную противоречивость данных;

· обладать свойством соединения без потерь;

· обладать свойством сохранения ФЗ.

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

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

Понятие о методах декомпозиции отношений

Предположим, что схема базы данных содержит F-зависимости. Из положений теории о F-зависимостях следует, что если отношения базы данных находятся в нормальной форме Бойса-Кодда (НФБК), то проектирование логической модели базы данных можно считать завершенным в этом классе зависимостей. Как видно, теория дает полезный (!) критерий останова проектирования.

Сформулируем наглядный критерий, позволяющий определить, находится ли отношение в НФБК. Для этого введем следующее вспомогательное понятие.

Определение 3. Пусть дана ФЗ: , и В функционально не зависит от любого подмножества А, тогда А называется детерминантом В.

Детерминантами в отношениях являются атрибуты левых частей ФЗ. Возможные ключи (см. учебный элемент "Реляционная модель данных") идентифицируются путем нахождения минимального множества значений атрибутов, которые определяют значения всех остальных атрибутов в отношении. Напомним понятие возможного ключа отношения как атрибута или атрибутов данного отношения, который (-ые) могут быть в данном отношении выбраны в качестве первичного.

Тогда критерий Кодда, позволяющий определить, находится ли отношение в НФБК, может быть сформулирован следующим образом:

Отношение находится в НФБК тогда и только тогда, когда каждый детерминант отношения является возможным ключом.

Таким образом, при декомпозиции отношений необходимо строить списки возможных ключей и детерминантов и сравнивать их на совпадение. Устранив таким образом большинство потенциальных аномалий, проектирование можно завершить.

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

Алгоритм метода декомпозиции отношений

Алгоритм

1. Разработка универсального отношения для базы данных.

2. Определение всех ФЗ между атрибутами отношения.

3. Определение, находится ли отношение в НФБК. Если да, то завершить проектирование; в противном случае отношение должно быть разбито на два других отношения.

4. Повторение пунктов 2 и 3 для каждого нового отношения, полученного в результате декомпозиции.

Уточним некоторые аспекты метода декомпозиции.

Во-первых, как выполнить декомпозицию отношения на два отношения. Пусть отношение R(A, B, C, D, ...) содержит ФЗ и, следовательно, не находится в НФБК. Атрибут С является детерминантом , но не возможным ключом. Для выполнения декомпозиции отношения R создаются два отношения R 1 (A, B, C, ...) и R 2 (C, D) , в одно из которых выделяется ФЗ. Такая декомпозиция является декомпозицией без потерь при естественном соединении . Далее с тех же позиций рассматриваются отношения R 1 и R 2 .

Во-вторых, каков критерий выбора ФЗ для выполнения проекции (далее мы увидим, насколько это может быть существенно). Понятно, что в качестве кандидатов для осуществления проекции следует отбирать ФЗ с детерминантами в левой части. Однако зависимости с детерминантами могут носить транзитивный характер, и здесь полезно применить первое эмпирическое правило выбора ФЗ для выполнения проекции - "правило цепочки". Правило цепочки состоит в следующем:

Если, то в качестве ФЗ для осуществления проекции используется крайняя правая зависимость или "конец цепочки" .

Методы проектирования на основе синтеза отношений

Некоторые проблемы метода декомпозиции

Алгоритм метода декомпозиции отношений не является совершенным. Мир ФЗ очень разнообразен. Он представляет собой хороший рабочий инструмент и, учитывая типы ФЗ, может совершенствоваться. Обратим внимание на две проблемные ситуации, связанные с применением метода декомпозиции. Пусть имеется отношение R(A, B, C, D, ...) из примера выше.

Первая ситуация: в процессе декомпозиции потеряна ФЗ, и если отношения R 1 и R 2 будут использованы для создания базы данных, то нельзя гарантировать, что связи между этими атрибутами будут внесены в БД корректно. Отсюда вытекает второе эмпирическое правило выбора ФЗ для выполнения проекции: не следует использовать ФЗ в качестве ФЗ для осуществления проекции, если ее левая часть является детерминантом другой ФЗ. Эта проблема разрешается путем применения правила цепочки.

Вторая ситуация: один атрибут зависит от двух детерминантов - один возможный ключ {A, C} и два детерминанта А и С . Эта ситуация является более критичной. Отношение не находится в НФБК; в отношении отсутствуют цепочки ФЗ, и правило цепочек к нему неприменимо. Эта проблема не разрешается с помощью стандартного метода декомпозиции. Решением является разложение исходного отношения на два отношения, в основе которого лежит утверждение о том, что все ФЗ с одинаковыми детерминантами необходимо выделять в отдельные группы и каждой такой группе отводить свое собственное отношение. Полученные отношения следует проверять на соответствие НФБК. Такой подход к проектированию логической модели реляционной базы данных получил название метода синтеза. Метод синтеза может использоваться как самостоятельно, так и в сочетании с методом декомпозиции по проекции. Приведенные примеры позволяют понять ряд потенциальных недостатков декомпозиции как метода проектирования лог ических моделей реляционных баз данных.

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

Понятие о методах синтеза отношений

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

Неединственность минимальных покрытий указывает на то, что порядок исключения избыточных ФЗ может оказать влияние на полученные результаты. Отсюда следует эмпирическое правило:

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

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

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

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

Кроме того, задача приведения исходных отношений к НФБК может оказаться невыполнимой. Такой факт имел место в практике проектирования. Поскольку НФБК может не существовать на заданном наборе ФЗ, то логичным было бы отказаться от требования приведения отношений базы данных к этой форме. Эта ситуация подкрепляется и теоретически: при любом заданном множестве F-зависимостей над схемой r БД можно построить схему БД в 3НФ.

Таким образом, ограничимся поиском 3НФ в ходе применения метода синтеза, при этом остаются проблемы, связанные с выполнением операций над данными.

Алгоритм метода синтеза отношений

В данном разделе приводится лишь некоторый обзор алгоритма синтеза отношений .

Мы уже рассматривали примеры декомпозиции с потерей ФЗ. Причиной потери ФЗ является некоторая ФЗ, которая не может быть исключена из множества F-зависимостей, связанных с получаемыми отношениями R 1 или R 2 . Таким образом, суть проблемы сводится к нарушению замкнутости реляционных операций над ФЗ на полученной схеме базы данных. Для того чтобы ее решить, необходимо пополнить минимальное покрытие ФЗ, или, как говорят, усилить минимальное покрытие.

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

Введем определение.

Определение 4. Реляционная база данных называется полной, если:

· все ФЗ усилены ключами;

· все отношения находятся в 3НФ;

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

Почти всегда в предметной области базы данных можно выделить набор отношений, обладающих свойством полноты. Доказана теорема [Мейер], что существует алгоритм, который выводит полную базу данных из множества заданных ФЗ.

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

Пример. Универсальный ключ и ложные соединения

Пусть отношение R имеет кортежи:

1 1 1 1

4 1 2 2

Случай 1. Отсутствие ложных соединений

Разбиение на отношения

R 1 =ABC и R 2 =BCD

1 1 1	1 1 1
4 1 2	1 2 2

не дает ложных соединений.

Случай 2. Наличие ложных соединений

Разбиение на отношения

R 1 = AB и R 2 = BCD

1 1	1 1 1
4 1	1 2 2

дает ложные соединения

ABCD

1 1 1 1	1 1 2 2
4 1 1 1	4 1 2 2

Поскольку, то решить проблему можно, введя универсальный ключ {A,C} . Тогда можно добавить в исходную схему отношение

AC

1 1

1 2

и выполнить соединение отношений AB, BCD и AC , которое восстановит исходное отношение ABCD .

Заметим, что атрибут А выступает в качестве ключа практически во всех ФЗ. Выделенный или добавленный атрибут, обладающий подобным свойством, называется универсальным ключом. Таким образом, решение проблемы ложных соединений заключается в добавлении подсхемы, которая содержит универсальный ключ, и выполнении соединения с ее использованием.

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

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

Введем некоторые обозначения. Составной ФЗ называется ФЗ: , где Y может быть пусто. С каждой составной ФЗ можно связать набор ФЗ: . Пусть С - множество составных ФЗ, fd(C) - множество всех ФЗ, связанных с ФЗ из С.

В принятых обозначениях основные этапы алгоритма синтеза отношений приведены ниже.

Алгоритм поэтапного синтеза отношений

Вход: F - множество ФЗ предметной области базы данных

Выход: схема полной базы данных

Этап 1. Нахождение неизбыточного покрытия F 1 для F

Для каждой ФЗ из F проверяется, может ли данная ФЗ быть выведена из оставшихся ФЗ. Если да, то ФЗ удаляется. Этап завершается после перебора всех ФЗ из F . В результате выполнения этапа получается множество ФЗ F 1 .

Этап 2. Сокращение слева элементов F 1

Удаляются последовательно один за другим атрибуты из левых частей ФЗ F 1 ; проверяется, может ли полученная ФЗ быть выведена из исходных ФЗ F 1 F 1 F 2 .

Этап 3. Сокращение справа элементов F 2

Удаляются последовательно один за другим атрибуты ФЗ из правых частей ФЗ F 2 ; проверяется, может ли исходная ФЗ быть выведена из полученной ФЗ и имеющихся ФЗ F 2 . Если да, то исходная ФЗ заменяется на новую ФЗ. Этап завершается после перебора всех ФЗ F 2 . В результате получается множество ФЗ F 3 .

На этом сокращение ФЗ закончено. Избыточность отсутствует. Необходимо приступать к построению минимального покрытия.

Этап 4. Разделение F 3 на классы эквивалентности по правым частям

Строится разбиение F 3 на группы: две ФЗ принадлежат одной и той же группе тогда и только тогда, когда их правые части эквивалентны. В результате получается множество классов эквивалентности ФЗ.

Этап 5. Удаление в классах эквивалентности избыточных ФЗ

Для всех пар ФЗ fd i и fd j из одной и той же группы проверяется, может ли ФЗ левой стороны fdj от правой стороны fd j быть выведена из этой группы ФЗ. Если да, то из fd j ФЗ удаляется и добавляется в правую часть этой ФЗ к правой fd i . Новая ФЗ будет находиться в той же группе, что и исходная ФЗ. В результате получается минимальное число ФЗ F 5 , покрывающих F 3 .

Этап 6. Получение классов эквивалентности по левым частям F 5 и составных ФЗ C 1

Для каждого множества ФЗ с эквивалентными левыми частями из F 5 создается составная ФЗ. Если какой-либо атрибут из Y есть в X i , то этот атрибут удаляется. В результате получается множество составных ФЗ С 1 .

Этап 7. Удаление избыточных зависимостей из С 1

Для каждой составной ФЗ из С 1 и для каждого атрибута X i из левой части С сдвигаются атрибуты в правую часть. В результате получается множество составных ФЗ С" . Если fd(C") эквивалентно fd(C 1) , то С 1 заменяется на С" . В результате получается множество ФЗ С 2 .

Этап 8. Формирование кольцевого минимального покрытия

Для каждой составной ФЗ c из С 2 и каждого атрибута A из правой части c удаляется атрибут А . В результате получается С" , состоящее из с" . Если fd(C") эквивалентно fd(C 2) , то С 2 заменяется на С" . В результате получается множество ФЗ С 3 .

Этап 9. Формирования схемы полной базы данных

Для каждой составной ФЗ с из С 3 формируется таблица атрибутов, которые появляются в с . Ключами для этой таблицы являются Х i из левой части с . Таблица послужит для усиления ФЗ в F .

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

Создание логической модели реляционной базы данных методом декомпозиции: преобразование ER -диаграмм в отношения базы данных

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

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

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

1. каждый преподаватель читает только один курс, и каждый курс читается только одним преподавателем, т.е. классы принадлежности обеих сущностей являются обязательными;

2. каждый преподаватель читает только один курс, и каждый курс читается не более чем одним преподавателем, т.е. класс принадлежности первой сущности является обязательным, а второй сущности - необязательным;

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

4. каждый преподаватель читает не более одного курса, а каждый курс читается только одним преподавателем.

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

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

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

Сформулируем первое правило.

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

Исходное отношение является одновременно и конечным отношением.

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

Это правило может быть применено во втором варианте, когда исходное отношение уже требует декомпозиции. Исходное отношение ПРЕПОДАВАТЕЛЬ_1 содержит проблему нуль-значений: данные о предметах, которые не читаются в данный момент, не могут быть внесены в базу данных.

Результирующее отношение ПРЕПОДАВАТЕЛЬ_2 не имеет проблемы нуль-значений. В результирующем отношении ПРЕДМЕТЫ эта проблема исключается: для предмета, который в данный момент не читается, определяется специальное непустое значение по умолчанию. Миграция ключа необходима для восстановления исходного отношения. Таким образом, миграция ключа в методе декомпозиции представляет собой перенос первичного ключа одного отношения в другое отношение для предотвращения потери данных при соединении.

Сформулируем третье правило.

Правило 3. Если степень бинарной связи 1:1 и класс принадлежности обеих сущностей не является обязательным, то требуется построение трех отношений - по одному на каждую объектную сущность и одному для связывающего отношения. При этом ключ каждой сущности является первичным ключом соответствующего отношения и одного отношения для связи, с первичным ключом, составленным из ключей объектных сущностей. Это правило можно применить в третьем варианте поведения предметной области, когда исходное отношение необходимо разбить на три отношения. Разбиение на два отношения не позволит исключить проблему нуль-значений. В случае трех отношений такая проблема исключается: в отношение ПРЕДМЕТЫ для предмета, который в данный момент не читается, определяется непустое значение по умолчанию.

Сформулируем четвертое правило.

Правило 4. Если степень бинарной связи 1:N , и класс принадлежности n-связной сущности является обязательным, то достаточно построить два отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения, а ключ 1-связной сущности добавляется в отношение для n -связной сущности в качестве атрибута.

Сформулируем пятое правило.

Правило 5. Если степень бинарной связи 1:N и класс принадлежности n-связной сущности не является обязательным, то необходимо построить три отношения - по одному на каждую сущность. При этом ключ каждой сущности является первичным ключом соответствующего отношения и одного отношения для связи. Ключи сущностей должны быть атрибутами последнего отношения.

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

Если степень бинарной связи N:M , то во избежание дублирования и нуль-значений необходимо всегда строить три отношения. Сформулируем шестое правило.

Правило 6. Если степень бинарной связи M:N , то необходимо построить три отношения - по одному для каждой сущности и одно отношение для связи. При этом ключ каждой сущности является первичным ключом соответствующего отношения, и входит в составной первичный ключ отношения для связи.

Для отношения с трех- и более сторонней связью во избежание избыточности и нуль-значений требуется построение не менее четырех отношений. Сформулируем седьмое правило.

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

Аналогично для отношения с n-сторонней связью требуется построение n+1 отношений.

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

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

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

Так, например, база данных кафедры института содержит две категории служащих - преподаватели и заведующий кафедрой. Заведующий кафедрой также может читать лекции по предметам, но получает обычно фиксированный оклад; преподаватели имеют почасовую ставку оплаты. Попробуем представить информацию о служащих кафедры более подходящим образом. Выделим для каждой категории служащих кафедры отдельную сущность и рассмотрим ER-диаграмму Зав. кафедрой Руководит Преподавателями.

При этом ключом каждой сущности будет являться табельный номер служащего. Поскольку связь Руководит имеет степень 1:N , и класс принадлежности обеих сущностей является обязательным, то согласно правилу 4 достаточно построить два предварительных отношения. Поскольку неключевые атрибуты Фамилия и Адрес_служащего помещены в оба предварительных отношения, то согласно общему принципу правил преобразования они должны быть переопределены для одного из отношений. Переименование атрибутов в одном из отношений порождает проблему ответа на запрос: для того чтобы найти домашний телефон конкретного служащего, необходимо пересмотреть оба отношения и построить объединение результатов просмотра. Таким образом, переименование атрибутов, к которому иногда поспешно прибегают проектировщики, не является хорошим решением.

Рассмотрим иной вариант представления данных о служащих кафедры. Будем считать заведующего кафедрой и преподавателей служащими, и представим их функции как роли, которые данный служащий может играть. Тогда Отношение СЛУЖАЩИЙ представляет собой родительское отношение - супертип для двух подчиненных отношений - подтипов ЗАВ. КАФЕДРОЙ и ПРЕПОДАВАТЕЛЬ, которые соединяются связью Руководит.

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

Результирующие отношения:

СЛУЖАЩИЙ (#служащий, общие атрибуты для всех служащих)

ЗАВЕДУЮЩИЙ (#заведующий, ....)

ПРЕПОДАВАТЕЛЬ (#преподаватель, ..., #заведующий)

Заметим, что связь, которая соединяет две роли одной исходной сущности, называется рекурсивной (служащие руководят служащими). Связь, которая соединяет роли двух различных сущностей, не является рекурсивной.

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

Сформулируем восьмое правило.

Правило 8. Исходная сущность служит источником генерации одного отношения. Ключ сущности есть ключ отношения. Подчиненные сущности (ролевые элементы) и связи, соединяющие их, порождают такое количество отношений, которое определяется набором правил 1-7, причем каждый ролевой элемент трактуется как обычная сущность.

Пример преобразования ER-диаграмм в отношения базы данных

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

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

1. Каждый клиент имеет свой регистрационный номер (далее - номер). Все номера у клиентов уникальны и различны. Номер однозначно определяет Фамилию, но не наоборот. .

2. Каждый клиент располагается по определенному адресу, по которому могут находиться несколько клиентов. .

3. Предположим, что только один телефон связан с данным адресом. .

4. Каждому клиенту может быть приписан телефон. .

5. Для каждого клиента определяется рейтинг (активность, частота обращений и т.д.) за период по конкретной теме. Рейтинг клиента однозначно определяется по его номеру.

6. Консультации носят тематический характер. Каждая тема имеет свой идентификатор.

7. Период представляет собой отрезок времени, в течение которого проводилась тематическая консультация. Для определенности назовем этот период семестром. Перечислим ФЗ предметной области базы данных:

Рассмотрим детерминанты и возможные ключи отношения КОНСУЛЬТАНТ.

Возможные ключи	Детерминанты
{Номер, Тема, Семестр}	{Номер, Тема, Семестр}
	{Номер}
	{Телефон}
	{Адрес}

Согласно критерию Кодда, поскольку не каждый детерминант в отношении есть возможный ключ, то отношение не находится в НФБК. Выполним декомпозицию отношения КОНСУЛЬТАНТ R0 (Номер, Тема, Семестр, Фамилия, Адрес, Телефон, Рейтинг). Кандидатами на выполнение проекции являются следующие ФЗ:

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

Проверим, находится ли отношение R2 в НФБК.

Отношение R2 находится в НФБК.

Проверим, находится ли отношение R1 в НФБК.

Возможные ключи	Детерминанты
{Номер, Тема, Семестр}	{Номер, Тема, Семестр}
	{Номер}
	{Адрес}

Отношение R1 не находится в НФБД, необходимо продолжить его декомпозицию. Выберем ФЗ и выполним разбиение R1 на R3(Номер, Тема, Семестр, Рейтинг) и R4 (Номер, Фамилия, Адрес).

Проверим, находится ли отношение R3 в НФБК.

Возможные ключи	Детерминанты
{Номер, Тема, Семестр}	{Номер, Тема, Семестр}

Отношение R3 находится в НФБК.

Проверим, находится ли отношение R4 в НФБК.

Возможные ключи	Детерминанты
{Номер}	{Номер}

Отношение R4 находится в НФБК. Декомпозиция закончена.

Заметим, что если бы изначально в нашем примере в качестве ФЗ для выполнения проекции была выбрана ФЗ, то в результате мы имели бы совсем другой (!) набор отношений.