Теормин

Теоритический минимум. Базы данных1. Тип данных – определяется аналогично типу данных в любом ЯП.2. Домен – понятие, определяемое путем задания некоторого базового типа ипроизвольного логического выражения. (Допустимое потенциальное ограниченноеподмножество данного типа)3. Заголовок отношения – конечно множество пар вида <A,T> , где А – имя атрибута, Т –либо тип, либо домен.4.

Кортеж – множество упорядоченных триплетов вида <A,T,v>, где v – допустимое значениедомена T.5. Тело отношения – произвольное множество кортежей.6. Значение отношения – пара множеств Hr, Br.7. Переменная отношения – именованный контейнер, содержащий допустимое значениеотношения.8. Степень (3-7) – мощность заголовка отношения.9. Схема реляционной БД – набор пар, включающий имена и заголовки всех переменныхотношения, которые определены в БД.10. Первичный ключ переменной отношения – минимальное подмножество множестваатрибутов заголовка данного отношения, составное значение которых уникальноопределяет кортеж отношения.11.

Фундаментальные свойства отношений:1) Отсутствие кортежей-дубликатов в теле отношения2) Наличие у каждого значения отношения первичного ключа3) Отсутствие упорядоченности кортежей4) Отсутствие упорядоченности атрибутов5) Значения всех атрибутов являются атомарными ( 1NF)12. Возможный ключ – минимальный набор атрибутов, обладающий свойствомуникальности, но не являющийся первичный ключом.13. Модель данных – модель, описывающая некий набор родовых понятий и признаков,которыми должны обладать СУБД и БД, основанные на этой модели.14.

Реляционная модель:1) Структурная часть2) Манипуляционная часть3) Целостная часть15. Целостность сущности – у любой переменной отношения должен существоватьпервичный ключ, и никакое значения первичного ключа в кортежах переменной недолжно содержать неопределенного значения.16. Целостность по ссылкам – для каждого значения внешнего ключа ссылающейсяпеременной либо должен найтись кортеж с таким же значением первичного ключа,либо значение первичного ключа должно быть неопределенным.17. Операции алгебры Кодда:1) Объединение отношений (UNION)2) Пересечение отношений (INTERSECT)3) Взятие разности (MINUS)4) Взятие расширенного декартова произведения (TIMES)5) Соединение (JOIN)6) Ограничение (WHERE)7) Проекция (PROJECT)8) Деление (DIVIDE BY)9) Переименование (RENAME)10) Присваивание (:=)18.

Совместимость отношений по объединению – два отношения совместимы пообъединению в том и только в том случае, когда их заголовки совпадают19. Совместимость по взятию расширенного декартова произведения – два отношениясовместимы по взятию расширенного декартова произведения в том и только томслучае, когда пересечение множеств имен их атрибутов пусто20. Базис алгебры А - <NOT> , <AND>, <OR>, дополнение базиса - <RENAME>, <REMOVE>21.

Реляционное дополнение – в тело результата входят все кортежи, соответствующиезаголовку и не входящие в тело отношения:1) Hs = Hr (заголовок результата совпадает с заголовком операнда);2) Bs = {ts : exists tr (tr Br and ts = tr)22. Удаление атрибута - заголовок результата получается из заголовка операнда изъятиематрибута, в тело результата входят все кортежи операнда, из которых удалено значениеатрибута.23.

Реляционная конъюнкция (<AND>)1) Hs = Hr1 union Hr22) Тело принимает три разных формы в зависимости от значений заголовков:I. Схемы отношений имеют непустое пересечение – операция работает какестественное соединениеII. Пересечение схем отношений пусто – операция работает какрасширенное декартово произведениеIII. Схемы отношений совпадают – операция работает как пересечение24. Реляционная дизъюнкция (<OR>)1) Hs = Hr1 union Hr22) Тело принимает три разных формы в зависимости от значений заголовков:I.

Пересечение схем отношений пусто – тело результата содержит всекортежи, которые являются объединением кортежей tr1 и tr2,соответствующих заголовкам отношений-операндов, и хотя бы один из этихкортежей принадлежит телу одного из операндовII. Схемы отношений имеют непустое пересечение - тело результатасодержит все кортежи, которые являются объединением кортежей tr1 и tr2,соответствующих заголовкам отношений-операндов, если хотя бы один изэтих кортежей принадлежит телу одного из операндов, и значения общихатрибутов совпадаютIII.

Схемы отношений совпадают – тело результата является объединением телоперандов25. Алгебра А является полной:1) PROJECT ~ <REMOVE>2) UNION ~ <OR>3) TIMES, INTERSECT, JOIN ~ <AND>4) R1 MINUS R2 = R1 <AND> <NOT> R25) WHERE: R1 <AND> R2 , где R2 – тело, содержащее условие6) R1{A,B}, R2{B} , R1 DIVIDE BY R2 = (R1 PROJECT A) MINUS (((R2 TIMES (R1 PROJECT A)MINUS R1)PROJECT A)26. Функциональная зависимость. В значении переменной отношения r атрибут Yфункционально зависит от атрибута X в том и только в том случае, если каждомузначению Х соответствует в точности одно значение Y.

Здесь Х является детерминантом Y,a Y является зависимым от Х. r.X->r.Y27. Тривиальная функциональная зависимость. FD A->B называется тривиальной, если Bявляется подмножеством A.28. Замыкание множества FD. Замыканием множества FD S является множество FD S+,включающее все FD, логически выводимые из FD множества S.29. Транзитивная функциональная зависимость. FD A->C называется транзитивной, еслисуществует такой атрибут В, что имеются функциональные зависимости A->B и B->C иотсутствует зависимость C->A.30. Аксиомы Армстронга.1) Рефлексивность.

Если В – подмножество А, то A->B2) Пополнение. Если A->B, то AC->BC3) Транзитивность. Если A->B и B->C, то A->C31. Расширения аксиом Армстронга1) Самодетерминированность. A->A2) Декомпозиция. Если A->BC, то A->B и A->C3) Объединение. Если A->B и A->C, то A->BC4) Композиция. Если A->B и C->D, то AC->BD5) Накопление. Если A->BC и B->D, то A->BCD32. Замыкание множества атрибутов. Пусть заданы отношение r, множество Z атрибутовэтого отношения и некоторое множество FD S, выполняемых для r.

Тогда замыканием Zнад S называется наибольшее множество Z+ таких атрибутов Y отношения r, что FD Z->Yвходит в S+33. Алгоритм вычисления Z+.34. Суперключ отношения r – любое подмножество К заголовка r, включающее, по меньшеймере, хотя бы один возможный ключ r.35. Покрытие множества FD. Множество S2 называется покрытием множества S1, если любаяFD, выводимая из S1, выводится так же и из S2.36.

Эквивалентные множества – множество, каждое из которых является покрытием другого.37. Минимальное множество FD. Множество FD S называется минимальным в том и только втом случае, когда оно удовлетворяет следующим свойствам:1) Правая часть любой FD из S является множеством из одного атрибута.2) Детерминант каждой FD из S обладает свойством минимальности: удалениелюбого атрибута из детерминанта приводит к изменению замыкания.3) Удаление любой зависимости из S приводит к изменению замыкания.38. Для любого множества FD S существует эквивалентное ему минимальное множество.39.

Минимальное покрытие множества FD S – любое минимальное множество FD S1,эквивалентное S.40. Декомпозиция без потерь – декомпозиция отношения, которая обратима.41. Теорема Хита. Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являютсясоставными атрибутами) и выполняется FD-> AB. Тогда r = (r PROJECT {A, B}) NATURAL JOIN(r PROJECT {A, C}).42. Минимально зависимые атрибуты.

Атрибут В минимально зависит от атрибута А, есливыполняется минимальная слева FD A->B.43. Свойства нормальных форм:1) Каждая следующая NF устраняет проблемы предыдущей2) В каждой следующей NF все свойства предыдущей сохраняются44. Аномалии обновления – трудности при выполнении операции добавления, удаления имодификации кортежей.45. Вторая нормальная форма (2NF). Переменная отношения находится во второйнормальной форме тогда и только тогда, когда она находится в первой нормальнойформе, и каждый неключевой атрибут минимально зависит от первичного ключа.46.

Третья нормальная форма (3NF). Переменная отношения находится в третьейнормальной форме тогда и только тогда, когда она находится во второй нормальнойформе, и каждый неключевой атрибут нетранзитивно функционально зависит отпервичного ключа.47. Независимые проекции отношений – проекции, которые могут обновляться независимо.48. Теорема Риссанена. Проекции r1 и r2 отношения r являются независимыми тогда и толькотогда, когда:1) Каждая FD в отношении r логически следует из FD в r1 и r2.2) Общие атрибуты r1 и r2 образуют возможный ключ хотя бы для одного из этихотношений.49. Атомарное отношение – отношение, которое нельзя деклмпозировать на независимыепроекции.50. Нормальная форма Бойса-Кодда (BCNF).

Переменная отношения находится внормальной форме Бойса-Кодда тогда и только тогда, когда любая выполняемая дляэтой переменной отношения нетривиальная иминимальная FD имеет в качестведетерминанта некоторый возможный ключ данного отношения.51. Многозначная зависимость. В переменной отношения r с атрибутами А,В,С ( в общемслучае, составными) имеется многозначная зависимость В от А (A->->B) в том и только втом случае, когда множество значений атрибута В, соответсвующее паре значенийатрибутов А и С, зависит от значения А и не зависит от значения С.52. Лемма Фейджина. В отношении r{A,B,C} выполняется MVD A->->B в том и только в томслучае, когда выполняется MVD A->->C.53. Теорема Фейджина.

Пусть имеется переменная отношения r с атрибутами А,В,С ( вобщем случае, составными). Отношение r декомпозируется без потерь на проекции{A,B} и {A,C} тогда и только тогда, когда для него выполняется MVD A->->B|C.54. Четвертая нормальая форма (4NF). Переменная отношения r находится в четвертойнормальной форме в том и только в том случае, когда она находится в BCNF, и все MVDr являются FD с детерминантами – возможными ключами отношения r.55. Тривиальная многозначная зависимость. В переменной отношения r с атрибутами A и В(в общем случае, составными) MVD A->->B называется тривиальной, если либо В естьподмножество А, либр A UNION B=r.56.