Выдержка из книги
Майер Д.N.
Теория реляционных баз данных
Вторая и третья нормальные формы введены Коддом ( Codd [ 1971b, 1972a ]), который указал способ их получения с помощью нормализации. В работе Kent [1973] излагается введение в нормальные формы. Первые варианты алгоритма синтеза даны в Delobel, Casey [1973], а также Wang, Wedekind [ 1975J, однако они содержат неточности. В работах Osborn [1977], Dayal и Bernstein [ 1978a ], а также Biskup, Dayal и Bernstein [1979] обсуждаются ЗНФ-схемы базы данных, удовлетворяющие условию соединения без потерь. Устранимые атрибуты введены Ling, Tompa и Kameda [1981]; ими же предложен алгоритм для их устранения. Методы декомпозиции и синтеза для получения нормальных форм сравниваются в работе Fagin [1977], а в Beeri, Bernstein и Goodman [1978] обсуждаются цели нормализации. Эти авторы указывают, что для заданного множества F-зависимостей может существовать много нормализованных схем. При этом отсутствуют четкие критерии выбора наилучшей. В работе Bernstein, Goodman [ 1980b ] поднимается вопрос о взаимодействии схем в НФБК с аномалиями обновления. Эти результаты были использованы для того, чтобы показать ( Beeri, Bernstein [1979]), что проверка состояния НФБК для заданной схемы базы данных и проверка существования для множества F-зависимостей полной НФБК-схемы являются NP-полными задачами. В работах Osborn [ 1979a ] и LeDoux, Parker [1980] приводятся алгоритмы, проверяющие, имеет ли множество F-зависимостей полную НФБК-схему. Однако оба алгоритма могут затрачивать в неудачном случае экспоненциальное время. Полиномиальный по времени алгоритм нахождения НФБК-схемы для множества F-зависимостей, обладающий свойством соединения, предложен в работе Tsou и Fischer [1980], но схема может оказаться неполной.
![Вторая и третья нормальные формы введены Коддом ( Codd [ 1971b, 1972a ]), который указал способ их получения с помощью нормализации. В работе Kent [1973] излагается введение в нормальные формы. Первые варианты алгоритма синтеза даны в Delobel, Casey [1973], а также Wang, Wedekind [ 1975J, однако они содержат неточности. В работах Osborn [1977], Dayal и Bernstein [ 1978a ], а также Biskup, Dayal и Bernstein [1979] обсуждаются ЗНФ-схемы базы данных, удовлетворяющие условию соединения без потерь. Устранимые атрибуты введены Ling, Tompa и Kameda [1981]; ими же предложен алгоритм для их устранения. Методы декомпозиции и синтеза для получения нормальных форм сравниваются в работе Fagin [1977], а в Beeri, Bernstein и Goodman [1978] обсуждаются цели нормализации. Эти авторы указывают, что для заданного множества F-зависимостей может существовать много нормализованных схем. При этом отсутствуют четкие критерии выбора наилучшей. В работе Bernstein, Goodman [ 1980b ] поднимается вопрос о взаимодействии схем в НФБК с аномалиями обновления. Эти результаты были использованы для того, чтобы показать ( Beeri, Bernstein [1979]), что проверка состояния НФБК для заданной схемы базы данных и проверка существования для множества F-зависимостей полной НФБК-схемы являются NP-полными задачами. В работах Osborn [ 1979a ] и LeDoux, Parker [1980] приводятся алгоритмы, проверяющие, имеет ли множество F-зависимостей полную НФБК-схему. Однако оба алгоритма могут затрачивать в неудачном случае экспоненциальное время. Полиномиальный по времени алгоритм нахождения НФБК-схемы для множества F-зависимостей, обладающий свойством соединения, предложен в работе Tsou и Fischer [1980], но схема может оказаться неполной.](/pic/4344173B3DjUHn0049326253.png)