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

Выбор ведущего D-кортежа. Пусть алгоритмы 3.3 и 3.1 (или 3.2)

применяются совместно. Тогда при выполнении шага 2 алгоритма проверки включения C-кортежа в C-систему существенное сокращение размерности результата пересечения C-кортежа и С-системы обеспечивается предварительной ортогонализацией. Уменьшение размерности результата достигается с помощью соответствующего выбора D-кортежа Dk1, преобразуемого в C-систему Rk0, т.е. ведущего D-кортежа. Пусть в атрибуте Xi D-системы Rk содержится Ki(1) компонент со значением {1} и Ki(0) компонент со значением {0}. Если в ведущем D-кортеже атрибут Xi не пуст и равен t {0, 1}, то Dk1 преобразуется в ортогональную C-систему Rk0 таким образом, чтобы все C-кортежи в Rk0 не содержали фиктивных компонент в атрибуте Xi. В таком случае Rk0 включает один C-кортеж со значением t в атрибуте Xi и m – 1 C-кортежей со значением t в том же атрибуте. Если, допустим, t = 1, то при пересечении C-систем Rk0 Rk1 получаются пустыми по крайней мере Ki(0) + (m 1)Ki(1) C-кортежей. При учете данного свойства удается подбором ведущих D-кортежей и выбором метода их ортогонализации построить стратегию вычислений, существенно уменьшающую число необходимых операций за счет элиминации большого числа пустых C-кортежей.

Одно из приложений алгоритма распознавания выполнимости КНФ в исчислении высказываний – доказательство полиномиальной разрешимости некоторых не известных ранее классов КНФ. Пока что не проводились достаточно представительные исследования по оценке эффективности алгоритма 3.3 в общем случае, но для систем, изоморфных формулам исчисления высказываний, были получены некоторые интересные результаты. Доказано, что если КНФ выражена как D-система, где содержатся только три равномерно распределенные (с вероятностью 1/3) символа: 1, 0 и , такая КНФ разрешима в среднем за полиномиальное время. Даже без применения рассмотренных выше методов ускорения среднее время решения не превосходит полинома 3-й степени от числа конъюнктов [Кулик, 1995].

3.5. Алгоритмы выполнения кванторных операций

Из теорем 2.23 и 2.24 следует, что операция x(R) легко осуществима, если АК-объект R представляет собой C-систему, а операция x(R) – если R есть

121

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

Пусть задана формула x(R), где R – C-система, содержащая атрибут X. Рассмотрим проекцию –X(R). Каждому элементарному кортежу ti в этой проекции соответствует некоторое множество элементов из атрибута X. Если в

–X(R) существует хотя бы один элементарный кортеж ts, которому в R соответствует множество всех элементов домена атрибута X, то отношениеx(R) непусто. И наоборот, если такого элементарного кортежа не существует, то x(R) = . Следовательно, для вычисления формулы x(R), где R – C-система, необходимо найти все элементарные кортежи типа ts в проекции

–X(R) или убедиться в их отсутствии.

Часть задачи решается просто, если в C-системе R существуют C-кортежи с фиктивной компонентой в атрибуте X. Тогда ясно, что x(R) , а для C-системы R , сформированной из этих C-кортежей, выполняется R x(R). Для полного решения задачи необходимо в оставшейся C-системе Q = R \ R найти множество элементарных кортежей из проекции –X(Q), которым в Q соответствует множество всех значений атрибута X. Поиск таких кортежей основан на следующем соотношении.

Теорема 3.6. Если в C-системе Q существует атрибут X, такой что пересечение всех C-кортежей в проекции –X(Q) непусто и равно C-кортежу C, то при добавлении в C атрибута X с компонентой, равной объединению всех компонент этого атрибута в Q, образуется C-кортеж C1, такой что C1 Q.

Доказательство. При пересечении C1 Q получается C-система, у которой во всех C-кортежах проекции –X(Q) компоненты одинаковы и совпадают с соответствующими компонентами C-кортежа C, а в проекции [X] совпадают с компонентами этого атрибута в Q. Такие C-кортежи можно объединить в один C-кортеж, у которого компонента в атрибуте X равна объединению всех компонент этого атрибута в Q. Тогда полученный C-кортеж равен C1. Из равенства C Q = C следует C Q. Конец доказательства.

122

Перейдем к алгоритму. В C-системе Q необходимо найти такие множества C-кортежей, у которых объединение компонент в атрибуте X равно домену этого атрибута. Перенумеруем все C-кортежи в Q номерами из J = {1, 2, ..., n} и выделим проекцию Q[X], которая будет представлять некоторую систему подмножеств {si} множества X, где индекс i J совпадает с номером

n

соответствующего C-кортежа из Q. Ясно, что si X означает невозможность

i 1

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

n

Если же si = X, то в системе множеств {si} существует некоторая

i 1

совокупность минимальных покрытий. Минимальное покрытие системы {si} на носителе X есть такая совокупность {sk} множеств из {si}, объединение которых равно X, и при этом удаление любого множества из {sk} приводит к тому, что объединение оставшихся подмножеств из {sk} становится строгим подмножеством X (т.е. перестает быть покрытием X).

Пусть Jk – некоторое подмножество индексов, содержащее номера всех компонент минимального покрытия {sk}. Если из C-системы Q выбрать все C-кортежи с номерами, принадлежащими Jk, то из них можно сформировать C-систему Qk, обладающую следующим свойством: если найти пересечение всех C-кортежей проекции –X(Qk), то в случае непустого пересечения получим C-кортеж Ck, который при добавлении фиктивного атрибута X удовлетворяет соотношению Ck Qk.

С учетом этого можно построить следующий алгоритм.

Алгоритм 3.4 (вычисление x(R) для C-системы):

1)сформировать пустое множество A, в котором накапливаются C-кортежи для x(R);

2)из C-системы R извлечь C-систему R с фиктивными компонентами в атрибуте X и выполнить A R ;

3)сформировать Q = R \ R ;

4)из проекции Q[X] сформировать систему множеств {si}; i J;

123