Декомпозиция схем отношений. Свойство соединения без потерь информации

Лекция 23.04 и 24.04.2020 1.1. Декомпозиция схем отношений 1.1.1. Понятие декомпозиции Декомпозицией схемы отношения R = A1, ..., Ak называется замена ее совокупностью  = {R1, R2, ..., RS} возможно пересекающихся подмножеств Rj  R, j = 1, 2, ... , S, таких что R1  R2  ...  RS = R. Каждое множество Rj   называется декомпозиционной подсхемой. Декомпозиция - важная операция разбиения схемы отношения на множество декомпозиционных подсхем, которая может использоваться для исключения некоторых недостатков, присущих исходной одной схеме отношения. Отметим основные недостатки [см. ссылку в пособии] отношения PPD. Итак, имеем отношение: 1. Потенциальная избыточность. Если на множестве атрибутов схемы отношения R справедлива зависимость X Y, то по определению функциональной зависимости все кортежи отношения, совпадающие по значениям атрибутов из набора X, должны совпадать и по значениям атрибутов из набора Y. Например, в отношении PPD если номер поставщика PN = “p1”, то значение атрибута PIM должно быть всегда “Иванов”, поскольку справедлива зависимость PN  PIM. Таким образом, если поставщик “p1” поставляет более одного вида деталей, то его имя будет повторено много раз. 2. Потенциальная противоречивость. Изменение в одном из кортежей значений атрибутов из набора X  Y при наличии функциональной зависимости X  Y может привести к нарушению этой зависимости в других кортежах отношения. Например, изменение в кортеже k1 значений атрибутов из набора PN  PIM (номер поставщика изменим на “p3” или имя поставщика изменим на “Сидоров”) может привести к нарушению зависимости PN  PIM в кортеже k2 (если изменили значение PIM) или в кортеже k5 (если изменили значение PN). 3. Аномалии включения. Если на множестве атрибутов X0, X1, X2,Y в отношении R справедливы зависимости ( X0  X1 )  Y и (X0  X2)  Y, то при добавлении или изменении значений атрибутов из набора X0, X1, Y или X0, X2, Y возникают проблемы проверки непротиворечивости данных по наборам X0, X1, Y или X0, X2, Y соответственно. Эта же проблема возникает, если на момент включения новых данных по набору X0, X1, Y значения X2 не определены или - по набору X0, X2, Y значения X1 не определены. Так в отношение PPD нельзя включить кортеж о новом поставщике, пока он не начнет поставлять какую-либо деталь. 4. Аномалии удаления. Если на множестве атрибутов справедливы зависимости X  Y и Y  Z, т.е. имеется транзитивная зависимость X  Z, то при удалении из отношения кортежей со значением, например “y0”, атрибута Y может возникнуть проблема сохранения соответствия значений “x0” и “z0” атрибутов X и Z в зависимости X  Z. Например, в отношении PPD справедливы зависимости PN  GOR и GOR  ST, т.е. имеется транзитивная зависимость PN  ST. При удалении из отношения двух кортежей k2 и k4 зависимость PN  ST может быть потеряна. В таком случае нужны специальные средства поддержания всех существующих зависимостей, что вызывает определенные трудности. Замена исходной схемы отношения R множеством  декомпозиционных подсхем позволяет исключить перечисленные выше недостатки исходной одной схемы отношения. 1.1.2. Свойства декомпозиции Однако не всякую декомпозицию можно использовать. Любая декомпозиция схемы отношения должна обладать двумя свойствами: • соединением без потерь информации относительно заданного множества функциональных зависимостей F; • сохранением исходного множества функциональных зависимостей на заданном множестве атрибутов U. 1.1.2.1. Свойство соединения без потерь информации Декомпозиция  = {R1, R2, . . . , RS} схемы отношения R обладает свойством соединения без потерь информации относительно множества функциональных зависимостей F, справедливых на схеме, если каждый экземпляр схемы отношения R восстанавливается из соединения проекций этого экземпляра на каждую декомпозиционную подсхему из  [см. ссылку в пособии]. Выполнимость этого свойства необходима для получения релевантных многотабличному запросу ответов, в которых участвуют атрибуты нескольких декомпозиционных подсхем по следующей причине. Если выполнена декомпозиция исходной схемы отношения R, то данные хранятся в базе данных не в виде экземпляров r(R), а в виде экземпляров декомпозиционных подсхем r(Ri). Для получения ответов на многотабличные запросы необходимо выполнять операцию соединения соответствующих экземпляров декомпозиционных подсхем. Невыполнимость свойства соединения без потерь информации всегда приводит на каком-то экземпляре отношения к наличию лишних кортежей в ответе на запрос, причем на каком экземпляре отношения это произойдет, сказать заранее нельзя. К каким последствиям это может привести? Если база данных проектируется для систем бизнеса, то это может привести только к материальным потерям, например, некоторые сотрудники получат лишнее вознаграждение или кто-то получит уведомление из налоговой инспекции о необходимости уплаты налогов, хотя налоги уже уплачены или данный клиент вообще не подлежит налогообложению. Если же база данных проектируется для систем управления, то невыполнимость свойства соединения без потерь информации может привести к катастрофическим последствиям, причем, когда это произойдет, заранее предсказать невозможно. Проверка выполнимости свойства соединения без потерь информации на каждом экземпляре схемы отношения - дело практически безнадежное. В настоящее время известны простые алгоритмы проверки выполнимости этого свойства для любого заданного набора декомпозиционных подсхем. В настоящее время известны два алгоритма проверки выполнимости свойства соединения без потерь информации [см. ссылки в пособии]. Первый алгоритм используется для декомпозиции, состоящей из двух декомпозиционных подсхем, а второй алгоритм – для любого количества декомпозиционных подсхем. Поскольку второй алгоритм является универсальным с точки зрения количества декомпозиционных подсхем, здесь ограничимся его рассмотрением. Пусть R = A1, . . . , An - схема отношения, на которой определено множество F и  = {R1, R2, . . . , Rk} - декомпозиция R. Построим таблицу из n (количество атрибутов в схеме R) столбцов и k (количество декомпозиционных подсхем) строк так, чтобы j-й столбец соответствовал атрибуту Aj , Aj  R, j = 1,2, . . . , n, а i - я строка - декомпозиционной подсхеме Ri, i = 1,2, . . . , k. Заполним таблицу следующим образом. Поставим на пересечении i - й строки и j - го столбца символ “a”, если атрибут Aj  Ri , и символ “bi” - иначе. Заполнив таким образом таблицу, начинаем ее видоизменять по следующему правилу. Циклически просматривая в любом порядке множество F от одной функциональной зависимости к другой, производим анализ каждой зависимости (X  Y)  F и вносим такие изменения в таблицу, чтобы рассматриваемая зависимость выполнялась. Для этого используем определение функциональной зависимости (см. пособие, раздел 1.3.1) Например, для зависимости X  Y из F находим в таблице такие строки, которые совпадают по всем атрибутам (столбцам) набора X. По определению функциональной зависимости в найденных строках должны совпадать значения атрибутов набора Y. Если значение хотя бы одного атрибута из набора Y есть “a” , то делаем его равным “a” для Y во всех найденных строках. Если ни одно значение не равно “a” , то делаем его равным любому, но одинаковому, значению “bi”. Аналогично осуществляем анализ остальных зависимостей. Процесс заканчиваем, когда в таблице невозможно будет сделать никаких изменений, или какая-либо строка таблицы не станет состоять сплошь из символов “a”. Наличие такой строки говорит о выполнимости свойства соединения без потерь информации для рассматриваемой декомпозиции, а отсутствие - о невыполнимости его. Доказательство корректности рассмотренного алгоритма дано в работе [см. ссылку в пособии]. Пример 1. Пусть R = ABCDELPS и F = {B  C, D  EL, B  PS, A  CDPS, AP  S}. Выясним, обладает ли декомпозиция  = {AB, ACDPS, BCPS, DEL} схемы отношения R свойством соединения без потерь информации? Для этого строим и заполняем, как было изложено выше, таблицу 1: Начинаем первый цикл просмотра зависимостей из F. Для зависимости B  C в исходной таблице 1 ищем строки, совпадающие по значению атрибута B. Это - первая и третья строки со значением “a” (подчеркнуты в таблице 1 и отмечены жирным шрифтом в таблице 2). Значит, по определению функциональной зависимости должны совпадать и значения в этих же строках и в столбце C. Так как в третьей строке это значение равно “a”, то делаем его равным “a” и в первой строке (также отмечены жирным шрифтом в таблице 2). Отметим, что для зависимостей, правые части которых содержат более одного атрибута, рекомендуется выполнить сначала декомпозицию правых частей, а затем уже производить соответствующие изменения в таблице. Рассмотрим вторую зависимость D  EL из F. Поскольку правая часть зависимости содержит более одного атрибута, по правилу декомпозиции правой части зависимости декомпозируем правую часть и для удобства анализа вместо одной зависимости D  EL рассматриваем две: D  E и D  L. В таблице 1 ищем в столбце D одинаковые значения. Это – символы “a” во второй и четвертых строках (подчеркнуты в таблице 1 и отмечены жирным шрифтом в таблице 2). Значит, по определению функциональной зависимости должны совпадать и значения в этих же строках и в столбцах E и L. А они разные, но в четвертой строке в столбцах E и L есть символ “a”. Поэтому делаем его равным “a” и во второй строке этих столбцов (также отмечены жирным шрифтом в таблице 2). Аналогичные изменения делаем в таблице 2 для остальных зависимостей. Эти изменения отображены в таблице 2. Таблица 2 соответствует первому циклу просмотра всех зависимостей из F. Видно, что в таблице нет строки, содержащей только символы “a”. Проверим, возможно ли и дальше видоизменять таблицу. Для удобства дальнейших преобразований скопируем результат первого цикла просмотра зависимостей в таблицу 3. Обратимся к таблице 3 и начнем второй цикл просмотра зависимостей из множества F, начиная опять с первой зависимости B  C. Для этой зависимости изменений в таблице не будет. Процесс заканчиваем, так как получили первую строку (подчеркнута) таблицы 3, состоящую сплошь из символов “a”. Следовательно, рассматриваемая декомпозиция обладает свойством соединения без потерь информации. Пример 2. Пусть R = ABCDEKM и F = {A  BC, A  D, D  EK, AD  M, M  AK}. Задана декомпозиция исходной схемы отношения в виде  = {ADME, EKC, ACE, DEB}. Проверим, обладает ли данная декомпозиция свойством соединения без потерь информации относительно F. Строим таблицу 1, которую заполняем по правилу, изложенному в алгоритме. Для удобства работы будем в таблице отображать только символы “a”, а символы “bi” будем подразумевать и отображать их в таблице только по необходимости. Анализируем первую зависимость A  BC из F. Одинаковые значения в столбце A имеются в первой и третьей строках (символы “a” подчеркнуты и таблице 1). Следовательно, в этих же строках в столбцах B и C должны стоять одинаковые значения. А они разные. Делаем их одинаковыми. В столбце B ни в первой, ни в третьей строке нет символа “a”, поэтому делаем их равными, например “b1” (или “b3”, важно сделать их одинаковыми). В таблице 2 отображены эти изменения. Так как в столбце C в третьей строке стоит символ “a”, то ставим символ “a” и в первой строке этого столбца. Анализируем вторую зависимость A  D из F. В столбце A, как мы только что выяснили, одинаковые символы стоят в первой и третьей строке. Следовательно, и в столбце D в этих же строках должны стоять одинаковые значения, а они разные, как видно из таблицы 1. Делаем их одинаковыми. Так как в первой строке в столбце D стоит символ “a”, то ставим и в третьей строке в столбце D также символ “a”. Анализируем третью зависимость D  EK из F. Ищем одинаковые значения в столбце D. Поскольку в столбце уже были сделаны изменения, то теперь уже обращаемся к таблице 2. Одинаковые значения в столбце D содержатся в первой, третьей и четвертой строках. Поэтому делаем одинаковыми значения в этих же строках в столбцах E и K. В столбце E они уже одинаковые. Поэтому изменения коснутся только столбца K. Очевидно, это будут символы “bi”, например “b1”. Анализируем четвертую зависимость AD  M из F. Опять обращаемся к таблице 2. Так как в левой части зависимости стоит набор из двух атрибутов, то ищем одинаковые пары значений в столбцах AD. Пара значений “aa” имеется в первой и третьей строках. Поэтому в этих строках в столбце M должны стоять одинаковые значения. Поскольку в первой строке в столбце стоит символ “a”, то ставим этот символ и в третьей строке столбца M. Из таблицы 2 видно, что последняя зависимость M  AK из F уже выполняется. Проверив еще раз выполнимость каждой зависимости из F, убеждаемся, что в таблице 2 никаких изменений больше сделать нельзя, и в то же время не получено строки, сплошь состоящей из символов “a”. Поэтому делаем вывод о том, что рассматриваемая декомпозиция не обладает свойством соединения без потерь информации относительно заданного множества функциональных зависимостей F. Очевидно, описанный алгоритм можно использовать и для анализа декомпозиции, состоящей из двух декомпозиционных подсхем. К достоинствам алгоритма следует отнести легкость его автоматизации. Порядок просмотра зависимостей из F не влияет на результат, а определяет лишь скорость принятия решения. Мейер показал [ссылка в пособии], что, если некоторая подсхема R схемы базы данных содержит универсальный ключ (или суперключ, не обязательно минимальный), то результирующая декомпозиция в подавляющем большинстве случаев будет обладать свойством соединения без потерь информации относительно заданного множества F-зависимостей, и обратно. Таким образом, выполнимость свойства соединения без потерь информации обеспечивается добавлением к декомпозиционному множеству подсхем лишней подсхемы, содержащей, как правило, универсальный ключ. Однако наличие суперключа является необходимым, но недостаточным условием, то есть наличие суперключа в какой-либо декомпозиционной подсхеме не гарантирует во всех случаях выполнимости свойства соединения без потерь информации. Этот факт подтверждает пример 37 в пособии. Поэтому рекомендуется всегда проводить дополнительное исследование результирующей декомпозиции на выполнимость свойства соединения без потерь информации. 1.1.2.2. Свойство сохранения функциональных зависимостей Свойство декомпозиции сохранять зависимости из исходного множества F состоит в том, что при восстановлении схемы отношения R из декомпозиционных подсхем все зависимости, объявленные в F, должны автоматически выполняться и в восстановленной схеме R. Определим это свойство формально. Проекцией множества функциональных зависимостей F на множество атрибутов Z  U, обозначаемое как Z (F), называется такое множество зависимостей (X  Y)  F, для которых XY  Z. Например, для U = ABC и F = {A  B, B  C} проекция AB (F) = {A  B}, а AС(F) = {A  С}. Легко видеть, что зависимость (A  C)  F, но следует из F по аксиоме транзитивности из зависимостей A  B и B  C. Следовательно, (A  C)  F. Декомпозиция  = {R1, R2, . . ., Rk} схемы отношения R сохраняет множество функциональных зависимостей F, определенное на R, если из объединения всех зависимостей, принадлежащих проекциям F на декомпозиционные подсхемы Ri, i = 1,2, . . . , k, логически следуют все зависимости из F. Тогда Пример. Пусть R = ABC и F = {A  B, B  C}. Случай 1. Декомпозиция  = {AB, BC} схемы отношения R сохраняет зависимости из F, так как F1 = AB (F) = {A  B}, F2 = BC (F) = {B  C} и (F1 F2) = {A  B, B  C} = F, а, следовательно, и {A  B, B  C} = F. Случай 2. Декомпозиция 1 = {AB, AC} не сохраняет зависимостей из F, так как F1 = AB (F) = {A  B}, F2 = AС (F) = {A  C}. Зависимость A  C выводится из исходного множества F по аксиоме транзитивности. Тогда (F1 F2) = {A  B, A  C} ≠ F. Зависимость B  C не восстанавливается из объединения проекций. Из приведенного примера с очевидностью вытекает условие достаточности того, в каком случае декомпозиция наверняка обладает свойством сохранения функциональных зависимостей на заданном множестве атрибутов, которое можно сформулировать следующим образом. Достаточное условие сохранения декомпозицией функциональных зависимостей состоит в том, чтобы все атрибуты каждой зависимости из F целиком входили в какую-нибудь декомпозиционную подсхему (как в случае 1). Тогда каждая зависимость из F наверняка окажется в проекции F на какую-нибудь декомпозиционную подсхему, а раз так, то все зависимости из F обязательно восстановятся из объединения проекций. Однако это условие не является необходимым, т.е. условие достаточности может быть не выполнено, а декомпозиция при этом сохраняет зависимости. Например, для R = ABC и F = {A  B, B  A, A  C} декомпозиция  = {AB, BC} сохраняет зависимости из F , несмотря на то, что условие достаточности не выполнено. Атрибуты AC зависимости A  C целиком не входят ни в одну декомпозиционную подсхему, но F1 = AB (F) = {A  B, B  A}, F2 = BС (F) = {B  C} и F1 F2 = {A  B, B  A, B  C}. Зависимость A  C транзитивно выводится из зависимостей A  B и B  C. Поэтому (F1 F2) = F. Будем в дальнейшем называть применимыми к некоторой декомпозиционной подсхеме те функциональные зависимости, все атрибуты которых целиком находятся среди атрибутов декомпозиционной подсхемы. Например, зависимость A  B будет применима к декомпозиционным подсхемам AB, ABC, ABCD, DAHRB и так далее. Иногда, если условие достаточности не выполняется, построение проекций множества функциональных зависимостей F на декомпозиционные подсхемы вызывает те же трудности, что и вычисление замыкания F. Чтобы их избежать, можно воспользоваться, по крайней мере, двумя способами: • Способ 1 использует алгоритм синтеза множества зависимостей, входящих в проекции Ri (F), где i = 1,2, . . . ,k. • Способ 2 основан на простых рассуждениях, использующих понятия расширенного множества зависимостей и условия достаточности. Способ 1 подробно изложен в работах[см. ссылки в пособии]. Способ 2, по мнению авторов, проще. Поэтому ограничимся рассмотрением именно этого способа. Пример 1. Пусть R = ABCDEM и F = {A  B, CD  A, CB  D, AE  M, CE  D}. Рассмотрим декомпозицию  = {R1, R2} , где R1 = AEM и R2 = ABCDE. На основе простых рассуждений выясним, обладает ли заданная декомпозиция  свойством сохранения функциональных зависимостей на заданном множестве атрибутов U = ABCDEM. Попробуем получить ответ на этот вопрос, используя только свойство достаточности. Строим таблицу из двух столбцов. В один столбец будем записывать функциональные зависимости из F, которые точно восстанавливаются из объединения проекций по условию достаточности, а в другой – остальные, которые необходимо дополнительно исследовать. Очевидно, точно восстанавливаются те зависимости, которые по условию достаточности применимы к какой-либо декомпозиционной подсхеме: Из таблицы видно, что все зависимости из исходного множества F восстанавливаются. Поэтому заданная декомпозиция обладает свойством сохранения функциональных зависимостей на заданном множестве атрибутов. Если в столбце “Остальные” останутся зависимости, то они требуют дополнительного исследования. Какого? Рассмотрим примеры. Пример 2. Пусть R = ABCDEKX и F = {A  BC, A  D, C  B, D  EK, AD  X, X  AK, E  K, A  K}. Рассмотрим декомпозицию  = {ADEX, EKC, ACEK, DEBC} схемы R. Пытаемся ограничиться только свойством достаточности. Строим таблицу: Теперь попытаемся вывести остальные зависимости из тех зависимостей, которые восстанавливаются. Так, зависимость A  B выводится транзитивно из зависимостей A  C и C  B, зависимость D  K аналогично выводится из зависимостей D  E и E  K, зависимость X  K – из зависимостей X  A и A  K. Таким образом, все зависимости из F восстанавливаются и свойство сохранения функциональных зависимостей для заданной декомпозиции выполняется. Однако так просто бывает не всегда. Иногда свойство достаточности дает отрицательный результат, а на самом деле свойство сохранения зависимостей выполняется. В этом случае предлагается получить дополнительные, выводимые из F зависимости, которые дадут возможность опять воспользоваться свойством достаточности. Эти дополнительные зависимости можно получить из расширенного множества F- зависимостей. Пример 3. Пусть R = ABC и F = {A  B, B  A, A  C}. Рассмотрим декомпозицию  = {AB, BC} схемы R. Воспользуемся только что предложенной процедурой. Для этого строим таблицу: Из таблицы видно, что зависимость A  C неприменима ни к подсхеме AB, ни к подсхеме BC. Поэтому она требует дополнительного исследования, которое может заключаться в следующем. Из левого столбца таблицы видно, что A функционально определяет B. Попробуем найти дополнительную зависимость, в которой B может функционально определять C (поскольку C является правой частью исследуемой зависимости)? Для этого строим расширенное множество F- зависимостей: ℱ = {A  BC, B  AC, A  CB}. Поскольку расширенное множество содержат все F-зависимости и выводимые из F зависимости, то в качестве дополнительной зависимости можно использовать B  C, которая получается из зависимости B  AC по правилу декомпозиции ее правой части и которая применима к декомпозиционной подсхеме BC. Добавляем полученную дополнительную зависимость в таблицу: Теперь зависимость A  C транзитивно выводится из зависимостей A  B и B  C, поэтому свойство сохранения зависимостей для рассматриваемой декомпозиции выполняется. Пример 4. Пусть R = ABCDEKMNLX и F = {A  CD, C  KML, A  BD, D  XNC, X  D, K  L, LB  E}. Рассмотрим декомпозицию  = {ABCDE, DX, XE, CKMNL, KM}. Выясним, обладает ли заданная декомпозиция  свойством сохранения функциональных зависимостей на заданном множестве атрибутов U = ABCDEKMNLX. Строим таблицу: Две зависимости в столбце “Остальные” требуют дополнительного исследования. Используя аксиомы и правила вывода функциональных зависимостей (см пособие раздел 1.3.2), а также факт выводимости зависимости (теорема 1 из раздела 1.4 пособия), нетрудно выяснить, что зависимости D  N и LB  E не выводятся из восстанавливаемых зависимостей. Попробуем воспользоваться расширенным множеством зависимостей. ℱ = {A  CDKMLBXNE, C  KML, A  CDKMLBXNE, D  XNCKML, X  DNCKML, K  L, LB  E}. Исследуя множество ℱ, приходим к выводу об отсутствии нужной дополнительной зависимости, которая позволила бы вывести зависимость LB  E. А, если такая зависимость и нашлась бы, то она была бы неприменима ни к одной декомпозиционной подсхеме. Таким образом, делаем вывод о невыполнимости свойства сохранения функциональных зависимостей для заданной декомпозиции. Декомпозиция может обладать или не обладать обоими свойствами, а также может обладать одним из них и не обладать другим.