ответы к зачёту по Базам Данных (2009), страница 5
Описание файла
Документ из архива "ответы к зачёту по Базам Данных (2009)", который расположен в категории "". Всё это находится в предмете "базы данных" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "ответы к зачёту по Базам Данных (2009)"
Текст 5 страницы из документа "ответы к зачёту по Базам Данных (2009)"
Целевые списки
Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена атрибутов результирующего отношения. Этот компонент называется целевым списком (target list).
Целевой список строится из целевых элементов, каждый из которых может иметь следующий вид:
-
var.attr, где var – имя свободной переменной соответствующей WFF, а attr – имя атрибута отношения, на котором определена переменная var;
-
var, что эквивалентно наличию подсписка var.attr1, var.attr2, ..., var.attrn, где {attr1, attr2, ..., attrn} включает имена всех атрибутов определяющего отношения;
-
new_name = var.attr; new_name – новое имя соответствующего атрибута результирующего отношения.
Последний вариант требуется в тех случаях, когда в WFF используется несколько свободных переменных с одинаковой областью определения.
Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE wff. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена - целевым списком.
-
Исчисление доменов. Основные отличия от исчисления кортежей.
В исчислении доменов областью определения переменных являются не отношения, а домены.
Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного множества предикатов, позволяющих выражать так называемые условия членства. Если R – это n-арное отношение с атрибутами a1, a2, ..., an, то условие членства имеет вид R (ai1 : vi1, ai2 : vi2, ..., aim : vim) (m <= n), где vij – это либо литерально задаваемая константа, либо имя доменной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения (v_ij) указанных атрибутов (a_ij). Если vij – константа, то на атрибут aij накладывается жесткое условие, не зависящее от текущих значений доменных переменных; если же vij – имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.
Примеры. WFF исчисления доменов
СЛУЖАЩИЕ (СЛУ_НОМ:2934, СЛУ_ИМЯ:'Иванов',
СЛУ_ЗАРП:22400.00, ПРО_НОМ:1)
примет значение true в том и только в том случае, когда в теле отношения СЛУЖАЩИЕ содержится кортеж <2934, 'Иванов', 22400.00, 1>. Соответствующие значения доменных переменных образуют область истинности этой WFF.
WFF
СЛУЖАЩИЕ (СЛУ_НОМ:2934, СЛУ_ИМЯ:'Иванов',
СЛУ_ЗАРП:22400.00, ПРО_НОМ:ПРО_НОМ)
будет принимать значение true для всех комбинаций явно заданных значений и допустимых значений переменной ПРО_НОМ, которые соответствуют кортежам, входящим в тело отношения СЛУЖАЩИЕ
Во всех остальных отношениях формулы и выражения исчисления доменов выглядят похожими на формулы и выражения исчисления кортежей. В частности, формулы могут включать кванторы, и различаются свободные и связанные вхождения доменных переменных.
-
Классический подход к проектированию баз данных на основе нормализации. Нормальная форма. Общие свойства нормальных форм. Полный список нормальных форм. Нормализация в OLAP и OLTP системах.
Подробнее – стр. 124-126, стр.
Будем считать, что проблема проектирования реляционной базы данных состоит в обоснованном принятии решений о том, из каких отношений должна состоять БД и какие атрибуты должны быть у этих отношений. Будем приближать схемы отношений к хорошему состоянию путем нормализации – приведения к виду, обладающему определенными хорошими свойствами, в несколько шагов.
В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм:
-
первая нормальная форма (1NF) — смотри вопрос 6;
-
вторая нормальная форма (2NF);
-
третья нормальная форма (3NF);
-
нормальная форма Бойса-Кодда (BCNF);
-
четвертая нормальная форма (4NF);
-
пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).
Основные свойства нормальных форм состоят в следующем:
-
каждая следующая нормальная форма в некотором смысле лучше предыдущей нормальной формы;
-
при переходе к следующей нормальной форме свойства предыдущих нормальных форм сохраняются.
Слабо нормализованные модели данных – формы 1НФ или 2НФ. Сильно нормализованные – 3НФ и далее.
OLTP и OLAP-системы
Можно выделить некоторые классы систем, для которых больше подходят сильно или слабо нормализованные модели данных.
Сильно нормализованные модели данных хорошо подходят для так называемых OLTP-приложений (On-Line Transaction Processing (OLTP)- оперативная обработка транзакций). Типичными примерами OLTP-приложений являются системы складского учета, системы заказов билетов, банковские системы, выполняющие операции по переводу денег, и т.п. Основная функция подобных систем заключается в выполнении большого количества коротких транзакций. Сами транзакции выглядят относительно просто, например, "снять сумму денег со счета А, добавить эту сумму на счет В". Проблема заключается в том, что, во-первых, транзакций очень много, во-вторых, выполняются они одновременно (к системе может быть подключено несколько тысяч одновременно работающих пользователей), в-третьих, при возникновении ошибки, транзакция должна целиком откатиться и вернуть систему к состоянию, которое было до начала транзакции (не должно быть ситуации, когда деньги сняты со счета А, но не поступили на счет В). Практически все запросы к базе данных в OLTP-приложениях состоят из команд вставки, обновления, удаления. Запросы на выборку в основном предназначены для предоставления пользователям возможности выбора из различных справочников. Большая часть запросов, таким образом, известна заранее еще на этапе проектирования системы. Таким образом, критическим для OLTP-приложений является скорость и надежность выполнения коротких операций обновления данных. Чем выше уровень нормализации данных в OLTP-приложении, тем оно, как правило, быстрее и надежнее.
Другим типом приложений являются так называемые OLAP-приложения (On-Line Analitical Processing (OLAP) - оперативная аналитическая обработка данных). Это обобщенный термин, характеризующий принципы построения систем поддержки принятия решений (Decision Support System - DSS), хранилищ данных (Data Warehouse), систем интеллектуального анализа данных (Data Mining). Такие системы предназначены для нахождения зависимостей между данными (например, можно попытаться определить, как связан объем продаж товаров с характеристиками потенциальных покупателей), для проведения анализа "что если…". OLAP-приложения оперируют с большими массивами данных, уже накопленными в OLTP-приложениях, взятыми их электронных таблиц или из других источников данных. Такие системы характеризуются следующими признаками:
-
Добавление в систему новых данных происходит относительно редко крупными блоками (например, раз в квартал загружаются данные по итогам квартальных продаж из OLTP-приложения).
-
Данные, добавленные в систему, обычно никогда не удаляются.
-
Перед загрузкой данные проходят различные процедуры "очистки", связанные с тем, что в одну систему могут поступать данные из многих источников, имеющих различные форматы представления для одних и тех же понятий, данные могут быть некорректны, ошибочны.
-
Запросы к системе являются нерегламентированными и, как правило, достаточно сложными. Очень часто новый запрос формулируется аналитиком для уточнения результата, полученного в результате предыдущего запроса.
-
Скорость выполнения запросов важна, но не критична.
Возвращаясь к проблеме нормализации данных, можно сказать, что в системах OLAP, использующих реляционную модель данных, данные целесообразно хранить в виде слабо нормализованных отношений, содержащих заранее вычисленные основные итоговые данные. Большая избыточность и связанные с ней проблемы тут не страшны, т.к. обновление происходит только в момент загрузки новой порции данных. При этом происходит как добавление новых данных, так и пересчет итогов.
-
Функциональная зависимость. Пример отношения и его функциональных зависимостей. Связь функциональных зависимостей и ограничений целостности. Тривиальная FD. Транзитивная FD.
Пусть задана переменная отношения R, и X и Y являются произвольными подмножествами заголовка R («составными» атрибутами).
В значении переменной отношения R атрибут Y функционально зависит (Functional Dependency – FD) от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y. В этом случае говорят также, что атрибут X функционально определяет атрибут Y (X является детерминантом (определителем) для Y, а Y является зависимым от X). Будем обозначать это как R.X –> R.Y. В общем случае X, Y – составные.
Пример:
СЛУ_НОМ -> СЛУ_ИМЯ
СЛУ_НОМ -> СЛУ_ЗАРП
СЛУ_НОМ -> ПРО_НОМ
СЛУ_НОМ -> ПРОЕКТ_РУК
ПРО_НОМ –> ПРОЕКТ_РУК
Все вышеперечисленные FD - инварианты, или ограничения целостности этой переменной отношения. Это значит, что FD порождаются не случайными явлениями в данной переменной, а знаниями из предметной области и выполняются всегда, даже при изменении отношения (например, если A — ключ отношения, то для любого B из заголовка этого отношения выполнена функциональная зависимость FD: A->B). Но бывают FD, не являющиеся инвариантами.
Например,
СЛУ_ИМЯ –> СЛУ_НОМ
тоже FD, но является таковой только потому, что нет совпадающих имен, иначе бы не выполнялось. Это не ограничение целостности.
FD A –> B называется тривиальной, если A содержит B. Очевидно, что любая тривиальная FD всегда выполняется.
FD A –> C называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости A –> B и B –> C и отсутствует функциональная зависимость C –> A.
.
-
Замыкание множества функциональных зависимостей. Аксиомы Армстронга (с доказательством). Расширенный набор правил вывода Дейта (с выводом).
Замыканием множества FD S является множество FD S+, включающее все FD, логически выводимые из FD множества S. Пример: (CN) -> (CName, CZarplata) => CN->CName и CN->CZarplata
Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг. Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD).
-
если B содержится в A, то A –> B (рефлексивность);
-
если A–> B, то AC –> BC (пополнение);
-
если A –> B и B –> C, то A –> C (транзитивность).
Истинность первой аксиомы Армстронга следует из того, что при B содержится в A FD A->B является тривиальной.
Справедливость второй аксиомы докажем от противного. Предположим, что FD AC->BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a), но t1 {BC} <> t2 {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}. Поскольку имеется FD A->B, должно соблюдаться равенство t1 {B} = t2 {B}. Тогда из неравенства (b) следует, что t1 {C} <> t2 {C}, что противоречит наличию тривиальной FD AC->C. Следовательно, предположение об отсутствии FD ACBC не является верным, и справедливость второй аксиомы доказана.