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

Теорема 5.3. Если для логической формулы F осуществима элементаризация, то ее представление S(F) в виде структуры АК в вероятностном пространстве есть точное решение уравнения регрессии.

Доказательство. Математическое ожидание уравнения регрессии в многомерном пространстве определяется как уравнение

E(y x1, x2, ..., xn) = (x1, x2, ..., xn),

где (x1, x2, ..., xn) – математическая модель уравнения регрессии в пространстве X1 X2 … Xn событий. Поскольку функция y = S(F) – отображение, в котором множество y представлено одним значением ("истина" или заданное состояние системы), то справедливо

E(y x1, x2, ..., xn) = E(S(F) x1, x2, ..., xn).

Из определения условной вероятности следует

P(S(F) x1, x2, ..., xn) = P(S(F)) (x1,x2,...,xn )),

P(x1,x2,...,xn )

где (x1, x2, ..., xn) соответствует полной группе событий, равной универсуму в пространстве X1 X2 … Xn атрибутов. Поскольку S(F) (x1, x2, ..., xn) = S(F) и

P(x1, x2, ..., xn) = 1, то P(y x1, x2, ..., xn) = P(S(F)) при любых значениях xi и,

следовательно, E(y x1, x2, ..., xn) = S(F). Конец доказательства.

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

Приведенные в этом и предыдущем разделах соотношения, алгоритмы и примеры показывают, что применение алгебры кортежей в логиковероятностном анализе обеспечивает решение следующих задач:

1)унификация алгоритмов расчета вероятностей сложных событий не только для моделей, заданных формулами исчисления высказываний, но и исчисления предикатов, что позволяет разработать методы расчета вероятности для систем с многими состояниями;

2)логический анализ систем с учетом условий и любых ограничений, а также с возможностью вероятностного расчета получающихся вариантов;

180

3) обратная задача вероятностного анализа: по заданным оценкам вероятностей сложных событий восстанавливать функции распределения маргинальных вероятностей и вероятностей событий с неизвестными оценками.

5.2.Работа с данными в структурах АК

5.2.1.Реляционные СУБД

Основные объекты управления в реляционных БД – файлы, организованные в виде таблиц (отношений), которые состоят из множества элементарных кортежей. В терминах АК таблица представима как C-система, где все компоненты есть одноэлементные множества. Такое представление позволяет применять все средства управления БД, включая методы поиска по ключу на основе теории нормальных форм, но не учитывает специфические свойства структур АК.

Если реляционные СУБД входят в состав систем искусственного интеллекта, то возникает необходимость в ассоциативных методах поиска, а также в средствах логического анализа данных, не предусмотренных в "классических" реляционных СУБД. В интеллектуальных системах преобладают структуры (сети, правила логического вывода, предикаты и т.д.), моделируемые АК-объектами с многоэлементными компонентами. Посредством таких же АК-объектов удобно выражать некоторые проекции обычных таблиц БД. За счет представления разнородных структур данных и знаний в виде АК-объектов достигается унификация их обработки и ускорение связанных с ними вычислительных процедур.

Опишем, как в АК выражаются запросы к СУБД. Если запрос сформулирован в виде АК-объекта, то атрибуты в нем делятся на два типа. К первому типу относятся атрибуты с заданными значениями, а ко второму – проблемные атрибуты, значения которых надо установить или уточнить в процессе поиска. При построении запроса проблемные атрибуты вводятся как фиктивные (в этом случае область поиска значений проблемных атрибутов охватывает всю область определения атрибута) или же в виде нефиктивной компоненты (тогда область поиска сужается).

Для реализации запросов над файлами (базовыми таблицами) или представлениями (производными таблицами) БД используется реляционная

181

алгебра (RA) [Дейт, 1999] со своим набором операций. Пять из них – основные: проекция, объединение, прямое произведение, разность и селекция. Остальные операции RA реализуются как комбинации основных операций. Покажем, что означают в АК основные операции RA.

Операция проекция в RA создает из отношения Q[X] отношение Qp[X\Y], где для множеств атрибутов X и Y справедливо Y X. Ясно, что в АК этой операции соответствует аналогичная операция.

Операция объединение в RA эквивалентна объединению C-систем с одинаковыми схемами отношений.

Операция прямое произведение (иногда эту операцию называют декартово произведение) в RA реализуется в АК пересечением C-систем, у которых схемы отношений не содержат одинаковых атрибутов. Например, в RA

В АК осуществление этой операции намного упрощается за счет использования фиктивных атрибутов. Для выполнения такой операции в АК достаточно найти пересечение двух C-систем, приведенных к единой схеме отношения (обобщенное пересечение):

и получить тот же результат.

Операция разность в RA эквивалентна в АК одноименной операции с однотипными отношениями, при этом можно использовать известное соотношение алгебры множеств:

P[X] \ Q[X] = P[X] Q[X].

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

182

схемы отношения в двух вариантах (X и Y – имена атрибутов): 1) X с и 2) X Y, где c – элемент или множество элементов сорта, соответствующего

предназначенными для селекции данных согласно отношениям сравнения. В ряде случаев эти операции можно выразить через уже известные нам операции АК. Рассмотрим примеры селекции в АК.

Для случая, когда селектор задан в виде равенств Xi = ci, ограничение можно выразить как C-кортеж, у которого выбранные атрибуты Xi представлены элементами или подмножествами соответствующих сортов, а остальные атрибуты данной схемы отношения – фиктивными компонентами. Например, для отношения P[XYZV] C-кортеж [ {a} {d, f}] является селектором с ограничениями Y = a; V = d или f. Селекция по данным ограничениям формируется при пересечении этого C-кортежа с отношением P. Для ограничения типа Xi ci в соответствующей позиции C-кортежа-селектора применяется компонента {ci}. Для отношений типа <, , или >, которые применимы только в частично упорядоченных множествах, селекторы также можно формировать в виде C-кортежей, у которых компоненты заданы как интервалы.

Теперь рассмотрим случай, когда селектор содержит ограничения типа 2. Допустим, в селекторе – условие равенства двух атрибутов. Например, имеется

Тогда сначала надо сформировать C-систему, у которой компоненты в атрибутах Y и Z равны пересечению компонент этих атрибутов в каждом C- кортеже, и удалить пустые C-кортежи. В результате получится промежуточная

{a, c} {a, c} 2-й и 3-й компонент второго C-кортежа выбирается только диагональ, в результате чего будет получена C-система

183

Опишем некоторые производные операции RA.

Операция пересечение двух однотипных отношений R и S в RA реализуется как комбинация операций R \ (R \ S). Нетрудно убедиться:

R \ (R \ S) = R R S = R (R S) = (R R) (R S) = R S,

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

Операция соединения отношений в RA определяется так. Пусть P[XA] и Q[BY] – отношения, где X, Y – некоторые непересекающиеся множества атрибутов, A, B – разные имена одного атрибута или разные атрибуты, относящиеся к одному и тому же сорту. Тогда результатом операции соединения является отношение R[X(A B)Y], где – одно из множества отношений сравнения {<, , =, , , >}. Если – покомпонентное равенство, то соединение отношений представляет в АК обычное пересечение АК-объектов при условии, что атрибутам A и B присваивается одно имя. При других условиях сравнения выполняется та же операция пересечения АК-объектов, но перед этим все компоненты одного из сравниваемых атрибутов преобразуются с учетом семантики отношения .

Приведем примеры. Пусть в БД имеется отношение, которому сопоставлен АК-объект P[XYZ], и требуется найти возможные значения атрибутов X и Y при заданном диапазоне значений D атрибута Z. На языке SQL этот запрос выражается так:

SELECT X, Y FROM P WHERE Z D.

В АК представленный запрос записывается как C-кортеж Q1[Z] = [D]. Ответ на запрос можно получить, вычислив

P[XYZ] G Q1[Z] = P[XYZ] Q1[XYZ], где Q1[XYZ] = [* * D].

Приведем пример, где требуется соединение отношений. Предположим, что в БД помимо отношения P[XYZ] имеется отношение R[YVW] и требуется найти значения атрибутов X и V, если Z = a. На языке SQL запрос

184