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

декартовых произведения

{a, c, d} {b, c} {b, c, f} и {a, d} {b, c} {b, f},

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

4. Объединение декартовых произведений В общем случае объединение двух декартовых произведений нельзя

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

Если нужно вычислить число элементов в объединении двух декартовых произведений, то расчет производится по следующей формуле. Пусть даны декартовы произведения A и B. Тогда

A B = A + B – A B .

Пример. Пусть A = {a, c, d} {b, c} {b, c, f} и B = {a, b, d} {b, c} {b, c, d}. Тогда A B = {a, d} {b, c} {b, c}; A = 18; B = 18; A B = 8;

A B = 18 + 18 – 8 = 28.

Существуют случаи, когда в соотношении (1.8) знак включения можно заменить знаком равенства. Таких случаев всего два.

Первый случай. Если для двух декартовых произведений A и B соблюдается A B, то справедливо A B = B. Например,

{a, c, d} {b, c} {b, c, f} {a, d} {b, c} {b, f} = {a, c, d} {b, c} {b, c, f},

так как проверка показывает, что второе декартово произведение включено в первое.

Второй случай. Если в двух декартовых произведениях все "места", за исключением одного, содержат равные множества, то в соотношении (1.8) знак включения заменяется на знак равенства. Например,

65

{a, d} {b, c} {b, c, d} {a, d} {b, f} {b, c, d} = {a, d} {b, c, f} {b, c, d},

так как в этих декартовых произведениях отличаются друг от друга только множества на втором "месте", а все остальные "места" содержат равные множества.

5. Разность декартовых произведений.

Структуру этой формулы легче понять, если расположить объединяемые в правой части подформулы в виде столбца:

Эти и некоторые другие свойства декартовых произведений используются в алгебре кортежей, основные понятия и методы которой рассматриваются в главе 2.

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

66

1.4.2. Бинарные отношения

Теория бинарных отношений имеет большую теоретическую базу и находит широкое применение в практических приложениях. Многие алгоритмы

всовременных информационных технологиях построены на основе этой теории

[Кристофидес, 1978; Липский, 1988; Рейнгольд, 1980; Kuznetsov, 2002]. В

частности, исследование свойств бинарных отношений (симметричности, транзитивности, рефлексивности) лежит в основе методов приобретения знаний интеллектуальными системами [Осипов, 2009]. В некоторых книгах, например,

в[Непейвода, 1997; Новиков, 2002], под теорией отношений подразумевают теорию бинарных отношений.

Бинарное отношение – это отношение, заданное как некоторое подмножество декартова произведения двух множеств, или подмножество пар

(ai, bj) декартова произведения A B, где ai A; bj B.

Широко известны частные случаи бинарных отношений – графы и частично упорядоченные множества. Бинарное отношение можно задать списком пар или (в случае, когда A = B) матрицей смежности порядка n n, где n

– мощность множества A.

Нередко бинарные отношения типа R A B представляют как соответствие между элементами множества A и элементами множества B.

Тогда множество A называется областью отправления, а B – областью прибытия соответствия. Соответствие, в котором каждому элементу области отправления сопоставляется не более одного элемента в области прибытия,

называется функциональным соответствием или отображением.

Для совокупности бинарных отношений, заданных на одном декартовом произведении, выполняются все соотношения и операции алгебры множеств (пересечение, объединение, дополнение, включение, равенство). Помимо операций алгебры множеств, в них определены еще три операции: соединение, композиция и обращение. Первые две операции возможны и для случаев, когда эти отношения определены на разных декартовых произведениях. Унарная операция обращения – это операция, при выполнении которой элементы всех пар отношения меняются местами. Более подробно перечисленные операции будут рассмотрены ниже (см. главу 2) как примеры использования алгебры кортежей при моделировании бинарных отношений и соответствий.

67

1.4.3. Отношения в реляционной алгебре

Одна из распространенных математических систем, предназначенных для моделирования и анализа многоместных отношений, – это разработанное Э.Ф. Коддом реляционное исчисление, которое лежит в основе современных систем управления базами данных (СУБД) [Codd, 1970; Codd, 1972]. На основе реляционного исчисления была создана реляционная алгебра, позволяющая

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

В основе реляционного исчисления лежат некоторые аналитические средства исчисления предикатов. Область интерпретации этого исчисления – множество кортежей всех включенных в конкретную СУБД отношений. Чтобы обеспечить в БД работу не только с кортежами, но и с атрибутами, в реляционное исчисление вводится понятие индексированной переменной. Для этого разработана теория нормализации отношений [Codd, 1971; Fagin, 1971], существенно облегчающая поиск информации в базах данных.

Одним из основных языков для СУБД является SQL, с его помощью осуществляется логический вывод новых фактов на основе существующих [Дейт, 1999; Ульман, 2000]. Однако выразительные и аналитические средства СУБД существенно беднее средств и методов математической логики хотя бы потому, что в них не используется дополнение отношения, а методы логического вывода существенно упрощены. Для расширения этих возможностей были разработаны дедуктивные базы данных [Чери, 1992], которые отличаются от реляционных тем, что в них определены рекурсивные процедуры. Но такое расширение не позволяет применять значительную часть аналитических средств математической логики. Итак, современную теорию баз данных нельзя рассматривать как общую теорию многоместных отношений.

68

1.4.4. Отношения в логике и искусственном интеллекте

Во многих современных теоретических исследованиях по искусственному интеллекту [Вагин, 2004; Тейз, 1990; Смолин, 2004; Представление знаний, 1989] предлагается в основном декларативный подход к разработке приложений. В математической логике термин "отношение" употребляется редко, однако оказывается, что многие структуры логики и искусственного интеллекта представимы в виде многоместных отношений. В математической логике предикаты изоморфны отношениям [Новиков, 1973]. Покажем, что любую логическую формулу можно отобразить в виде многоместного отношения.

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

Рассмотрим вкратце основные структуры баз знаний искусственного интеллекта. К ним относятся семантические сети, фреймы и системы продукций. Формально семантические сети эквивалентны ориентированным графам с помеченными вершинами и ребрами [Искусственный интеллект, 1990; Представление знаний, 1989]. Имена ребер соответствуют именам отношений, а вершины – элементам семантической сети. С учетом этого любую семантическую сеть можно представить как совокупность связанных по смыслу бинарных отношений. В правилах вывода на семантических сетях используются операции, которые соответствуют композиции или соединению этих отношений.

Фреймы реализуют более сложные (по сравнению с семантическими сетями) структуры. Каждый фрейм состоит из некоторого множества слотов, а каждый слот содержит значение слота. Значением слота могут быть

69