Общие понятия реляционного подхода к организации бд. Основные концепции и термины Домен - umotnas.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
История развития средств компьютерной обработки данных. Обоснование... 1 131.1kb.
Правила проведения Акции «sportivный look» общие положения термины... 1 126.1kb.
Правила проведения Акции «Блондинки против Брюнеток» общие положения... 1 116.21kb.
Правила проведения Акции «Поездка в Вену на концерт группы Depeche... 1 146.81kb.
Общие понятия и термины по теме: ? Краткий план ответа 1 35.83kb.
Учебно-методическое и информационное обеспечение дисциплины Список... 1 13.28kb.
Термины и определения 1 53.04kb.
Термины и определения 1 63.75kb.
Программа экзамена по дисциплине «Информационный менеджмент» Основные... 1 13.97kb.
Специфика художественной речи. Диалог. Монолог 1 14.26kb.
Статья Основные понятия, используемые в настоящем законе используются... 1 148.08kb.
Тестовые вопросы по Дискретной математике 1 114.21kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Общие понятия реляционного подхода к организации бд. Основные концепции и термины - страница №3/3

Избыточность операции переименования.


Наконец, покажем, что избыточна и операция . Ну там надо тупо добавить к таблице еще один столбец, копию столбца, который собираемся переименовывать, но уже с новым именем. А потом REMOVE столбец со старым названием.

Тем самым, можно сократить набор операций Алгебры A до двух операций: (или


) и и операции присваивания переменной отношения.
Реляционное исчисление кортежей

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


В исчислении кортежей областями определения переменных являются тела отношений базы данных, т. е. допустимым значением каждой переменной является кортеж тела некоторого отношения.

Для определения кортежной переменной используется оператор RANGE. Например, для того чтобы определить переменную СЛУЖАЩИЙ, областью определения которой является отношение СЛУЖАЩИЕ, нужно употребить конструкцию

RANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕ

Как уже говорилось, из этого определения следует, что в любой момент времени переменная СЛУЖАЩИЙ представляет некоторый кортеж отношения СЛУЖАЩИЕ. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке C можно сослаться на значение поля структурной переменной). Например, для того, чтобы сослаться на значение атрибута СЛУ_ИМЯ переменной СЛУЖАЩИЙ, нужно употребить конструкцию СЛУЖАЩИЙ.СЛУ_ИМЯ.



Правильно построенная формула (Well-Formed Formula, WFF) служит для выражения условий, накладываемых на кортежные переменные.

Способ реализации, который приводит к получению области истинности рассмотренной формулы, в действительности является наиболее общим (и зачастую неоптимальным) способом выполнения операций соединения (он называется методом вложенных циклов – nested loops join). ( два вложенных цикла, по первому переменной и по второй, применяется в случае формулы типа перем1.что-то=перем2.кто-то )

При построении WFF допускается использование кванторов существования (EXISTS) и всеобщности (FORALL). Если form – это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют собой WFF. По определению, формула EXISTS var (form) принимает значение true в том и только в том случае, если в области определения переменной var найдется хотя бы одно значение (кортеж), для которого WFF form принимает значение true. Формула FORALL var (form) принимает значение true, если для всех значений переменной var из ее области определения WFF form принимает значение true.

Переменные, входящие в WFF, могут быть свободными или связанными. По определению, все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var является связанной переменной. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся область ее определения.

Итак, 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 используется несколько свободных переменных с одинаковой областью определения. Фактически применение целевого списка к области истинности WFF эквивалентно действию алгебраической операции проекции, а последний из приведенных вариантов представляет собой некоторую разновидность алгебраической операции переименования атрибута.

Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE WFF. Значением выражения является отношение, тело которого определяется WFF, а множество атрибутов и их имена – целевым списком.

Реляционное исчисление доменов.

В исчислении доменов областью определения переменных являются не отношения, а домены.

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного множества предикатов, позволяющих выражать так называемые условия членства. Если R – это n-арное отношение с атрибутами a1, a2, ..., an, то условие членства имеет вид R (ai1 : vi1, ai2 : vi2, ..., aim : vim) (m http://citforum.ru/database/advanced_intro/le.gifn), где vij – это либо литерально задаваемая константа, либо имя доменной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов. Если vij – константа, то на атрибут aij накладывается жесткое условие, не зависящее от текущих значений доменных переменных; если же vij – имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

Функциональные зависимости, замыкание множества функциональных зависимостей, аксиомы Армстронга, замыкание множества атрибутов. Минимальное покрытие множества функциональных зависимостей
Пусть задана переменная отношения R, и X и Y являются произвольными подмножествами заголовка R («составными» атрибутами). В значении переменной отношения R атрибут Y функционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точности одно значение Y. В этом случае говорят также, что атрибут X функционально определяет атрибут Y (X является детерминантом (определителем) для Y, а Y является зависимым от X). Будем обозначать это как R.Xhttp://citforum.ru/database/advanced_intro/srarr.gifR.Y.

Итак, мы будем иметь дело с FD, которые выполняются для всех возможных состояний тела соответствующего отношения и могут рассматриваться как ограничения целостности. Таких зависимостей может быть очень много. Поскольку они трактуются как ограничения целостности, за их соблюдением должна следить СУБД. Поэтому важно уметь сократить набор FD до минимума, поддержка которого гарантирует выполнение всех зависимостей.

FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB называется тривиальной, если Ahttp://citforum.ru/database/advanced_intro/supe.gifB (т. е. множество атрибутов A включает множество B или совпадает с множеством B). Очевидно, что любая тривиальная FD всегда выполняется. Частным случаем тривиальной FD является Ahttp://citforum.ru/database/advanced_intro/srarr.gifA. Поскольку тривиальные FD выполняются всегда, их нельзя трактовать как ограничения целостности, и поэтому они не представляют интереса с практической точки зрения. Однако в теоретических рассуждениях их наличие необходимо учитывать.

Замыканием множества FD S является множество FD S+, включающее все FD, логически выводимые из FD множества S.

FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifC называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости Ahttp://citforum.ru/database/advanced_intro/srarr.gifB и Bhttp://citforum.ru/database/advanced_intro/srarr.gifC и отсутствует функциональная зависимость Chttp://citforum.ru/database/advanced_intro/srarr.gifA.



Аксиомами Армстронга:

Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг. Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения R. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:



  1. если B http://citforum.ru/database/advanced_intro/sube.gifA, то Ahttp://citforum.ru/database/advanced_intro/srarr.gifB (рефлексивность);

  2. если Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, то AChttp://citforum.ru/database/advanced_intro/srarr.gifBC (пополнение);

  3. если Ahttp://citforum.ru/database/advanced_intro/srarr.gifB и Bhttp://citforum.ru/database/advanced_intro/srarr.gifC, то Ahttp://citforum.ru/database/advanced_intro/srarr.gifC (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при Bhttp://citforum.ru/database/advanced_intro/sube.gifA FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD AChttp://citforum.ru/database/advanced_intro/srarr.gifBC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a), но t1 {BC} http://citforum.ru/database/advanced_intro/ne.gift2 {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}. Поскольку имеется FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, должно соблюдаться равенство t1 {B} = t2 {B}. Тогда из неравенства (b) следует, что t1 {C} http://citforum.ru/database/advanced_intro/ne.gift2 {C}, что противоречит наличию тривиальной FD AChttp://citforum.ru/database/advanced_intro/srarr.gifC. Следовательно, предположение об отсутствии FD AChttp://citforum.ru/database/advanced_intro/srarr.gifBC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} http://citforum.ru/database/advanced_intro/ne.gift2 {C}. Но из наличия FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB следует, что t1 {B} = t2 {B}, а потому из наличия FD Bhttp://citforum.ru/database/advanced_intro/srarr.gifC следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifC не является верным, и справедливость третьей аксиомы доказана.



Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

  1. Ahttp://citforum.ru/database/advanced_intro/srarr.gifA (самодетерминированность) – прямо следует из правила (1);

  2. если Ahttp://citforum.ru/database/advanced_intro/srarr.gifBC, то Ahttp://citforum.ru/database/advanced_intro/srarr.gifB и Ahttp://citforum.ru/database/advanced_intro/srarr.gifC (декомпозиция) – из правила (1) следует, что BChttp://citforum.ru/database/advanced_intro/srarr.gifB; по правилу (3) Ahttp://citforum.ru/database/advanced_intro/srarr.gifB; аналогично, из BChttp://citforum.ru/database/advanced_intro/srarr.gifС и правила (3) следует Ahttp://citforum.ru/database/advanced_intro/srarr.gifC;

  3. если Ahttp://citforum.ru/database/advanced_intro/srarr.gifB и Ahttp://citforum.ru/database/advanced_intro/srarr.gifC, то Ahttp://citforum.ru/database/advanced_intro/srarr.gifBC (объединение) – из правила (2) следует, что Ahttp://citforum.ru/database/advanced_intro/srarr.gifAB и ABhttp://citforum.ru/database/advanced_intro/srarr.gifBC; из правила (3) следует, что Ahttp://citforum.ru/database/advanced_intro/srarr.gifBC;

  4. если Ahttp://citforum.ru/database/advanced_intro/srarr.gifB и Chttp://citforum.ru/database/advanced_intro/srarr.gifD, то AChttp://citforum.ru/database/advanced_intro/srarr.gifBD (композиция) – из правила (2) следует, что AСhttp://citforum.ru/database/advanced_intro/srarr.gifBС и BChttp://citforum.ru/database/advanced_intro/srarr.gifBD; из правила (3) следует, что AChttp://citforum.ru/database/advanced_intro/srarr.gifBD;

  5. если Ahttp://citforum.ru/database/advanced_intro/srarr.gifBC и Bhttp://citforum.ru/database/advanced_intro/srarr.gifD, то Ahttp://citforum.ru/database/advanced_intro/srarr.gifBCD (накопление) – из правила (2) следует, что BСhttp://citforum.ru/database/advanced_intro/srarr.gifBCD; из правила (3) следует, что Ahttp://citforum.ru/database/advanced_intro/srarr.gifBCD.

Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Z+ таких атрибутов Y отношения R, что FD Zhttp://citforum.ru/database/advanced_intro/srarr.gifY входит в S+.

Алгоритм вычисления Z+



Докажем корректность алгоритма по индукции. На нулевом шаге Z[0] = Z, FD Zhttp://citforum.ru/database/advanced_intro/srarr.gifZ[I], очевидно, принадлежит S+ (тривиальная FD «выводится» из любого множества FD). Пусть для некоторого K выполняется FD Zhttp://citforum.ru/database/advanced_intro/srarr.gifZ[K], и пусть мы нашли в S такую FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, что Ahttp://citforum.ru/database/advanced_intro/sube.gifZ[K]. Тогда можно представить Z[K] в виде AC, и, следовательно, выполняется FD Zhttp://citforum.ru/database/advanced_intro/srarr.gifAC. Но по правилу (8) мы имеем FD Zhttp://citforum.ru/database/advanced_intro/srarr.gifACB, т.е. FD Zhttp://citforum.ru/database/advanced_intro/srarr.gif(Z[K] UNION B) входит во множество S+, что переводит нас на следующий шаг индукции.

Пусть для примера имеется отношение с заголовком {A, B, C, D, E, F} и заданным множеством FD S = {Ahttp://citforum.ru/database/advanced_intro/srarr.gifD, ABhttp://citforum.ru/database/advanced_intro/srarr.gifE, BFhttp://citforum.ru/database/advanced_intro/srarr.gifE, CDhttp://citforum.ru/database/advanced_intro/srarr.gifF, Ehttp://citforum.ru/database/advanced_intro/srarr.gifC}. Пусть требуется найти {AE}+ над S. На первом проходе тела цикла DO Z[1] равно AE. В теле цикла FOR EACH будут найдены FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifD и Ehttp://citforum.ru/database/advanced_intro/srarr.gifC, и в конце цикла Z[1] станет равным ACDE. На втором проходе тела цикла DO при Z[2], равном ACDE, в теле цикла FOR EACH будет найдена FD CDhttp://citforum.ru/database/advanced_intro/srarr.gifF, и в конце цикла Z[2] станет равным ACDEF. Следующий проход тела цикла DO не изменит Z[3], и Z+ ({AE}+) будет равно ACDEF.

Алгоритм построения замыкания множества атрибутов Z над заданным множеством FD S помогает легко установить, входит ли заданная FD Zhttp://citforum.ru/database/advanced_intro/srarr.gifB в замыкание S+. Очевидно, что необходимым и достаточным условием для этого является Bhttp://citforum.ru/database/advanced_intro/sube.gifZ+, т. е. вхождение составного атрибута B в замыкание Z.

Суперключом отношения R называется любое подмножество K заголовка R, включающее, по меньшей мере, хотя бы один возможный ключ R.

Одно из следствий этого определения состоит в том, что подмножество K заголовка отношения R является суперключом тогда и только тогда, когда для любого атрибута A (возможно, составного) заголовка отношения R выполняется FD Khttp://citforum.ru/database/advanced_intro/srarr.gifA. В терминах замыкания множества атрибутов K является суперключом тогда и только тогда, когда K+ совпадает с заголовком R.



Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.
Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+http://citforum.ru/database/advanced_intro/sube.gifS2+. Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1+ = S2+.
Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

  1. правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);

  2. детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т. е. порождению множества FD, не эквивалентного S30);

  3. удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.

Для любого множества FD S существует (и даже может быть построено) эквивалентное ему минимальное множество S-.

Приведем общую схему построения S- по заданному множеству FD S. Во-первых, используя правило (5) (декомпозиции), мы можем привести множество S к эквивалентному множеству FD S1, правые части FD которого содержат только одноэлементные множества (простые атрибуты). Далее, для каждой FD из S1, детерминант D {D1, D2, …, Dn} которой содержит более одного атрибута, будем пытаться удалять атрибуты Di, получая множество FD S2. Если после удаления атрибута Di S2 эквивалентно S1, то этот атрибут удаляется, и пробуется следующий атрибут. Назовем S3 множество FD, полученное путем допустимого удаления атрибутов из всех детерминантов FD множества S1. Наконец, для каждой FD f из множества S3 будем проверять эквивалентность множеств S3 и S3 MINUS {f}. Если эти множества эквивалентны, удалим f из множества S3, и в заключение получим множество S4, которое минимально и эквивалентно исходному множеству FD S.

Пример (оставил ради понимания что происходит) :

Пусть, например, имеется отношение R {A, B, C, D} и задано множество FD S = {Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, Ahttp://citforum.ru/database/advanced_intro/srarr.gifBC, ABhttp://citforum.ru/database/advanced_intro/srarr.gifC, AChttp://citforum.ru/database/advanced_intro/srarr.gifD, Bhttp://citforum.ru/database/advanced_intro/srarr.gifC}. По правилу декомпозиции S эквивалентно множеству S1 {Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, Ahttp://citforum.ru/database/advanced_intro/srarr.gifC, ABhttp://citforum.ru/database/advanced_intro/srarr.gifC, AChttp://citforum.ru/database/advanced_intro/srarr.gifD, Bhttp://citforum.ru/database/advanced_intro/srarr.gifC}. В детерминанте FD AChttp://citforum.ru/database/advanced_intro/srarr.gifD можно удалить атрибут C, поскольку по правилу дополнения из FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifC следует Ahttp://citforum.ru/database/advanced_intro/srarr.gifAC; по правилу транзитивности выводится FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifD, поэтому атрибут C в детерминанте FD AChttp://citforum.ru/database/advanced_intro/srarr.gifD является избыточным. FD ABhttp://citforum.ru/database/advanced_intro/srarr.gifC может быть удалена, поскольку может быть выведена из FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifC (по правилу пополнения из этой FD выводится ABhttp://citforum.ru/database/advanced_intro/srarr.gifBC, а по правилу декомпозиции далее выводится ABhttp://citforum.ru/database/advanced_intro/srarr.gifC). Наконец, FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifC тоже выводится по правилу транзитивности из FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB и Bhttp://citforum.ru/database/advanced_intro/srarr.gifC. Таким образом, мы получаем множество зависимостей {Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, Ahttp://citforum.ru/database/advanced_intro/srarr.gifD, Bhttp://citforum.ru/database/advanced_intro/srarr.gifC}, которое является минимальным и эквивалентно S по построению.

Минимальным покрытием множества FD S называется любое минимальное множество FD S1, эквивалентное S.

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



Декомпозиция без потерь и функциональные зависимости, теорема Хита

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

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

Теорема Хита (Корректность декомпозиции).

Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB. Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}).



Доказательство. Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через r1) содержатся все кортежи тела отношения r. Действительно, пусть кортеж {a, b, c} http://citforum.ru/database/advanced_intro/isin.gifr. Тогда по определению операции взятия проекции {a, b} http://citforum.ru/database/advanced_intro/isin.gif(r PROJECT {A, B}) и {a, с} http://citforum.ru/database/advanced_intro/isin.gif(r PROJECT {A, С}). Следовательно, {a, b, c} http://citforum.ru/database/advanced_intro/isin.gifr1. Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т. е. что если кортеж {a, b, c} http://citforum.ru/database/advanced_intro/isin.gifr1, то {a, b, c} http://citforum.ru/database/advanced_intro/isin.gifr. Если {a, b, c} http://citforum.ru/database/advanced_intro/isin.gifr1, то существуют {a, b} http://citforum.ru/database/advanced_intro/isin.gif(r PROJECT {A, B}) и {a, с} http://citforum.ru/database/advanced_intro/isin.gif(r PROJECT {A, С}). Последнее условие может выполняться в том и только в том случае, когда существует кортеж {a, b*, c} http://citforum.ru/database/advanced_intro/isin.gifr. Но поскольку выполняется FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB, то b = b* и, следовательно, {a, b, c} = {a, b*, c}. Конец доказательства.

Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD Ahttp://citforum.ru/database/advanced_intro/srarr.gifB.

Управление буферами основной памяти

Если бы при выполнении логических действий в базу данных сразу бы помещался результат этой операции, то скорость работы такой СУБД была бы сравнима со скоростью работы магнитных носителей. А скорости работы магнитных носителей всегда были и будут несравнимо ниже скорости работы оперативной памяти. Точно также, если при каждом обращении к страницам данных, СУБД будет лесть на внешнюю память, то произойдет тоже самое. На самом деле работа СУБД организована с помощью буферов в оперативной памяти. А именно с помощью буферного пула, в которой помещаются страницы данных или же индексные страницы, а также буфера журналльных записей, в который, соответственноЭ, помещаются все действия над журналом.

Когда СУБД требуется какая-то страницы данных, она копирует ее в буферный пул, и выполняет все изменения над ней в буферном пуле.

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

Но вопрос, какую из страниц?

В операционных системах в таком случае использовался алгоритм LRU. Тоесть, выталкивалась та страница, которая дольше всего не использовалась в прошлом( своеобразный прогноз на будущее). Но СУБД умнее. Она может более точно прогнозировать, какая страница понадобится в будущем, а какая нет. Например, при последовательном сканировании (NEXT без использования индекса) некоторой таблицы, можно заранее предугадать, какая страница дальше потребуется, и скопировать ее во внутреннюю память. Точно также, можно с уверенностью сказать, что индексные страницы будут успользоваться очень часто( имеются в виду страницы хранящие корни индексов). Поэтому, кроме такого прогноза, еще этот алгоритм LRU в СУБД снабжен системой приоритетов. Так, например страница корневой индексной информации будет иметь самый высокий приоритет и почти никогда не будет вытолкнута.



Физически согласованное состояние базы данных

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

Опр: Состояние базы данных называется физически согласованным, если все страницы данных, соответствующие каждому общекту базы данных либо соответствую состоянию объекта до изменения, либо состоянию объекта после изменения.

Пример


Теневой механизм

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

Чтобы восстановить последнее согласованное состояние текущая таблица отображения заменяется теневой таблицей.

Другой подход- Журнализация постраницных изменений. Он основан на том, что нужно журнулировать не только лоигические изменения над базой данных( изменения кортежей), но и физические постраницные изменения.Сначала откатываются все незавершенные логические операции над БД. Тоочно также журнализация постраничных изменений от одной лигической операции заканчивается завершающей операцией.

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

Иногда эти два журнала(логический и физический) хранят вместе, но обычно их разделяют на два

При создании новой точки физической согласованности:



  1. Прекращается инициализация новых логических операций

  2. После завершения всех лог операций, все страницы выталкиывются из буферного пула

  3. Формируется и вуталкивается в буферный пул специальная запись о точке физического согласованного состояния

  4. Если предыдущая запись выполнилась нормально, то внови разрешают логические операции.

Ситуации, требующие восстановление базы данных:

  1. Откат транзакций. Это может произойти путем выполнения операции ROLLBACK или же путем возникновения исключительной ситуации(например, деление на 0). Также транзакция может быть выбрана жертвой при возникновении тупиковой ситуации

  2. Мягкий сбой.Теряется содержимое оперативной памяти(например, при аварийном отключении питания.)

  3. Самый редкий случай-жесткий сбой. Возникает при потери данных с внешней памяти( примером может служить поломка магнитного диска)

Во всех трех случаях для восстановления базы данных используется журнал. В нем хранится вся последовательность изменений, происходящих с базой данных.

Существуют два основных подходя ведения журнала. Первый из которых- также хранение индивидуальных журналов для каждой транзакций. Обесечивает быстрый откат транзакций.

Второй подход основывается на ведении общего журнала.

Но каждый из подходов означает хранение избыточной информации для обеспечения возможности восстановления базы данных.

Индивидуальный откат транзакций

При индивидуальном откате транзакиций все операции, относящиеся к данной транзакции связывают в обратный список,в котором последней операцие всегда является операция начала транзакции. В общем случае для завершенной транзакции, результаты всех операций уже будут вытолкнуты из буферного пула, а значит первой операцией будет операция, завершающая транзакцию. Такие транзакции уже невозможно откатить. В случае, когда транзакция не завершена, какие-то даже уже выполненные операции могут быть из буфера не вытолкнуты и, соответственно, в журнале( по протоколу write ahead Log) находиться не могут. Тогда первой для такой транзакции будет некоторая операция транзакции.



  1. Сначала по порядку из списка выбираются операции

  2. Для выполнения отката индивидуальной транзакции, все операции из данного списка, заменяясь на противоположные( тоесть вставка заменяется на удаление удаление на вставку а обновление заменяется на обновление, производящще обратные действия)

  3. Каждая такая операция также журнализируется. В случае происхождения сбоя во время отката транзакции, все операции по откату откатываются и потом откат начинается сначала.

  4. Далее, в случае успешного завершения, журнале отражается операция завершения транзакции, и такая транзакция считается завершенной и зафиксированной.

Протокол Write Ahead Log.

При выполнении некоторых транзакций, действия изменения базы данных не сразу отражаются в базе данных, а сначала буферизуются, и когда в буфере нет места для вставки новой страницы, и некоторая страница выталкивается из буфера,и, если она отличается от страницы в во внешней памяти, то страница во внешней памяти заменчется на нее.Журнальная информация выталкивается из буфера в том случае, если этот буфер целиком заполнился. Вопрос состоит в том, в каком порядке нужно помещать информацию из буферов так, чтобы при возможности можно было восстановить БД при сбое во время такого выталкивания. Ответ дает протокол Write Ahead Log

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

Восстановление базы данных после жесткого сбоя

Самый простой способ восстановления:

Нужел логический журнал и архивная копия


  1. Копирование Базы данных из архивной копии на носитель

  2. Обратное выполнение всех операций из логического журнала

Если журнал утерян, то единственный способ-возврат к архивной копии.

Способы архивирования:



  1. Администратор сам решает, когда нужно архивировать

  2. Тогда, когда переполняется журнал

Но можно выполнять архивацию и реже, чем переполняется журнал.Можно выполнять архивацию самого журнала. В таком случае для восстановления БД нужна последняя версия логического журнала, последовательность архивов журналов и архивная копия БД.

Также архивные копии БД можно сжимать



  1. Можно сжимать отдельную копию, оставляя только последнее действие над каким-то кортежем. Например, если последнее действие – удаление, то остальные действия можно не хранить

  2. Можно аналогичным способом сжимать и последоватьельные архивные копии логического журнала.

Тоесть, для восстановления БД достаточно зранить архивную копию БД, сжатый архив журнала и последньь версию логического журнала.
<< предыдущая страница