Министерство образования российской федерации московский государственный институт электроники и математики (Технический университет)
 Скачать 1.02 Mb.
|
|
Декомпозицией схемы отношения R называется замена её совокупно- стью схем отношений А i таких, что i i A R , и не требуется, чтобы отношения А i были непересекающимися. Декомпозиция отношения не должна приводить к потере зависимостей между атрибутами сущностей. Для декомпозиции должна существовать операция реляционной ал- гебры, применение которой позволит восстановить исходной отношение. Введём понятие простого и сложного атрибута. Простой атрибут – это атрибут, значения которого атомарны (т.е. неделимы). Сложный атрибут мо- жет иметь значение, представляющее собой конкатенацию нескольких значе- ний одного или разных доменов. Аналогом сложного атрибута может быть аг- регат или повторяющийся агрегат данных. Покажем нормализацию на примере отношения КНИГИ (табл. 3.1): Id – идентификатор (первичный ключ), Code – шифр рубрики, Theme – название рубрики, Title – название книги, Author – автор, Editor – редактор, Type – тип издания (учебник, учебное пособие, сборник и.т.п.), Year – год издания, Pg – количество страниц. Таблица 3.1. Исходное отношение КНИГИ ID Code Theme Author Title Editor Type Year Pg Бочков С. 200 681.3 ПО ВТ С убботин Д. Язык СИ Садчиков П. учебник 1990 384 100 681.3 ПО ВТ Джехани Н. Язык АДА учебник 1960 552 300 621.5 МО Крон Г. Диакоптика Баранов А. учебник 1972 544 Кикоин И. 876 007 ИИ Гик Е.Я. Шахматы и математика Капица С. учебное пособие 1983 176 440 32.97 ВТ ПУ для ПЭВМ Витенберг Э. спра- вочник 1992 208 Фролов Г. Храмов А. 385 001.8 Инфор- матика Кузнецов Э. Элементы информатики Рожков П. учебное пособие 1989 304 Примечание. В таблице 3.1 используются следующие сокращения: ВТ – вычислительная техника; ПО ВТ – программное обеспечение вычислительной техники; МО – математическое обеспечение; ИИ – искусственный интеллект. Первая нормальная форма (1НФ). Отношение приведено к 1НФ, если все его атрибуты простые. Отношение КНИГИ содержит сложные атрибуты Author ("Авторы") и Editor ("Редакторы"). Для приведения к 1НФ требуется сделать ключ отноше- ния составным – атрибуты ID, Author и Editor (табл. 3.2). – 33 – Таблица 3.2. Отношение КНИГИ, приведённое к 1НФ ID Code Theme Author Title Editor Type Year Pg 200 681.3 ПО ВТ Бочков С. Язык СИ Садчиков П. учебник 1990 384 200 681.3 ПО ВТ С убботин Д. Язык СИ Садчиков П. учебник 1990 384 100 681.3 ПО ВТ Джехани Н. Язык АДА учебник 1960 552 300 621.5 МО Крон Г. Диакоптика Баранов А. учебник 1972 544 876 007 ИИ Гик Е.Я. Шахматы и математика Кикоин И. учебное пособие 1983 176 876 007 ИИ Гик Е.Я. Шахматы и математика Капица С. учебное пособие 1983 176 440 32.97 ВТ ПУ для ПЭВМ Витенберг Э. спра- вочник 1992 208 385 001.8 Инфор- матика Фролов Г. Элементы информатики Храмов А. учебное пособие 1989 304 385 001.8 Инфор- матика Кузнецов Э. Элементы информатики Рожков П. учебное пособие 1989 304 Введём понятие функциональной зависимости. Пусть X и Y – атрибуты (группы атрибутов) некоторого отношения. Говорят, что Y функционально за- висит от X, если в любой момент времени каждому значению X=х соответству- ет единственное значение Y=y (XY). (При этом любому значению Y=y может соответствовать несколько значений Х=(х 1 , х 2 ,…)). Атрибут X в функциональ- ной зависимости XY называется детерминантом отношения. В нормализованном отношении все неключевые атрибуты функциональ- но зависят от ключа отношения. Неключевой атрибут функционально полно за- висит от составного ключа, если он функционально зависит от ключа, но не на- ходится в функциональной зависимости ни от какой части составного ключа. Вторая нормальная форма (2НФ). Отношение находится во 2НФ, если оно приведено к 1НФ и каждый неклю- чевой атрибут функционально полно зависит от составного ключа. Для того чтобы привести отношение ко 2НФ, нужно: построить его проекцию, исключив атрибуты, которые не находятся в функ- ционально полной зависимости от составного ключа; построить дополнительные проекции на часть составного ключа и атрибуты, функционально зависящие от этой части ключа. Ключом отношения КНИГИ (табл. 3.2) является комбинация полей (ID, Author, Editor ) . Все поля, не входящие в состав ключа, зависят только от иден- тификатора книги. Поэтому отношение должно быть разбито на два: КНИГИ (табл. 3.3) и КНИГИ–АВТОРЫ–РЕДАКТОРЫ (табл. 3.4). Эти отношения связа- ны по внешнему ключу, которым является поле ID. Таблица 3.3. Отношение КНИГИ, приведённое к 2НФ ID Code Theme Title Type Year Pg 200 681.3 ПО ВТ Язык СИ для ПК учебник 1990 384 100 681.3 ПО ВТ Язык АДА учебник 1960 552 300 621.5 МО Диакоптика учебник 1972 544 876 007 ИИ Шахматы и математика учебное пособие 1983 176 – 34 – 440 32.97 ВТ ПУ для ПЭВМ справочник 1992 208 385 001.8 Информатика Элементы информатики учебное пособие 1989 304 Таблица 3.4. Отношение КНИГИ–АВТОРЫ–РЕДАКТОРЫ (2НФ) ID Author Editor 200 Бочков С. Садчиков П. 200 С убботин Д. Садчиков П. 100 Джехани Н. 300 Крон Г. Баранов А. 876 Гик Е.Я. Кикоин И. 876 Гик Е.Я. Капица С. 440 Витенберг Э. 385 Фролов Г. Храмов А. 385 Кузнецов Э. Рожков П. Рассмотрим понятие транзитивной зависимости. Пусть X, Y, Z – атри- буты некоторого отношения. При этом XY и YZ, но обратное соответствие отсутствует, т.е. Z не зависит от Y или Y не зависит от X. Тогда говорят, что Z транзитивно зависит от X (XZ). Третья нормальная форма (3НФ). Отношение находится в 3НФ, если оно находится во 2НФ и в нем отсут- ствуют транзитивные зависимости. Для отношения КНИГИ (табл. 3.3) атрибут Theme зависит от атрибута Code, а не от ключа (хотя название рубрики, естественно, соответствует её шифру). Поэтому для приведения отношения к 3НФ (табл. 3.5) нужно выделить из него ещё одно отношение РУБРИКАТОР (табл. 3.6). Таблица 3.5. Отношения КНИГИ, приведённые к 3НФ ID Code Title Type Year Pg Табл. 3.6. Отношение РУБРИКАТОР 200 681.3 Язык СИ для ПК учебник 1990 384 Code Theme 100 681.3 Язык АДА учебник 1960 552 681.3 ПО ВТ 300 621.5 Диакоптика учебник 1972 544 621.5 МО 440 32.97 ПУ для ПЭВМ справочник 1992 208 007 ИИ 876 007 Шахматы и ма- тематика учебное пособие 1983 176 32.97 ВТ 385 001.8 Элементы ин- форматики учебное пособие 1989 304 001.8 Информатика Введём понятие многозначной зависимости. Многозначная зависимость существует, если заданным значениям атрибута X соответствует множество, состоящее из нуля (или более) значений атрибута Y (X–»Y). Если в отношении присутствуют многозначные зависимости, то схема отношения должна нахо- диться в 4НФ. Различают тривиальные и нетривиальные многозначные зависимости. Тривиальной называется такая многозначная зависимость X–»Y, для которой Y X или X U Y = R, где R – рассматриваемое отношение. Тривиальная много- значная зависимость не нарушает 4НФ. Если хотя бы одно из двух этих усло- вий не выполняется (т.е. Y не является подмножеством X или X U Y состоит не – 35 – из всех атрибутов R), то такая многозначная зависимость называется нетриви- альной. Четвертая нормальная форма (4НФ). Отношение находится в 4НФ, если оно находится в 3НФ и в нем отсутст- вуют нетривиальные многозначные зависимости. Для отношения КНИГИ–АВТОРЫ–РЕДАКТОРЫ (табл. 3.4) атрибуты Au- thor и Editor зависит образуют две многозначные зависимости от первичного ключа, и при этом значения этих атрибутов не зависят друг от друга. Поэтому для приведения отношения к 4НФ нужно разбить его на два отношения КНИГИ–АВТОРЫ и КНИГИ–РЕДАКТОРЫ (табл. 3.7, 3.8). Таблица 3.7. Отношение КНИГИ–АВТОРЫ (4НФ) Таблица 3.8. Отношение КНИГИ–РЕДАКТОРЫ (4НФ) ID Author ID Editor 200 Бочков С. 200 Садчиков П. 200 С убботин Д. 300 Баранов А. 100 Джехани Н. 876 Кикоин И. 300 Крон Г. 876 Капица С. 876 Гик Е.Я. 440 Витенберг Э. 385 Фролов Г. 385 Храмов А. 385 Кузнецов Э. 385 Рожков П. Нормализация сокращает дублирование данных, но появление новых от- ношений усложняет поддержку логической целостности данных. 4. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ Система управления базами данных (СУБД) – это важнейший компонент АИС, основанной на базе данных. СУБД необходима для создания и поддержки базы данных информационной системы в той же степени, как для разработки программы на алгоритмическом языке – транслятор. Программные составляю- щие СУБД включают в себя ядро и сервисные средства (утилиты). Ядро СУБД – это набор программных модулей, необходимый и доста- точный для создания и поддержания БД, то есть универсальная часть, решаю- щая стандартные задачи по информационному обслуживанию пользователей. Сервисные программы предоставляют пользователям ряд дополнительных возможностей и услуг, зависящих от описываемой предметной области и по- требностей конкретного пользователя. Системой управления базами данных называют программную систему, предназначенную для создания на ЭВМ общей базы данных для множества приложений, поддержания её в актуальном состоянии и обеспечения эф- фективного доступа пользователей к содержащимся в ней данным в рамках предоставленных им полномочий. Принципиально важное свойство СУБД заключается в том, что она по- зволяет различать и поддерживать два независимых взгляда на базу данных: "взгляд" пользователя, воплощаемый в "логическом" представлении данных, и – 36 – "взгляд" системы – "физическое" представление (организация хранимых дан- ных). Для инициализации базы данных разработчик средствами конкретной СУБД описывает логическую структуру БД, её организацию в среде хранения и представления данных пользователями (соответственно концептуальную схему БД, схему хранения и внешние схемы). Обрабатывая эти схемы, СУБД создаёт пустую БД требуемой структуры и предоставляет средства для наполнения её данными о предметной области и дальнейшей эксплуатации. 4.1. Классификация СУБД По степени универсальности СУБД делят на два класса: СУБД общего назначения (СУБД ОН) и специализированные СУБД (СпСУБД). СУБД ОН не ориентированы на какую-либо предметную область или на конкретные информационные потребности пользователей. Каждая система та- кого рода является универсальной и реализует функционально избыточное множество операция над данными. СУБД ОН имеют в своем составе средства настройки на конкретную предметную область, условия эксплуатации и требо- вания пользователей. Производство этих систем поставлено на широкую ком- мерческую основу. Специализированные СУБД создаются в тех случаях, когда ни одна из существующих СУБД общего назначения не может удовлетворительно решить задачи, стоящие перед разработчиками, например, не достигается требуемое быстродействие обработки или не обеспечивается поддержка необходимого объёма данных. СпСУБД предназначены для решения конкретной задачи, а приемлемые параметры этого решения достигаются следующим образом: 1) за счёт знания особенностей конкретной предметной области, 2) путём сокращения функциональной полноты системы. Создание СпСУБД – дело весьма трудоемкое, поэтому для того, чтобы выбрать этот путь, надо иметь действительно веские основания. В дальнейшем будут рассматриваться только СУБД общего назначения. По модели данных различают иерархические, сетевые, реляционные и объектно-ориентированные СУБД. По методам организации хранения и обработки данных СУБД делят на централизованные и распределённые. Первые работают с БД, которая физи- чески хранится в одном месте (на одном компьютере). Это не означает, что пользователь может работать с БД только за этим же компьютером: доступ мо- жет быть удалённым (в режиме клиент–сервер). Большинство централизован- ных СУБД перекладывает задачу организации удалённого доступа к данным на сетевое обеспечение, выполняя только свои стандартные функции, которые, ес- тественно, усложняются за счёт одновременности доступа многих пользовате- лей к данным. 4.2. Основные функции СУБД В качестве основных функций СУБД можно выделить следующие: 1. Хранение, извлечение и обработка данных. – 37 – Это основная функция системы, ради которой она создаётся. 2. Наличие языка обработки данных. Язык обработки данных должен быть полнофункциональным, т.е. включать все необходимые для управления данными операции. 3. Наличие доступного словаря–справочника данных. Словарь–справочник содержит метаданные, т.е. описание данных. Обычно он организован с использованием тех же структур, что и сами данные. Это даёт возможность использовать для доступа к нему тот же язык, который используется для доступа к самим данным. 4. Поддержка многопользовательского режима доступа. База данных создаётся для решения многих задач многими пользователями. Это подразумевает возможность одновременного доступа многих пользова- телей к данным. Данные в БД являются разделяемым ресурсом, и СУБД должна обеспечивать разграничение доступа к ним. 5. Обеспечение логической независимости данных. Это свойство позволяет сконструировать несколько различных логических взглядов (представлений) на одни и те же данные для разных групп пользо- вателей, не изменяя их физического представления. При этом пользователь- ское представление данных может сильно отличаться не только от физиче- ской структуры их хранения, но и от логической схемы данных. Оно может синтезироваться динамически на основе хранимых объектов БД в процессе обработки запросов. 6. Обеспечение физической независимости данных. Под физической независимостью данных подразумевается способность СУБД предоставлять некоторую свободу модификации способов организа- ции базы данных в среде хранения, не вызывая необходимости внесения изменений в логическое представление данных. Это позволяет оптимизиро- вать среду хранения данных с целью повышения эффективности системы, не затрагивая созданных прикладных программ, работающих с БД. Свойства (5–6) обеспечиваются с помощью одних и тех же механизмов СУБД. 7. Обеспечение логической целостности БД. Под логической целостностью понимается непротиворечивость данных, то есть все объекты данных в БД должны соответствовать одному и тому же (во времени) состоянию ПО. Это обеспечивается с помощью механизма транзакций (см. следующий раздел). Значения объектов данных не должны выходить за границы допустимых значений. Ограничения целостности объявляются в схеме БД, и их проверка выполняется всякий раз при модификации данных. 8. Обеспечение физической целостности данных. Проблема обеспечения физической целостности данных обусловлена воз- можностью разрушения данных в результате сбоев и отказов в работе вы- числительной системы или в результате ошибок пользователей. Развитые СУБД позволяют в большинстве случаев восстановить потерянные данные. – 38 – Восстановление данных чаще всего основано на периодическом создании резервных копий БД и ведении журнала регистрации изменений (журнала транзакций). 9. Управление доступом. Для многопользовательских систем актуальна проблема защиты данных от несанкционированного доступа. Каждый пользователь этой системы в соот- ветствии со своим уровнем (приоритетом) имеет доступ либо ко всей сово- купности данных, либо только к её части. Управление доступом также под- разумевает предоставление прав на проведение отдельных операций над отношениями или другими объектами БД. 10. Настройка СУБД. Настройка СУБД обычно выполняется администратором БД, отвечающим за функционирование системы в целом. В частности, она может включать в себя следующие операции: модификация параметров организации среды хранения данных с целью повышения эффективности системы; изменение структуры хранимых данных или их размещения в среде хра- нения (реорганизацию БД) для повышения производительности системы или повторного использования освободившейся памяти; подключение внешних приложений к БД; модификацию концептуальной схемы данных (реструктуризацию БД) при изменении предметной области и/или потребностей пользователей. 4.3. Логическая и физическая целостность БД Поддержка логической целостности БД при модификации данных осуще- ствляется с помощью механизма транзакций. Транзакция – это последовательность операций над БД, рассматривае- мых СУБД как единое целое. Это означает следующее: либо успешно выпол- няются все составляющие транзакцию операции и СУБД фиксирует результат их выполнения (команда COMMIT), либо происходит откат всей транзакции (команда ROLLBACK) и все изменения отменяются. При таком подходе каждая операция модификации данных (или группа взаимосвязанных операций) рас- сматриваются системой как логически неделимая операция. Особенно важен механизм транзакций для многопользовательских сис- тем. То свойство, что каждая транзакция начинается при целостном состоянии БД и оставляет это состояние целостным после своего завершения, делает очень удобным использование понятия транзакции как единицы активности пользователя по отношению к БД. Одно из основных требований к СУБД – надежное хранение данных во внешней памяти. Под надежностью хранения понимается то, что СУБД должна быть в состоянии автоматически восстановить последнее согласованное со- стояние БД после аппаратного или программного сбоя, в результате которых может быть нарушена логическая и/или физическая целостность данных. Для восстановления БД необходимо располагать некоторой дополнительной ин- |