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

Аналогично следует поступить с вновь полученным разложением. Следовательно, непустота хотя бы одного из столбцов D-системы

свидетельствует о непустоте всей системы.

Теорема 3.3 непосредственно пригодна для решения практических задач, но чаще применяются ее следствия, для рассмотрения которых введем некоторые обозначения и теоремы.

Конфликтующая пара D-системы есть непересекающаяся пара непустых компонент в одном атрибуте.

Конфликтный атрибут D-системы – это атрибут, в котором пересечение всех непустых компонент пусто, в противном случае атрибут называется

бесконфликтным.

Бесконфликтный блок D-системы (BlNC) – ее вертикальный блок, содержащий только бесконфликтные атрибуты. Соответственно вертикальный блок с конфликтными атрибутами называется конфликтным блоком (BlC). Из определений ясно, что в бесконфликтном блоке могут содержаться пустые компоненты, но в то же время пересечение всех непустых компонент в каждом атрибуте этого блока непусто.

Монотонным атрибутом D-системы является бесконфликтный атрибут, не содержащий пустых компонент.

Монотонным блоком D-системы (BlM) называется бесконфликтный блок, не содержащий D-кортежей со всеми пустыми компонентами.

Для D-системы Q, содержащей монотонный блок BlM(Q), построим C-кортеж Cint, в котором все компоненты проекции монотонного блока равны пересечению всех непустых компонент исходной D-системы Q в соответствующем атрибуте, а все остальные компоненты – фиктивные, т.е. равны " ".

Теорема 3.4. Если D-система Q содержит монотонный блок, то она непуста и Cint Q.

Доказательство. По условиям теоремы Cint , и для каждого D-кортежа Qi системы Q по теореме 2.16 соблюдается Cint Qi, так как в монотонном блоке всегда существует непустая компонента, такая что соответствующая компонента Cint включена в нее. Отсюда в силу теоремы 2.17 получаем Cint Q.

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

В качестве примера возьмем D-систему

110

Нетрудно убедиться, что первый и третий атрибуты в T бесконфликтны и вместе образуют монотонный блок. Соответственно Cint = [{A} {c}]. Из теоремы 1.2 следует, что T – непуста и Cint T, это легко проверяется с помощью теорем 2.16 и 2.17.

Рассмотрим теперь D-системы с бесконфликтными блоками, которые содержат D-кортежи со всеми пустыми компонентами. Пусть D-система Q содержит бесконфликтный блок T1 = BlNC(Q). Тогда после соответствующих перестановок строк и столбцов D-систему Q можно изобразить как блочную

всеми пустыми компонентами и являющаяся монотонным блоком, T21 – подматрица Q с D-кортежами, содержащими только пустые компоненты.

Теорема 3.5. Если в D-системе Q имеется бесконфликтный блок, то Q непуста, если и только если при разложении ее в блочную матрицу T непуста D-система, представленная блоком T22.

Доказательство. Необходимость. Ясно, что одна из D-систем в формуле

T11

(3.2) из теоремы 3.3 может быть представлена блочной матрицей T22 .

Поскольку T11 монотонна, то существует непустой C-кортеж C11, такой что C11 T11. Если T22 непуста, то в проекции, соответствующей T22, имеется C-кортеж C22, такой что C22 T22. При пересечении C11 и C22 образуется непустой C-кортеж C0, так как всем нефиктивным компонентам кортежа C11 соответствуют фиктивные компоненты кортежа C22, и наоборот. Согласно теоремам 2.16 и 2.17 C0 T. Достаточность. Предположим, что T22 пуста, а Q непуста. Тогда T22 эквивалентна D-системе той же размерности, все компоненты которой – пустые множества. Если вместо T22 вставить эту D-систему, то нижняя часть блочной матрицы будет содержать D-кортежи со всеми пустыми компонентами и, следовательно, соответствующая ей D-система окажется пустой. Конец доказательства.

Приведем пример. Дана D-система

111

Первый и третий столбцы в ней – бесконфликтные. Следовательно, после соответствующей перестановки столбцов и строк Q можно преобразовать в эквивалентную ей блочную матрицу:

следовательно, она непуста и содержит C-кортеж C22 = [{h} ]. Монотонный блок T11 содержит C-кортеж [{A} {b}]. Пересечение этих C-кортежей после приведения к одной схеме отношения равно C-кортежу C0 = [{A} {b} {h} ], он при перестановке атрибутов в соответствии со схемой отношения исходной D-системы Q преобразуется в C-кортеж [{A} {h} {b} ], который и является выполняющей подстановкой D-системы Q. Проверить правильность этой подстановки можно с помощью теорем 2.16 и 2.17.

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

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

112

частности, матричные свойства АК-объектов активно используются в алгоритмах решения задач проверки выполнимости КНФ и включения АКобъектов, например С-кортежа в С-систему.

3.3. Алгоритм проверки включения C-системы в C-систему

Этот алгоритм, как и его частный случай (проверка включения C-кортежа в C-систему), лежит в основе методов уменьшения трудоемкости многих не полиномиальных по вычислительной сложности алгоритмов. При общем подходе к решению этих задач требуется преобразовать вторую C-систему в D-систему (см. п. 2.2), чтобы использовать соотношения из теорем 2.16 и 2.17, которые позволяют осуществить проверку за время, полиномиально зависящее от размерности исходных АК-объектов. Однако при преобразовании АК-объекта в альтернативный класс не только требуется алгоритм из класса

#P-полных (класс более трудный, чем NP), но еще может получиться АК-объект с размерностью, экспоненциальной относительно исходного АК-объекта. Рассмотрим менее трудоемкий алгоритм проверки включения C-кортежа в C-систему. Пусть заданы C-кортеж C и C-система R. Необходимо проверить выполнение соотношения C R.

Алгоритм 3.1 (проверка включения C-кортежа в C-систему):

1)проверить, существует ли в R такой C-кортеж Ci, для которого C Ci. Если существует, то выход с ответом "да";

2)вычислить R0 = C R;

3)если R0 = , то выход с ответом "нет";

4)если R0 содержит один C-кортеж Ci, то выход с ответом "нет";

5)проверить, существуют ли в R0 атрибуты, у которых все компоненты равны между собой и равны соответствующим компонентам C-кортежа C. Если такие атрибуты существуют, то удалить их из R0 и из C (т.е. вычислить проекции этих АК-объектов по остальным атрибутам), в результате чего будут получены АК-объекты R1 и C1;

6)считая полученный на шаге 5 C-кортеж C1 универсумом отношения R1,

вычислить D-систему R1 .

7) проверить непустоту полученной D-системы R1 , при возможности

113