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

Декомпозиция r = {R₁, R₂,..., R_S} схемы отношения R обладает свойством соединения без потерь информации относительно множества функциональных зависимостей F, справедливых на схеме, если каждый экземпляр схемы отношения R восстанавливается из соединения проекций этого экземпляра на каждую декомпозиционную подсхему из r [6].

Выполнимость этого свойства необходима для получения релевантных многотабличному запросу ответов, в которых участвуют атрибуты нескольких декомпозиционных подсхем по следующей причине. Если выполнена декомпозиция исходной схемы отношения R, то данные хранятся в базе данных не в виде экземпляров r(R), а в виде экземпляров декомпозиционных подсхем r(R_i). Для получения ответов на многотабличные запросы необходимо выполнять операцию соединения соответствующих экземпляров декомпозиционных подсхем.

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

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

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

В настоящее время известны два алгоритма проверки выполнимости свойства соединения без потерь информации [1], [3], [6]. Первый алгоритм используется для декомпозиции, состоящей из двух декомпозиционных подсхем, а второй алгоритм – для любого количества декомпозиционных подсхем. Поскольку второй алгоритм является универсальным с точки зрения количества декомпозиционных подсхем, здесь ограничимся его рассмотрением.

Пусть R = A₁,..., A_n - схема отношения, на которой определено множество F и r = {R₁, R₂,..., R_k} - декомпозиция R. Построим таблицу из n (количество атрибутов в схеме R) столбцов и k (количество декомпозиционных подсхем) строк так, чтобы j -й столбец соответствовал атрибуту A_j, A_j Î R, j = 1,2,..., n, а i - я строка - декомпозиционной подсхеме R_i, i = 1,2,..., k. Заполним таблицу следующим образом.

Поставим на пересечении i - й строки и j - го столбца символ “ a ”, если атрибут A_j Î R_i, и символ “ b_i ” - иначе. Заполнив таким образом таблицу, начинаем ее видоизменять по следующему правилу.

Циклически просматривая в любом порядке множество F от одной функциональной зависимости к другой, производим анализ каждой зависимости (X ® Y) Î F и вносим такие изменения в таблицу, чтобы рассматриваемая зависимость выполнялась. Для этого используем определение функциональной зависимости, сформулированное в разделе 1.3.1. Например, для зависимости X ® Y из F находим в таблице такие строки, которые совпадают по всем атрибутам (столбцам) набора X. По определению функциональной зависимости в найденных строках должны совпадать значения атрибутов набора Y. Если значение хотя бы одного атрибута из набора Y есть “ a ”, то делаем его равным “ a ”для Y во всех найденных строках. Если ни одно значение не равно “ a ”, то делаем его равным любому, но одинаковому, значению “ b_i ”. Аналогично осуществляем анализ остальных зависимостей. Процесс заканчиваем, когда в таблице невозможно будет сделать никаких изменений, или какая-либо строка таблицы не станет состоять сплошь из символов “ a ”. Наличие такой строки говорит о выполнимости свойства соединения без потерь информации для рассматриваемой декомпозиции, а отсутствие - о невыполнимости его. Доказательство корректности рассмотренного алгоритма дано в работе [1].

Пример 25 [6]. Пусть R = ABCDELPS и F = {B ® C, D ® EL, B ® PS, A ® CDPS, AP ® S}. Выясним, обладает ли декомпозиция r = {AB, ACDPS, BCPS, DEL} схемы отношения R свойством соединения без потерь информации? Для этого строим и заполняем, как было изложено выше, таблицу 1:

1) A B C D E L P S 2) A B C D E L P S

AB a a b₁ b₁ b₁ b₁ b₁ b₁ AB a a b₁ a b₁a b₁ b₁ b₁a b₁a

ACDPS a b₂ a a b₂ b₂ a a Þ ACDPS a b₂ a a b₂ a b₂ a a a

BCPS b₃ a a b₃ b₃ b₃ a a BCPS b₃ a a b₃ b₃ b₃ a a

DEL b₄ b₄ b₄ a a a b₄ b₄ DEL b₄ b₄ b₄ a a a b₄ b₄

Начинаем просмотр зависимостей из F. Для зависимости B ® C в исходной таблице 1 ищем строки, совпадающие по значению атрибута B. Это - первая и третья строки со значением “ a ”(подчеркнуты в таблице 1 и отмечены жирным шрифтом в таблице 2). Значит, по определению функциональной зависимости должны совпадать и значения в этих же строках и в столбце C. Так как в третьей строке это значение равно “ a ”, то делаем его равным “ a ” и в первой строке (также отмечены жирным шрифтом в таблице 2).

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

Рассмотрим вторую зависимость D ® EL из F. Поскольку правая часть зависимости содержит более одного атрибута, по правилу декомпозиции правой части зависимости (раздел 1.3.2) декомпозируем правую часть и для удобства анализа вместо одной зависимости 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 B C D E L P S

D ® EL. Одинаковые значения AB a a a a b₁ a b₁ a a a

в столбце D имеют первая, вто- ACDPS a b₂ a a a a a a

рая и четвертая строки. Вносим BCPS b₃ a a b₃ b₃ b₃ a a

соответствующие изменения сна- DEL b₄ b₄ b₄ a a a b₄ b₄

чала в столбец E, а затем в стол-

бец L.

Процесс заканчиваем, так как получили первую строку (подчеркнута) таблицы 3, состоящую сплошь из символов “ a ”. Следовательно, рассматриваемая декомпозиция обладает свойством соединения без потерь информации.

Пример 26 [6]. Пусть R = ABCDEKM и F = {A ® BC, A ® D, D ® EK, AD ® M, M ® AK}. Задана декомпозиция исходной схемы отношения в виде r = {ADME, EKC, ACE, DEB}. Проверим, обладает ли данная декомпозиция свойством соединения без потерь информации относительно F.

Строим таблицу 1, которую заполняем по правилу, изложенному в алгоритме. Для удобства работы будем в таблице отображать только символы “ a ”, а символы “ b_i ” будем подразумевать и отображать их в таблице только по необходимости.

1) A D B C E K M 2) A D B C E K M

ADME a a.. a. a a a b₁ a a b₁ a

EKC... a a a. Þ... a a a.

ACE a.. a a.. a a b₁ a a b₁ a

DEB. a a. a... a a. a b₁.

Анализируем первую зависимость A ® BC из F. Одинаковые значения в столбце A имеются в первой и третьей строках (символы “ a ” подчеркнуты и таблице 1). Следовательно, в этих же строках в столбцах B и C должны стоять одинаковые значения. А они разные. Делаем их одинаковыми. В столбце B ни в первой, ни в третьей строке нет символа “ a ”, поэтому делаем их равными, например “ b₁ ” (или “ b₃ ”, важно сделать их одинаковыми). В таблице 2 отображены эти изменения. Так как в столбце C в третьей строке стоит символ “ a ”, то ставим символ “ a ”и в первой строке этого столбца.

Анализируем вторую зависимость A ® D из F. В столбце A, как мы только что выяснили, одинаковые символы стоят в первой и третьей строке. Следовательно, и в столбце D в этих же строках должны стоять одинаковые значения, а они разные, как видно из таблицы 1. Делаем их одинаковыми. Так как в первой строке в столбце D стоит символ “ a ”, то ставим и в третьей строке в столбце D также символ “ a ”.

Анализируем третью зависимость D ® EK из F. Ищем одинаковые значения в столбце D. Поскольку в столбце уже были сделаны изменения, то теперь уже обращаемся к таблице 2. Одинаковые значения в столбце D содержатся в первой, третьей и четвертой строках. Поэтому делаем одинаковыми значения в этих же строках в столбцах E и K. В столбце E они уже одинаковые. Поэтому изменения коснутся только столбца K. Очевидно, это будут символы “ b_i ”, например “ b₁ ”.

Анализируем четвертую зависимость AD ® M из F. Опять обращаемся к таблице 2. Так как в левой части зависимости стоит набор из двух атрибутов, то ищем одинаковые пары значений в столбцах AD. Пара значений “ aa ” имеется в первой и третьей строках. Поэтому в этих строках в столбце M должны стоять одинаковые значения. Поскольку в первой строке в столбце стоит символ “ a ”, то ставим этот символ и в третьей строке столбца M. Из таблицы 2 видно, что последняя зависимость M ® AK из F уже выполняется.

Проверив еще раз выполнимость каждой зависимости из F, убеждаемся, что в таблице 2 никаких изменений больше сделать нельзя, и в то же время не получено строки, сплошь состоящей из символов “ a ”. Поэтому делаем вывод о том, что рассматриваемая декомпозиция не обладает свойством соединения без потерь информации относительно заданного множества функциональных зависимостей F.

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

Порядок просмотра зависимостей из F не влияет на результат, а определяет лишь скорость принятия решения.