Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

77-30569/294486 Алгоритм синтеза частично оптимальной схемы реляционной базы данных

# 01, январь 2012
Файл статьи: Григ_1_P.pdf (236.04Кб)
автор: Григорьев Ю. А.

УДК 004.654

МГТУ им. Н.Э. Баумана

grigorev@iu5.bmstu.ru

Благодаря своей простоте и ясным концептуальным основам, реляционная модель данных получила широкую поддержку среди поставщиков коммерческих СУБД. Начиная с исторической работы Кодда [1], вокруг этой модели развернулись активные теоретические исследования. В теории проектирования реляционных баз данных одной из центральных является проблема синтеза оптимальной логической схемы базы данных на основе множества функциональных зависимостей (ФЗ) атрибутов универсального отношения [2]. Как показано в [3], задача поиска оптимальной схемы является NP-полной, т.е. относится к классу труднейших по вычислительной сложности. Соответственно, алгоритм ее решения имеет экспоненциальную временную сложность. Поэтому  на практике часто проектируют неоптимальную схему,  имеющую полиномиальный алгоритм синтеза, гарантирующий получение заданных свойств.

В традиционной постановке задача синтеза неоптимальной схемы  сформулирована в следующем виде [2, 4]. Пусть задана схема S = (R; F), где R - множество атрибутов универсального отношения, F - множество ФЗ атрибутов из R. Необходимо получить схему T как множество подсхем (схем отношений) вида Si = (Ri; Ki), где Ri - множество атрибутов подсхемы, Ki = {Xi1,…, Xiq} - множество ключей подсхемы  (Xij  Ri, i = , j = ). При этом схема T должна удовлетворять следующим требованиям.

1. Декомпозиция {R1,…, Rp} обладает свойством естественного соединения результирующих отношений без потерь информации.

2. Обеспечивается сохранение множества всех ФЗ из замыкания F+ (т.е. из объединения всех ФЗ подсхем логически следуют все зависимости, принадлежащие F).

3. Все подсхемы Si находятся в третьей нормальной форме (3НФ).

4. Число подсхем в схеме минимально, т.е. не существует схемы, удовлетворяющей требованиям 1-3 и содержащей менее p подсхем.

Свойства сохранения информации и множества ФЗ, отраженные в пунктах 1 и 2, имеют большое значение, так как позволяют восстановить  исходную схему S по декомпозиции T. Соответствие подсхем Si 3НФ (пункт 3) позволяет избежать значительной части аномалий включения, удаления и модификации кортежей базы данных. Требование, изложенное в пункте 4, позволяет обеспечить минимальный объем хранения базы данных.

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

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

Алгоритм А.

Шаг 1: (устранение лишних атрибутов и поиск неизбыточного покрытия). Для каждого отображения f: X→AF и каждого BX, если  f*: (X - {B}) → A), заменить f на f*. Затем найти неизбыточное покрытие G для F.

Шаг 2: (разбиение). Разделить G на группы так, что все ФЗ в каждой группе имеют одинаковые левые части.

Шаг 3: (объединение эквивалентных ключей). Пусть J = 0. Для каждой пары групп, скажем, G1 и G2 c левыми частями X и Y соответственно, объединить G1 и G2  вместе, если существует X ↔ Y в G+ (т.е. для X → YY→X). Для каждого АY добавить f1: X→A к J и если f1 имеется в G, то удалить ее из G. Аналогично, для каждого BX добавить f2: Y→B к J и если f2 имеется в G, то удалить ее из G.

Шаг 4: Найти G*G такое, что (G* + J)+ = (G + J)+ и никакое собственное подмножество G* не обладает этим свойством. Добавить каждую ФЗ из J в соответствующую группу G*.

Шаг 5: (конструирование отношений). Для каждой группы построить  отношение, состоящее из атрибутов, появляющихся в этой группе. Каждое множество атрибутов, появляющихся в левой части ФЗ в этой группе, являются ключом отношения (каждый ключ, определенный таким образом, называется синтезированным). Множество созданных отношений образует схему T для данного множества ФЗ.

Недостатком этого алгоритма является сложность  машинной реализации шага 4, что затрудняет использование данного алгоритма в системах автоматизированной поддержки проектирования баз данных.  Использование при реализации шага 4 условия (G* + J)+ = (G + J)+ вызывает трудности вычисления, так как получение покрытия любого множества ФЗ F+ может экспоненциально зависеть от размера F.

В настоящей работе предлагается алгоритм решения задачи синтеза частично оптимальной схемы базы данных, обеспечивающий выполнение требований 1-3 для Т и относительно простую возможность машинной реализации [8].

Алгоритм Б.

Шаг 1: Пусть Т = Ø.

Шаг 2: Построить G - минимальное покрытие для F.

Шаг 3: Каждую зависимость X→A из G заменить на XA  (запись вида XA означает объединение множества атрибутов X и атрибута A). Получившееся таким образом множество подсхем обозначить через Q.

Шаг 4: Если A1A2…Am Q, то добавить в Т подсхему A1A2…Am  и выйти из алгоритма.

Щаг 5: Добавить в Т  в качестве подсхем те атрибуты, которые не входят ни в какие подсхемы из Q.

Шаг 6: Добавить в Т все подсхемы из Q.

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

Покрытие G будем называть минимальным, если оно содержит минимальное число ФЗ и минимальное число атрибутов в левой и правой частях каждой ФЗ. Развернутое определение минимального покрытия и алгоритм его построения представлен в [6].

Замечание. Предложенный алгоритм Б не гарантирует выполнения пункта 4 требований к множеству Т, так как не предполагает объединения ФЗ с эквивалентными левыми частями. Однако пункт 4 не является определяющим при проектировании "хорошей" схемы базы данных. Более того, соблюдение требований данного пункта в случае распределенного хранения таблиц базы данных приводит к значительным издержкам выполнения операций соединения. Этот и ряд других факторов [5] приводят к отказу от повсеместного и всеобязательного принципа исключения избыточности.

В [6] приведены теоремы 5.7  и  5.8, подтверждающие, что алгоритм Б обеспечивает выполнение требований 1-3 для Т.

Пример. Рассмотрим  гипотетическую базу данных учебного отдела ВУЗа, имеющую следующее универсальное отношение:

R = (A - дисциплина, В - преподаватель, С - час начала занятия, D - номер аудитории, Е - студент, K - оценка)

Пусть среди атрибутов данного отношения существуют следующие ФЗ:

 F = {

A→B -      каждую дисциплину ведет только один преподаватель,

СD→A -   в аудитории одновременно может читаться только одна дисциплина,

СB→D -    преподаватель может одновременно находится только в одной  аудитории,

AE→K -    по  каждой дисциплине каждый студент имеет только одну оценку,

AC→D -   каждая дисциплина может одновременно читаться только в одной аудитории,

СЕ→D -    студент может одновременно находится только в одной аудитории

}

Необходимо построить схему базы данных, отвечающую условиям 1-3.

Шаг 1: Т =  Ø

Шаг 2: G = { A→B, СD→A, СB→D, AE→K, AC→D, СЕ→D}

 

a1) ABG - {AB} = {СDA, СBD, AEK, ACD, СЕ→D}

A+ = ABA+  AB(G - {AB})+

б1) CDA, G - {CDA}= { AB, СBD, AEK, ACD, СЕ→D }

(CD)+ = CDA(CD)+CD→A(G - {CD→A})+

в1) CB→D, G - {CB→D} = { A→B, СD→A, AE→K, AC→D, СЕ→D}

(CB)+ = CBD(CB)+CB→D(G - {CB→D})+

г1) AE→K, G - {AE→K} = { A→B, СD→A, СB→D, AC→D, СЕ→D}

(AE)+ = AEBK(AE)+AE→K(G - {AE→K})+

д1) AC→D, G - {AC→D} = { A→B, СD→A, СB→D, AE→K, СЕ→D}

(AC)+ = ACBDD(AC)+ACD(G - {ACD})+ФЗ ACD может быть исключена из множества G, т.е. теперь

G = { A®B, СDA, СBD, AEK, СЕ→D}

е1) CED, G - {CED} = { AB, СDA, СBD, AEK}

(CE)+ = CED(CE)+CE→D(G - {CE→D})+

Далее рассматриваются ФЗ из G, имеющие 2 и более атрибутов в левой части, и анализируются собственные подмножества левых частей:

a2) СDA

CA, ниже замыкания множества атрибутов берутся  для G,

C+ = CCAG+

DA,

D+ = DDAG+

Аналогично можно показать, что

б2) для СBD ФЗ С→D и B→DG+

в2) для AEK  ФЗ A→K и E→KG+

г2) для СЕ→D  ФЗ С→D и E→DG+

Таким образом G = { AB, СDA, СBD, AEK, СЕ→D} – это минимальное покрытие для множества исходных функциональных зависимостей F.

Шаг 3: Q = {AB, CDA, CBD, AEK, CED}

Шаг 4: ABCDEKQ

Шаг 5: Все атрибуты принадлежат хотя бы одной подсхеме из Q

Шаг 6: T = {AB, CDA, CBD, AEK, CED}

Шаг 7:

X0 = ABCDEK

(BCDEK)+ = BCDEKA = SX1 = BCDEK

(CDEK)+ = CDEKAB = SX2 = CDEK

(DEK)+ = DEK ¹ S

(CEK)+ = CEKDAB = SX3 = CEK

(EK)+ = EK ¹ S

(CK)+ = CK ¹ S  

(CE)+ = CEDABК = SX4 = CE

C+ = C ¹ S

E+ = E ¹ S

Следовательно, X = CE – ключ универсального отношения. Так как CECED, то схема базы данных Т = {AB, CDA, CBD, AEK, CED} обладает

1) свойством соединения без потерь,

2) свойством сохранения зависимостей,

3) каждая подсхема находится в 3НФ. 

 

Литература

 

1.     Codd E.F. A relational model of data for large shared data banks. Comm. ACM. 1970. V. 13. № 6.

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

3.     Lucchesi C., Osborn S. Candidate keys for relations// J. Computer and System Sciences. 1978. V. 17. № 2. 

4.     Bernstein P. Synthesizing third normal form relations from functional dependencies// ACM Trans. on Database Systems. 1976. V. 1. № 4.

5.     Зиндер E. Проектирование баз данных: новые требования, новые подходы// СУБД. - 1996. - № 3.

6.     Ульман Дж. Основы систем баз данных. - М.: Финансы и статистика, 1983. – 334 с.

7.       Преснякова Г.В. Проектирование интегрированных реляционных баз данных. – М.: КДУ: СПб.: Петроглиф, 2007. – 224 с.

8.      Григорьев Ю.А., Плутенко А.Д. Теория и практика проектирования систем на основе баз данных: Учебное пособие. – Благовещенск: Амурский гос. ун-т, 2007. – 396 с.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)