lecture BD (Лекции по теории проектирования баз данных (БД))
Описание файла
Документ из архива "Лекции по теории проектирования баз данных (БД)", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "lecture BD"
Текст из документа "lecture BD"
14
Лекция 1
Технология проектирования баз данных
Вопросы:
-
Проектирование базы данных как элемент информационной технологии;
Теоретические основы проектирования БД;
-
Синтез БД.
Проектирование базы данных как элемент информационной технологии
Как видно из материалов предыдущих лекций основу большинства информационных технологий составляют большие массивы накопленной информации. Основной формой организации хранения данных в информационных системах являются базы данных. В курсе “Автоматизированные системы обработки учетной информации” мы рассмотрели основные понятия, связанные с моделями данных, теоретические основы разработки простейших баз данных и жизненный цикл баз данных. Теперь, рассматривая БД как часть информационной технологии, необходимо по новому взглянуть на проблему проектирования базы.
Проблемы проектирования связаны с функциями БД в программно - технологической среде, поддерживающей информационные технологии. В общем случае место БД можно отразить следующей схемой:
П риложения поддержки
информационных
технологий
Прочие
приложения
Поскольку база данных является связующим звеном между пользовательскими приложениями и аппаратными средствами, ее проектирование можно разделить на два направления: проектирование структуры и пользовательских приложений и распределение данных по аппаратным средствам (в случае баз данных на сетях). В данном разделе мы рассмотрим вопросы проектирования структуры базы данных. В дисциплине АСОЭИ, рассматривая основы реляционной алгебры и разработки реляционных моделей, мы коснулись вопросов проектирования реляционных баз данных. Одной из распространенных технологий разработки БД является следующая:
-
сбор данных о предметной области;
-
анализ представлений пользователей;
-
интеграция представлений пользователей;
-
разработка сетевой модели;
-
преобразование сетевой модели в первую нормальную форму реляционной модели;
-
нормализация отношений путем преобразования их к третьей нормальной форме.
В результате получается модель реляционной базы данных, которая представляет собой совокупность взаимосвязанных отношений.
Построение сетевой модели связано скорее с потребностью разработчика графически представить взаимосвязь данных, полученных в результате интеграции представлений пользователей. Преобразование сетевой модели в реляционную дает первую нормальную форму последней. Напомним, что отношение R находится в первой нормальной форме, если значения в dom(A) являются атомарными для каждого атрибута А в R . Вторая и третья нормальные формы позволяют избежать аномалий при обновлении данных и избавится от информационной избыточности в отношениях. Напомним, что отношение R нормальной форме, если оно находится в первой нормальной форме и каждый атрибут не являющийся ключом полностью зависит от любого ключа в R. И отношение R находится в третьей нормальной форме, если оно находится во 2НФ и каждый атрибут, не являющийся первичным ключом не транзитивно зависит от любого возможного ключа.
Недостатком такого подхода является то, что в моделях, имеющих десятки и сотни атрибутов очень трудно имперически построить модель, все отношения которой заданы в третьей нормальной форме и связаны между собой таким образом, что составляют единое целое.
Пример.
А В С
D F G H
G V M N
B M T X
Другим подходом является возможность формального синтеза модели на основании априорно установленных зависимостей между атрибутами. Зависимости между атрибутами устанавливаются на основании смысловой связи.
Пример.
НОМЕР_ЗАЧЕТКИ - ИМЯ_СТУДЕНТА
НОМЕР_РЕЙСА - ДАТА_ВЫЛЕТА
Безусловно такой подход к разработке модели базы данных предпочтительнее, так как позволяет автоматизировать процесс моделирования. Для реализации этого подхода необходимо расширение теоретической базы, полученной в курсе АСОЭИ.
Теоретические основы проектирования БД.
Основные понятия.
Поскольку рассматриваемый подход к разработке реляционной модели базируется на формальной логике, то в его основе должны лежать некоторые фундаментальные формализации. В теории реляционных баз данных к ним относятся понятия атрибута, отношения, ключа и функциональной зависимости.
Атрибутом будем называть поименованное свойство объекта и обозначать Аi , где . Домен атрибута Аi обозначим dom(Аi). Тогда отношением R называется конечное множество атрибутов . Ключ отношения R является подмножеством К = со следующим свойством. Для любых двух различных кортежей t1 и t2 в R существует такое , что t1(B) t2(B). Другими словами , не существует двух кортежей, имеющих одно и то же значение на всех атрибутах из К . Таким образом, достаточно знать К - значение кортежа, чтобы идентифицировать кортеж однозначно.
Пример.
СТУДЕНТ[НОМЕР_ЗАЧЕТКИ,ИМЯ,КУРС,ГРУППА]
Ключи, явно указанные в модели называются выделенными. Могут быть ключи отличные от выделенных и называемые неявными ключами. Например ИМЯ в предыдущем прмере.
Под функциональной зависимостью атрибутов или F-зависимостью понимают такую связь между атрибутами, когда значения кортежа на одном множестве атрибутов единственным образом определяют эти значения на другом множестве атрибутов. Так в отношении:
ГРАФИК[ПИЛОТ,РЕЙС,ДАТА,ВРЕМЯ]
ПИЛОТ функционально зависит от {РЕЙС,ДАТА}
F-зависимости принято обозначать {РЕЙС,ДАТА}-> ПИЛОТ и говорят, что РЕЙС и ДАТА функционально определяют ПИЛОТ.
В терминах теории множеств и реляционной алгебры F-зависимость определяется так. Пусть R отношение и X, Y подмножества атрибутов в R. Отношение R удовлетворяет функциональной зависимости X -> Y, если Y(X-x®) имеет не более чем один кортеж для каждого Х - значения х. В F-зависимости X->Y подмножество X называется левой частью, а Y - правой частью.
Лекция 2
Такая интерпретация функциональной зависимости является основой алгоритма SATISFIES, приводимого ниже.
SATISFIES
Вход: Отншение R и F-зависимость X->Y.
Выход: истина, если R удовлетворяет X->Y, ложь - в противном случае.
SATISFIES(R,X->Y)
-
Отсортировать отношение R по Х-столбцам так, чтобы собрать кортежи с равными Х-значениями вмести.
-
Если каждая совокупность кортежей с равными Х-значениями имеет также равные Y-значения, то на выходе получаем истину, а в противном случае - ложь.
Этот алгоритм проверяет, удовлетворяет ли отношение R F-зависимости X -> Y.
Пример.
В результате выполнения алгоритма SATISFIES выясним удовлетворяет ли F-зависимость РЕЙС -> ВРЕМЯ_ВЫЛЕТА следующему отношению
ГРАФИК
ПИЛОТ | РЕЙС | ДАТА | ВРЕМЯ_ВЫЛЕТА |
А... | 83 | 9 авг | 10:15 |
П... | 83 | 11 авг | 10:15 |
А... | 116 | 10 авг | 13:25 |
Р... | 116 | 12 авг | 13:25 |
П... | 281 | 8 авг | 5:50 |
С... | 281 | 9 авг | 5:50 |
П... | 301 | 12 авг | 18:35 |
С... | 412 | 15 авг | 13:25 |
Однако F-зависимость ВРЕМЯ_ВЫЛЕТА -> РЕЙС согласно этому алгоритму не выполняется для этого отношения
ГРАФИК
ПИЛОТ | РЕЙС | ДАТА | ВРЕМЯ_ВЫЛЕТА |
П... | 281 | 8 авг | 5:50 |
С... | 281 | 9 авг | 5:50 |
А... | 83 | 9 авг | 10:15 |
П... | 83 | 11 авг | 10:15 |
А... | 116 | 10 авг | 13:25 |
Р... | 116 | 12 авг | 13:25 |
С... | 412 | 15 авг | 13:25 |
П... | 301 | 12 авг | 18:35 |
Д ля разработки модели базы данных необходимо знать полное множество F-зависимостей. Чтобы найти их, необходимы семантические знания об исходном отношении R. Поэтому можно считать семейство F-завсимостей заданным. Обозначим его F. Однако при таком подходе нельзя быть уверенным, что найдены все F-зависимости отношения R. Для того, чтобы найти все F-зависимости, если известны некоторые из них, можно воспользоваться аксиомами вывода. Возможность получения новых F-зависимостей с помощью аксиом вывода базируется на следующем правиле. Мнжество F-зависимостей F влечет за собой F-зависимость X -> Y (обозначение: F = X -> Y ), если каждое отношение удовлетворяющее всем зависимостям в F, удовлетворяет также зависимости X -> Y. Аксиома вывода - это правило, устанавливающее, что если отношение удовлетворяет определенным F-зависимостям, то оно должно удовлетворять и некоторым другим F-зависимостям. Существует шесть аксиом вывода:
Рефлексивность: X -> X.
Пополнение: X -> Y влечет за собой XZ -> y.
Аддитивность: X -> Y и X -> Z влечет за собой X -> YZ.