6.2. РАСШИРЕННАЯ РЕЛЯЦИОННАЯ АЛГЕБРА И СВЯЗЫВАЕМЫЙ С НЕЙ ЯЗЫК ЗАПРОСА
6.2.1. ОБОБЩЕНИЕ ОПЕРАЦИИ ОТБОРА
Основные характеристики. Операция
-отбора состоит в нахождении строк некоторого отношения, составляющие которого удовлетворяют заданному условию (простому или составному) Следовательно, эта операция играет большую роль в построении языка запроса. Операция
-отбора, применяемая к отношению
при условии С, обозначается через
Составное условие С строится на основе простых условий с помощью логических связок (отрицания, конъюнкции, дизъюнкции). При этом различают два типа простых условий: условия вида
содержащие два атрибута А и В и отношение сравнения 0, а также условия вида
включающие один атрибут А и одну константу а, которая может быть четкой или нечеткой. В обычной реляционной алгебре в качестве отношения сравнения выступают равенство
неравенства
. В рамках нашего подхода можно представить вариант (четкого или нечеткого) сравнения с помощью функции принадлежности
определенной на декартовом произведении двух областей и принимающей свои значения в интервале [0, 1]; таким образом можно моделировать такие отношения сравнения, как «примерно равен”, «значительно больше, чем” и т. д.
Использование функций распределения возможностей с целью ограничения возможных значений каждого атрибута индуцирует меру возможности и меру необходимости, служащих для оценки удовлетворения заданного условия некоторой строкой. Напомним, что меры возможности и необходимости, построенные по некоторой функции распределения возможностей
определяются для нечеткого отношения соотношениями (см. формулы (1 63) и (1.66))
и
Таким образом, в результате
-отбора
получаем два нечетких множества: множество строк отношения
которые, возможно, удовлетворяют условию С, и множество строк, которые с необходимостью удовлетворяют условию С, где степень принадлежности соответствует мере возможности и мере необходимости. В работах [22, 23, 25] для случая неполной, но четкой информации также проводились различия между множеством строк, которые достоверно удовлетворяют некоторому запросу, и множеством строк, которые, возможно, удовлетворяют этому же запросу.
Мы запишем
с целью выразить, что результат
-отбора есть пара нечетких множеств. Когда функция распределения возможностей нормальна, возможность (четкого
или нечеткого) события всегда больше или равна его необходимости и для каждой строки х отношения
получаем
где через
обозначается функция принадлежности. Формула (6.8) выражает условие вложенности нечетких множеств
Составные условия. Оценка некоторого составного условия сводится к оценке простых условий благодаря следующим результатам
где
(соответственно
) означает дополнение к
(соответственно к
причем определяется дополнением степени принадлежности
, а объединение и пересечение нечетких множеств определяются соответственно операторами
Формула (6.9) непосредственно получается из условия
Формулы (6.10) и (6 11) применимы лишь тогда, когда атрибуты, входящие в условия
являются невзаимодействующими (два атрибута называются невзаимодействующими, если для каждой
значение одного из них не зависит от значения другого (см. разд. 1.8).
Простые условия, включающие единственный атрибут и константу. Сначала рассмотрим простые условия вида
где А — атрибут, в — отношение сравнения, представленное с помощью своей функции принадлежности, а — константа, представленная с помощью своей функции принадлежности
Примерами таких условий являются «Возраст значительно больше тридцати лет” или «Возраст, приравниваемый к молодому”, соответствующее запросу «найти всех молодых людей”
Возможность того, что значение атрибута А для объекта х принадлежит множеству элементов, которые находятся в отношении в хотя бы с одним элементом а, задается в виде
причем
где
- область значений атрибута
- функция принадлежности (четкого или нечеткого) отношения, определенного на декартовом произведении
функция распределения возможностей, ограничивающая возможные значения атрибута А для объекта х при дополнительном условии, что
- дополнительный элемент, введенный в разд. 1.1).
Необходимость этого же события задается в виде
В формулах (6.12),
(соответственно
определяет степень принадлежности объекта х к множеству наборов, которые возможно (соответственно с необходимостью) удовлетворяют условию
Формула (6 13) показывает, что
есть нечеткое множество элементов области
которые находятся в отношении 0 хотя бы с одним элементом а. Формула (6.13) расширяет на случай нечетких множеств следующее выражение, справедливое дня обычных множеств:
где
- множество элементов области
находящихся в отношении в с
Отметим, что если отношение
рефлексивно
то
. Формулы (6.12) и (6.14) непосредственно следуют из выражений (6 5) и (6 6). Если а можно представить в виде объединения двух нечетких отношений
, где объединение определяется оператором
, то имеем
Аналотичной формулы для пересечения не существует. Можно убедиться, что
С друг ой стороны, имеем лишь
Таким образом, при проведении вычислений по формуле (6.14) а нельзя представить в виде объединения двух подмножеств. К тому же бывают ситуации, когда дизъюнкция двух расплывчатых предикатов нельзя удовлетворительным образом представить объединением нечетких множеств, а более адекватное представление дает выпуклая оболочка объединений Выпуклая оболочка а нечеткого множества, определяемая на внолне упорядоченном универсальном множестве
задается выражением
Отметим, что
, выпуклая оболочка объединения двух нечетких множеств
и с представлена на рис. 6.1. Так, выпуклая оболочка нечеткого множества, выражающего характеристику «средней или большой”, включает все элементы, расположенные между
Рис. 6.1
«средним” и «большим” со степенью принадлежности, равной 1.
Замечание Когда
когда имеется ненулевая возможность того, что атрибут А не применим к объекту х, формулы (6 15) и (6.16) заменяются формулами
где символ означает, что формуле (6 12) используется сужение функции
на множество
а не
, определенное на множестве
как в формуле (6 23) С целью обоснования формулы (6 23) заметим, что необходимость в том, чтобы объект х удовлетворял условию
соответствует невозможности события ”А не применим к
или значение
не удовлетворяет условию
Мера возможности, появляющаяся в формуле (6 23), вычисляется заменой а о в на
и
на
и
в формуле (6 12).
Наконец, рассмотрим случай, когда в - равенство,
и формулы (6.12) и (6 14) выражают соответственно возможность и необходимость тою, что значение
принадлежит а. Вообще говоря, следует заметить, что если а — одноточечное множесгво
то условие
находится в отношении
имеет смысл
находится в отношении в с
тогда как в противном случае условие
находится в отношении в
означает в рамках нашего подхода, что
находится в отношении в с
Простые условия, включающие два атрибута. Теперь мы рассмотрим простые условия вида
где А и В — различные атрибуты с одной и той же областью значений, а в — четкое или нечеткое отношение сравнения, выраженное с помощью своей функции принадлежности
. В дальнейшем мы будем предполагать, что атрибуты всегда применимы. Такие условия содержат
в следующих примерах «Найти всех студентов, у котррых уровень подготовки по математике примерно равен уровню подготовки по физике” или «Найти всех студентов, у которых уровень подготовки по математике выше,
уровень подготовки по физике”.
Возможность того, что значение атрибута А для объекта х будет
отношении в со значением атрибута В для того же объекта х, задается выражением
где
функция распределения возможностей, ограничивающая возможные значения пары
для
Когда атрибуты А и В являются невзаимодействующими, функцию распределения
в можно разложить следующим образом
(см разд. 1.8) Тогда выражение (6 24) принимает вид
Необходимость того, что значение атрибута А для объекта х будет в отношении в со значением атрибута В для объекта х, задается выражением
которое в случае невзаимодействующих атрибутов принимает вид
Отметим, что формулы (6.24) и (6.27) непосредственно выводятся из соотношений (6.5) и 6.6).
Величина
(соответственно
определяет степень принадлежности объекта х к множеству таких наборов, которые возможно (соответственно с необходимостью) удовлетворяют условию
В случае симметричных отношений сравнения (равенство, приближенное равенство) можно убедиться, что выражения (6.26) и (6.28) симметричны по А и В. Точнее, в случае равенства
формула (6.28) оценивает необходимость того, чтобы значения атрибутов А и В для объекта х были равны, однако не оценивает, насколько равны функции распределения возможностей
самом деле, величина
в формуле (6.28) принимает ненулевое значение тогда, и только тогда, когда
такое, что
и За
где
значение необходимости, полученное по формуле (6.28), равно 1 тогда, и только тогда, когда значения атрибутов точно известны и равны.
Замечания. Отметим, что вопрос «Найти людей, возраст которых примерно равен возрасту Поля” - рассматривается в рамках подхода, используемого для условий вида
хотя связанное с ним условие может быть типа
где а - информация о возрасте Поля Фактически мы должны сравнить возраст х и возраст Поля, а не оценивать, насколько возраст х принадлежит нечеткому множеству значений, примерно равных возможному возрасту Поля. В более общем случае можно убедиться, что
но
где
выражение (6.31) является строгим неравенством, за исключением нескольких особых случаев; в частности, равенство выполняется тогда, когда а - одноточечное множество.
Толерантность. Содержание этого параграфа охватывает две проблемы: вначале рассматриваются последствия возможной неточности задания функций принадлежности, определяющих распределения возможностей, затем изучаются способы учета изменений в ограничении С и их влияние на результат
-отбора
.
Как отмечалось в [32], если
максимальная амплитуда возможной абсолютной ошибки в каждой точке области определения функции распределения возможностей, то эта возможная ошибка не может изменить значения мер возможности и необходимости, вычисляемые по этим функциям распределения, больше чем на е. Наоборот, в теории вероятностей ошибки при задании функции распределения могут привести к более серьезным нарушениям.
Условие С при
-отборе
включает одно или несколько отношений сравнения, в зависимости от того, является ли оно простым или составным. Это условие можно сделать более или менее ограничительным, изменяя отношения сравнения. Отношение сравнения 0 можно смягчить (например, заменяя строгое равенство на приближенное равенство) за счет его композиции с некоторым четким или нечетким отношением толерантности Т:
где
— функция принадлежности отношения толерантности, которая должна быть рефлексивной и симметричном (т. е.
). Отметим, что при наличии условия
введение отношения толерантности Т приводит также к расширению множества элементов, находящихся в отношении 0 хотя бы с одним элементом а, поскольку имеем
где о означает
- композицию. Практически вычисление
-композиции по формуле (6.33) сводится к сложению нечетких чисел (см. замечание в конце разд. 2.3.2)