Материал: Алгебра_кортежей

Теорема 2.9. Для произвольного D-кортежа P = ]P1 P2 … Pn[ его

дополнение равно C-кортежу P = [P1 P2 … Pn ].

Теорема 2.10. Дополнение D-системы есть C-система той же размерности,

вкоторой каждая компонента равна дополнению соответствующей компоненты

висходной D-системе.

Обобщая теоремы 2.7-2.10, можно сказать, что дополнение произвольного АК-объекта P эквивалентно АК-объекту Q альтернативного класса и той же размерности, в котором каждая компонента Qij равна дополнению соответствующей компоненты Pij в P.

Имеется исключение, когда дополнение может быть непосредственно выражено АК-объектом того же класса. Если C-кортеж или D-кортеж имеют только одну нефиктивную компоненту, то для вычисления дополнения достаточно в исходной структуре заменить нефиктивную компоненту на ее

возможно лишь в двух случаях:

(i)P Q или Q P;

(ii)Pi = Qi для всех соответствующих пар компонент, за исключением одной пары.

Доказательство. Пусть D = ]P1 Q1 P2 Q2 … Pn Qn[ . По закону контрапозиции утверждение теоремы справедливо тогда и только тогда, когда

равенство возможно лишь в двух случаях: (i) Pi Qi или Qi Pi ; (ii) Pi = Qi для всех соответствующих пар компонент за исключением одной пары. Снова используя закон контрапозиции, условия (i) и (ii) можно записать в более привычном виде, а именно так, как в формулировке теоремы. Конец доказательства.

В соответствии с определением 2.7 всегда справедливо равенство

80

Теорема 2.12. P Q, если и только если Pi Qi для всех i = 1, 2, …, n. Доказательство. Рассмотрим дополнения операндов:

предложения. Конец доказательства.

Теорема 2.13. P Q = ]P1 Q1 P2 Q2 … Pn Qn[.

Доказательство этой теоремы очевидно, если вспомнить, что D-кортежи P и Q – это диагональные C-системы. Если итоговый D-кортеж содержит хотя бы одну компоненту, равную домену соответствующего атрибута, то результат равен частному универсуму.

Теорема 2.14. Пересечение двух однотипных D-систем равно D-системе, содержащей все D-кортежи операндов.

Теорема 2.15. Объединение D-систем P и Q эквивалентно D-системе, состоящей из всех не равных универсуму D-кортежей, образующихся при выполнении операций объединения каждого D-кортежа из P с каждым D-кортежем из Q.

Нетрудно видеть, что соотношения между C-объектами (C-кортежи и C-системы) и D-объектами (D-кортежи и D-системы) соответствуют законам двойственности де Моргана. В силу этого они названы альтернативными классами.

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

81

основе следующих теорем также можно построить полиномиальные алгоритмы.

Теорема 2.16. Для C-кортежа P = [P1 P2 … Pn] и D-кортежа Q = ]Q1 Q2 … Qn[ справедливо P Q, если и только если по крайней мере для одного i соблюдается Pi Qi.

Доказательство. Каждый D-кортеж эквивалентен C-системе, содержащей n C-кортежей, каждый из которых состоит из всех полных компонент, за исключением Qi. Следовательно (учитывая, что C-система есть объединение C- кортежей), для того, чтобы соблюдалось P Q, необходимо выполнение Pi Qi по крайней мере для одного i. Действительно, если один из C-кортежей преобразованного в C-систему D-кортежа Q равен [ ... Qi ... ] и Pi Qi, то P [ ... Qi ... ] и, следовательно, P Q. Докажем достаточность. Предположим, что условие Pi Qi не соблюдается для всех i. Докажем, что в таком случае P Q невозможно. Из предположения следует, что для каждого i

доказательства.

Теорема 2.17. Для C-кортежа (или D-кортежа) P и D-системы Q справедливо P Q, если и только если для каждого D-кортежа Qj из Q выполняется P Qj.

Доказательство. Утверждение следует из того, что D-система есть пересечение множеств элементарных кортежей, содержащихся в D-кортежах, входящих в ее состав. Поскольку P включено в каждый D-кортеж, то оно включено также в их пересечение и, следовательно, в D-систему. Конец доказательства.

Следующее утверждение в силу его тривиальности приводится без доказательства.

Теорема 2.18. Для C-системы P и D-системы Q справедливо P Q, если и только если каждый C-кортеж из P включен в каждый D-кортеж из Q.

Далее рассмотрим алгоритмы, регламентирующие упомянутые преобразования АК-объектов.

82

2.2. Преобразования АК-объектов в альтернативные классы

Приведенные выше операции и алгоритмы проверки включения определены не для всех возможных сочетаний классов АК-объектов. В частности, не приведены алгоритмы пересечения D-системы и C-системы. Кроме того, пока что не предусмотрены алгоритмы проверки включения АК-объектов P Q, когда P – D-система или Q – C-система. Следовательно, необходимо предложить алгоритмы преобразования АК-объектов в альтернативные классы. Эти алгоритмы, в общем случае, не полиномиальны по вычислительной сложности.

Теорема 2.19. Каждый C-кортеж (D-кортеж) P преобразуется в эквивалентную ему диагональную D-систему (C-систему).

Диагональная D-система (по аналогии с диагональной C-системой) есть выраженная матрицей размерности n n D-система, у которой все недиагональные компоненты равны фиктивной компоненте “ ”.

Например, D-кортеж ]A B C[, где A, B, C – непустые компоненты,

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

Теорема 2.20. D-система P, содержащая m D-кортежей, эквивалентна C-системе, которая равна пересечению m C-систем, полученных с помощью преобразования каждого D-кортежа из P в C-систему.

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

83