Материал: Алгебра_кортежей
Глава 3. Методы снижения трудоемкости в АК
Того, кто не задумывается о далеких трудностях, непременно поджидают близкие неприятности.
Конфуций
При реализации алгоритмов на компьютере представление многоместных отношений как множеств элементарных кортежей зачастую приводит к повторению в памяти одних и тех же данных – компонент кортежей. При вычислениях это вызывает многократное дублирование действий.
Запись отношений в более "компактном" виде, а именно в виде АК-объектов, как показано в главе 2 (п. 2.1, пример к теореме 2.5), значительно сокращает вычислительные затраты на осуществление действий над отношениями. Кроме того, переход от элементарных кортежей к кортежам, компоненты которых – не отдельные элементы, а множества, позволяет обойтись меньшими объемами памяти при хранении данных и знаний.
Однако во многих случаях требуются дополнительные средства ускорения вычислительных процедур. Рассмотрим способы снижения трудоемкости операций над отношениями, применимые в алгебре кортежей.
Первый способ – ортогонализация – сводится к разбиению совокупности элементарных кортежей, формирующих некоторый АК-объект, на взаимно не пересекающиеся множества, что исключает дублирование одних и тех же элементарных кортежей в различных подструктурах АК-объекта. Помимо этого, ортогонализация операндов способствует уменьшению размерности результатов операций над ними.
Еще одна возможность сократить время производимых над отношениями операций состоит в использовании их матричных свойств. Исходное отношение, заданное в декартовом произведении D, предлагается разделять на блоки – отношения внутри проекций D – и обрабатывать каждый блок независимо друг от друга (распараллеливать операции), опираясь на известные
100
свойства декартовых произведений. Анализируя блоки, можно значительно снизить размерность исходной задачи, а в некоторых случаях – и ее вычислительную сложность.
Использование упомянутых методов позволяет применять алгебраический подход не только в системах управления БД, но и для систем БЗ, поскольку во многих случаях уменьшает трудоемкость алгоритмов, реализующих задачи логического анализа (например, задачи выполнимости КНФ).
3.1. Ортогонализация
Анализируя приведенные выше примеры C-систем, можно увидеть, что некоторые пары содержащихся в них C-кортежей имеют непустое пересечение. Иногда это сильно затрудняет расчеты. Например, возможны ситуации, когда требуется вычислить общее число элементарных кортежей, содержащихся в таких C-системах – приходится учитывать все возможные пересечения пар, троек и т.д. C-кортежей. Те же трудности возникают, если исследуются метрические свойства АК-объектов, например, их вероятностное представление. Ортогонализация как раз и предназначена для преодоления этих трудностей.
Кроме того, ортогонализация дает эффективные средства уменьшения трудоемкости алгоритмов преобразования АК-объектов в альтернативные классы и, в частности, D-систем в C-системы. Основная теорема ортогонализации была сформулирована и доказана русским логиком П.С. Порецким [Порецкий, 1887].
Рассмотрим основные соотношения ортогонализации, используемые в математической логике.
ДНФ называется ортогональной, если любая пара ее конъюнктов не имеет общих выполняющих подстановок. Ортогонализация есть преобразование, переводящее произвольную формулу в эквивалентную ей ортогональную ДНФ. В общем случае ортогональной также можно считать любую формулу вида
H1 H2 ... Hk, если для |
любой пары (Hi, Hj) ее подформул соблюдается |
|
Hi Hj = false |
при условии, |
что i j. Это равносильно пустоте пересечения |
АК-объектов, |
моделирующих формулы Hi, Hj. Оценка меры ортогональной |
|
формулы, если известна мера (Hi) каждой из ее подформул Hi, может быть
101
вычислена с помощью простого суммирования мер составных частей. Частный случай ортогональной функции – совершенная ДНФ (СДНФ), в
которой каждый конъюнкт содержит столько литералов, сколько переменных в данной формуле. В АК совершенной ДНФ соответствует C-система, где каждый C-кортеж содержит в качестве компонент только одноэлементные множества. В основе существующих методов ортогонализации лежит следующее соотношение, полученное П.С. Порецким для формул исчисления высказываний:
Дизъюнкция H1 H2 ... Hk эквивалентна ортогональной ДНФ вида
(H1) (H1 H2) ... (H1 H2 ... Hk 1 Hk).
Определение 3.1. C-система называется ортогональной, если пересечение любой пары содержащихся в ней различных C-кортежей равно пустому C- кортежу.
Ортогонализация диагональной C-системы (D-кортежа) не составляет особого труда и производится согласно теореме 3.1.
Теорема 3.1. D-кортеж вида ]Q1 Q2 ... Qm-1 Qm[, где Qi – произвольные компоненты, преобразуется в эквивалентную ему ортогональную C-систему:
Q |
|
... |
|
||
|
1 |
|
|
|
|
|
Q2 ... |
|
|||
Q1 |
|||||
|
... |
|
|||
|
|
|
|
|
|
|
Q2 ... |
Qm 1 |
|||
Q1 |
|||||
|
|
|
|
|
|
|
Q2 ... |
Qm 1 |
|||
Q1 |
|||||
. Qm
Доказательство. Результат следует из соотношения Порецкого и изоморфизма системы исчисления высказываний и АК, так как каждая компонента Qi в исходном D-кортеже при преобразовании в C-систему может
быть представлена только в двух вариантах (например, Q – истина и Qi – ложь), при этом никакие другие значащие (т.е. в данном случае не фиктивные) подмножества соответствующих доменов атрибутов при преобразовании не используются. Конец доказательства.
Рассмотрим пример. Пусть в схеме отношения [XYZ], где X = Y = Z = {a, b, c, d}, задан D-кортеж ]{a, c} {d} {b, d}[. Тогда по теореме 3.1 получим следующие равенства:
102
{a,c} |
|
|
|
|
]{a, c} {d} {b, d}[ = |
|
{d} |
|
= |
|
|
|
{b,d} |
|
|
|
|
|
|
{a,c} |
|
|
|
|
|
|
|
|
, |
{b,d} |
{d} |
|
||
{b,d} {a,b,c} |
{b,d} |
|
||
|
|
|
|
|
причем вторая C-система ортогональна.
Ортогонализация произвольных АК-объектов сводится к ортогонализации эквивалентных им D-систем (преобразованию D-систем в ортогональные С-системы). Для этого требуется: 1) выразить исходный АК-объект как D-систему, 2) представить D-систему как пересечение D-кортежей, 3) каждый D-кортеж преобразовать в ортогональную C-систему с использованием теоремы 3.1, 4) выполнить пересечение промежуточных ортогональных С-систем, опираясь на теорему 3.2.
Теорема 3.2. Если P и Q – ортогональные C-системы, то пересечение этих C-систем, вычисленное в соответствии с теоремой 2.5, либо пусто, либо состоит из одного C-кортежа, либо представляет собой ортогональную C-систему.
Доказательство. Каждую из исходных C-систем можно представить как некоторое множество элементарных кортежей. Пусть T(Pi), T(Qj) – множества всех элементарных кортежей, содержащихся в C-кортежах Pi из P и Qj из Q. Ясно, что системы множеств {T(Pi)} и {T(Qj)} есть разбиения, так как P и Q – ортогональные C-системы. Полученная при пересечении C-система будет содержать непустые C-кортежи, каждый из которых состоит из множества T(Pi) T(Qj) элементарных кортежей. Выберем два различных C-кортежа
результирующей C-системы, эквивалентные |
множествам T(Pk) T(Ql) и |
T(Pr) T(Qs) элементарных кортежей (то есть |
вариант когда одновременно |
k = r и l = s исключается, поскольку он означает дублирование одного и того же пересечения). Не нарушая общности, достаточно рассмотреть вариант k r (если k = r, то вместо него можно рассмотреть аналогичный вариант l s). Тогда равенство (T(Pk) T(Ql)) (T(Pr) T(Qs)) = следует из того, что T(Pk) T(Pr) = . В результате после выполнения всех операций пересечения C-кортежей возможны три варианта: 1) в итоговой С-системе не останется ни
одного непустого C-кортежа; 2) останется один |
непустой C-кортеж; |
|||
3) оставшиеся |
C-кортежи |
образуют ортогональную |
C-систему. |
Конец |
доказательства. |
|
|
|
|
Рассмотрим |
пример |
ортогонализации для приведенной в |
качестве |
|
|
|
103 |
|
|
{a,c} |
{d} {b,d} |
|
иллюстрации к теореме 2.20 D-системы P = |
{a,d} |
{a,c} , имеющей те |
{b,c} |
|
{b} |
|
|
|
же схему отношения и состав атрибутов, что и в предыдущем примере. Используя для каждого D-кортежа теорему 3.1, найдем
|
{a,c} |
|
|
|
|
{a,d} |
|
|
|
{b,c} |
|
|
|
|
|
|
|
|
|
||||||
P = |
{b,d} |
{d} |
|
|
|
|
|
|
. |
|||
|
{b,d} {a,b,c} |
{b,d} |
|
{b,c} |
{a,c} |
|
{a,d} |
{b} |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Вычислим промежуточные результаты (пустые C-кортежи не показаны):
{a,c} |
|
|
|
{b,d} |
{d} |
|
|
|
|
|
|
{b,d} {a,b,c} |
{b,d} |
||
|
|
|
|
|
{a,d} |
|
|
= |
|
|
|
||
|
{b,c} |
{a,c} |
|
|
{a,c} {a,d} |
|
|
|
|
|
{a,c} {b,c} |
{a,c} |
|
{b,d} {d} |
|
. |
|
|
|
{b,d} {a} |
{b,d} |
|
|
|
|
|
|
|
|
|
{c} |
|
|
|
|
|
|
|
|
|
|
|
{a,c} {a,d} |
|
|
|
|
|
|
|
{a} |
|
{a,c} {b,c} |
{a,c} |
|
{b,c} |
|
|
|
{c} |
||
|
|
|
|||||||
|
|
|
|
|
|
|
= |
{b} |
|
{b,d} {d} |
|
|
|
||||||
|
{a,d} |
{b} |
|
|
|||||
|
|
|
|
|
|
|
|
{d} |
|
{b,d} {a} |
{b,d} |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
{b} |
|
{d}
{a,d} |
|
|
{a,d} |
{b} |
|
|
||
{b,c} {a,c} |
||
{d} |
|
|
. |
||
{d} |
{b} |
|
|
|
|
{a} |
{b,d} |
|
{a} |
{b} |
|
|
||
Получен результат, который по размерности незначительно улучшил результат, вычисленный без ортогонализации – матрица C-системы сократилась лишь на одну строку. Ниже мы рассмотрим некоторые другие методы сокращения размерности и трудоемкости вычислений при выполнении этой операции. Но само по себе получение ортогональной C-системы дает и другие преимущества. Например, можно легко вычислить количество элементарных кортежей, содержащихся в исходной D-системе. Для этого достаточно подсчитать их число в каждом C-кортеже и просто сложить их. Этого нельзя было сделать без ортогонализации, так как в C-системе имелись пары C-кортежей с непустым пересечением. Так, для данного примера, если учитывать, что мера каждой фиктивной компоненты равна 4, имеем: 8 + 2 + 4 + 4 + 1 + 2 + 1 = 22. Кроме того, если заданы вероятностные меры компонент, то вероятность всей системы вычисляется суммированием всех
104