Основные положения теории реляционных баз данных, страница 5

Определение 33. Схема   реляционной БД называется эффективной относительно  F, если она находится в НФБК, обладает свойством соединения без потерь и  сохраняет  F . 

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

Теорема 5. Для любого множества ФЗ ,  

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

Определение 34. Схему БД, удовлетворяющую условиям тео­ремы 5, принято называть  

В-схемой. 

Поскольку проверка выполнимости свойства НФБК для заданной схемы БД является NP – полной задачей, то все практически значимые методы синтеза схемы БД гарантируют получение лишь B- схемы. Суть всех этих методов сводится к следующим основным 
действиям. Вначале выполняют эквивалентные преобразования заданного множества F (удаление избыточных ФЗ, редуцирование и т.п.). Затем осуществляют синтаксическое разложение R согласно структуре множества F, то есть каждой схеме из  ставится в соответствие одна или несколько ФЗ из F. Большинство методов синтеза имеют полиномиальную вычислительную сложность. Один из методов приведен в прил.6.

1.2 Методы проверки существования зависимостей соединения

Рассмотрим теоремы, указывающие пути проверки для заданной декомпозиции  свойства F .

Теорема 6. Для  свойство  имеет место тогда и только тогда, когда выполнено хотя бы одно из следующих условий: , .

Теорема 7. Если декомпозиция  сохраняет F, то F  тогда и только тогда, когда существует хотя бы одна подсхема  такая, что , где K -  ключ схемы R относительно F.

Область применения теорем 6, 7 весьма ограничена, поскольку теорема 6 применима лишь для случая, когда , а теорема 7, когда  сохраняет F.

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