link3256 link3257 link3258 link3259 link3260 link3261 link3262 link3263 link3264 link3265 link3266 link3267 link3268 link3269 link3270 link3271 link3272 link3273 link3274 link3275 link3276 link3277 link3278 link3279 link3280 link3281 link3282 link3283 link3284 link3285 link3286 link3287 link3288 link3289 link3290 link3291 link3292 link3293 link3294 link3295 link3296 link3297 link3298 link3299 link3300 link3301 link3302 link3303 link3304 link3305 link3306 link3307 link3308 link3309 link3310 link3311 link3312 link3313 link3314 link3315 link3316 link3317 link3318 link3319 link3320 link3321 link3322 link3323 link3324 link3325 link3326 link3327 link3328 link3329 link3330 link3331 link3332 link3333 link3334 link3335 link3336 link3337 link3338 link3339 link3340 link3341 link3342 link3343 link3344 link3345 link3346 link3347 link3348 link3349 link3350 link3351 link3352 link3353 link3354 link3355 link3356 link3357 link3358 link3359 link3360 link3361 link3362 link3363 link3364 link3365 link3366 link3367 link3368 link3369 link3370 link3371 link3372 link3373 link3374 link3375 link3376 link3377 link3378 link3379 link3380 link3381 link3382 link3383 link3384 link3385 link3386 link3387 link3388 link3389 link3390 link3391 link3392 link3393 link3394 link3395 link3396 link3397 link3398 link3399 link3400 link3401 link3402 link3403

Курс лекций: Информационное обеспечение автоматизированных библиотечных систем. Часть 4 — Операции реляционной алгебры

Операции реляционной алгебры

1. В процессе преобразования базы данных (её нормализации) с целью устранения избыточности и повышения надежности часто необходимо разбить большие таблицы на более мелкие. Но как затем сформировать требуемый ответ на запрос пользователя, если нужные для этого данные хранятся в разных таблицах? Для этого в рамках реляционной алгебры разработаны следующие операции над отношениями:

2. Объединение R=R1И R2;

3. Пересечение R=R1З R2

4. Вычитание R=R1–R2;

5. Эти три операции выполняются над строками отношений и имеют полные аналоги с операциями над множествами. При этом требуется одинаковая арность отношений, участвующих в операции.

6. Декартово произведение R = R1*R2.

7. В результате получается отношение R, содержащее все попарные комбинации строк двух перемножаемых отношений R1 и R2. При этом если отношение R1 обладает арностью k1 и количеством строк s1, а отношение R2 — арностью k2 и количеством строк s2, то результирующее отношение R имеет арность k=k1+k2 и содержит в себе s=s1*s2 строк.

8. Проецирование на атрибуты R = ПРA1,…,An R1.

9. Здесь A1,…,An — атрибуты на которые происходит проецирование. В результате этой операции получается отношение, содержащее только указанные атрибуты исходного отношения. Количество строк в отношении при этом остается прежним.

10. Операция выборки R = ПРУСЛОВИЕ R1.

11. В результате этой операции из исходного отношения выбираются только те строки, которые удовлетворяют указанному условию. Число атрибутов в отношении при этом не меняется.

12. Операция соединения отношений по определенному условию.

Почему БД может быть плохой?

Приведем пример плохой БД. Пусть проектируется база “Питание”. Эту базу можно представить в виде одного отношения, представленного на рисунке.

Начинающий проектировщик будет использовать данное отношение в качестве завершенной БД. Действительно, зачем разбивать его на несколько более мелких отношений, если оно заключает в себе все данные? А разбивать надо потому, что при использовании такого единственного отношения возникает несколько проблем:

1. Избыточность. Данные практически всех столбцов многократно повторяются. Повторяются и некоторые наборы данных (Блюдо-Вид-Рецепт, Продукт-Калорийность, Поставщик-Город-Страна). Нежелательно повторение рецептов, некоторые из которых намного больше рецепта «Лобио». И уж совсем плохо, что все данные о блюде (включая рецепт) повторяются каждый раз, когда это блюдо включается в меню.

2. Потенциальная противоречивость (аномалии обновления). Вследствие избыточности можно обновить адрес поставщика в одной строке, оставляя его неизменным в других. Если поставщик кофе сообщил о своем переезде в Харбин и была обновлена строка с продуктом кофе, то у поставщика «Хуанхэ» появляется два адреса, один из которых не актуален. Следовательно, при обновлениях необходимо просматривать всю таблицу для нахождения и изменения всех подходящих строк.

3. Аномалии включения. В БД не может быть записан новый поставщик («Няринга», Вильнюс, Литва), если поставляемый им продукт (Огурцы) не используется ни в одном блюде. Можно, конечно, поместить неопределенные значения в столбцы Блюдо, Вид, Порций и Вес (г) для этого поставщика. Но если появится блюдо, в котором используется этот продукт, не забудем ли мы удалить строку с неопределенными значениями?

clip_image016

По аналогичным причинам нельзя ввести и новый продукт (например, Баклажаны), который предлагает существующий поставщик (например, "Полесье"). А как ввести новое блюдо, если в нем используется новый продукт (Крабы)?

4. Аномалии удаления. Обратная проблема возникает при необходимости удаления всех продуктов, поставляемых данным поставщиком или всех блюд, использующих эти продукты. При таких удалениях будут утрачены сведения о таком поставщике.

Многие проблемы этого примера исчезнут, если выделить в отдельные таблицы сведения о блюдах, рецептах, расходе блюд, продуктах и их поставщиках, а также создать связующие таблицы «Состав» и «Поставки» .

В полученной БД все еще много повторяющихся данных, находящихся в связующих таблицах (Состав и Поставки). Следовательно, в данном варианте БД сохранилась потенциальная противоречивость: для изменения названия поставщика с «Полесье» на «Днепро» придется изменять не только строку таблицы Поставщики, но и множество строк таблицы Поставки. При этом не исключено, что в БД будут одновременно храниться: "Полесье", "Палесье", «Днепро», «Днипро» и другие варианты названий.

Для исключения ссылок на длинные текстовые значения последние обычно нумеруют: нумеруют блюда в больших кулинарных книгах, товары (продукты) в каталогах и т.д. Воспользуемся этим приемом для исключения избыточного дублирования данных и появления ошибок при копировании длинных текстовых значений. Теперь при изменении названия поставщика «Полесье» на «Днепро» исправляется единственное значение в таблице Поставщики. И даже если оно вводится с ошибкой («Днипро»), то это не может повлиять на связь между поставщиками и продуктами (в связующей таблице Поставки используются номера поставщиков и продуктов, а не их названия). Окончательный вариант базы данных «Питание» приведен на следующем рисунке.

clip_image018

Нормализация таблиц

Нормализация — это разбиение таблицы на две или более, обладающих лучшими свойствами при включении, изменении и удалении данных. Окончательная цель нормализации сводится к получению такого проекта базы данных, в котором каждый факт появляется лишь в одном месте, т.е. исключена избыточность информации. Это делается не столько с целью экономии памяти, сколько для исключения возможной противоречивости хранимых данных.

Процесс нормализации заключается в приведении таблиц в так называемые нормальные формы. Существует несколько видов нормальных форм: первая нормальная форма (1НФ), вторая нормальная форма (2НФ), третья нормальная форма (3НФ), нормальная форма Бойса-Кодда (НФБК), четвертая нормальная форма (4НФ), пятая нормальная форма (5НФ). С практической точки зрения, достаточно трех первых форм — следует учитывать время, необходимое системе для “соединения” таблиц при отображении их на экране. Поэтому мы ограничимся изучением процесса приведения отношений к первым трем формам.

Этот процесс включает:

· устранение повторяющихся групп (приведение к 1НФ);

· удаление частично зависимых атрибутов (приведение к 2НФ);

· удаление транзитивно зависимых атрибутов (приведение к 3НФ).

Приведение к первой нормальной форме

Когда поле в данной записи содержит более одного значения для каждого вхождения первичного ключа, такие группы данных называются повторяющимися группами. 1НФ не допускает наличия таких многозначных полей. Иными словами, значение каждого атрибута должно быть атомарным. Полная формулировка 1-й НФ следующая:

Таблица находится в первой нормальной форме (1НФ) тогда и только тогда, когда ни одна из ее строк не содержит в любом своем поле более одного значения и ни одно из ее ключевых полей не пусто.

Приведение ко второй нормальной форме

Следующий важный шаг в процессе нормализации состоит в удалении всех неключевых атрибутов, которые зависят только от части первичного ключа. Такие атрибуты называются частично зависимыми. Неключевые атрибуты заключают в себе информацию о данной сущности предметной области, но не идентифицируют ее уникальным образом. В теории вторая нормальная форма определяется через понятия функциональной зависимости:

Таблица находится во второй нормальной форме (2НФ), если она удовлетворяет определению 1НФ и все ее поля, не входящие в первичный ключ, связаны полной функциональной зависимостью с первичным ключом.

Функциональная зависимость. Поле В таблицы функционально зависит от поля А той же таблицы в том и только в том случае, когда в любой заданный момент времени для каждого из различных значений поля А обязательно существует только одно из различных значений поля В. Отметим, что здесь допускается, что поля А и В могут быть составными.

Полная функциональная зависимость. Поле В находится в полной функциональной зависимости от составного поля А, если оно функционально зависит от А и не зависит функционально от любого подмножества поля А.

Приведение к третьей нормальной форме

Третий этап процесса приведения таблиц к нормальной форме состоит в удалении всех неключевых атрибутов, которые зависят от других неключевых атрибутов. Каждый неключевой атрибут должен быть логически связан с атрибутом (атрибутами), являющимся первичным ключом. Таким образом:

Таблица находится в третьей нормальной форме (3НФ), если она удовлетворяет определению 2НФ и не одно из ее неключевых полей не зависит функционально от любого другого неключевого поля.

Вы здесь: Главная Библиотечное дело Курс лекций: Информационное обеспечение автоматизированных библиотечных систем. Часть 4