ПРИЛОЖЕНИЕ К ГЛ. 6

В этом приложении приводится программа обработки вопросов, составленная на примере из разд. 6.3. В первой части описывается способ представления данных в программе, затем излагается способ практического представления вопросов и даются комментарии к процедурам обработки этих вопросов. Программа написана на языке MACLISP и реализована на (введение в программирование на языке Лисп читатель найдет в работе [15] из списка литературы к гл. 6).

1. СТРУКТУРИРОВАНИЕ ДАННЫХ

База данных - это список атомов где каждый атом представляет собой расширенное отношение. Любому атому (например, приписываются два свойства: и Содержание свойства — это список атрибутов, описывающих атом Содержание

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

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

Используемые отношения сравнения параметризуются следующим образом. Для некоторого отношения сравнения в можно записать, что где — функция распределения возможностей, кодируемая четверкой (например, понятие «значительно больше, обозначаемое кодируется четверкой где - величина, достаточно большая по отношению к элементам области значений. Код, приписываемый отношению сравнения, хранится в свойстве

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

2. ПРЕДСТАВЛЕНИЕ ВОПРОСОВ

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

Для разборчивости на внешнем уровне имеются упрощенные формы дескрипторов; тогда процедура ДЕСКРИПТОР преобразует каждую простую форму в соответствующий дескриптор который будет использоваться в программе Файл содержит упрощенные дескрипторы соответствующие вопросам рассматриваемого примера В дальнейшем мы дадим пояснение относительно общего вида используемых дескрипторов

Здесь элементарной парой называется список из двух элеменгов, второй из которых - атом (имя атрибута) стрелка произвольного отношения также имеет свойство — список элементарных пар, где первый элемент является меткой

Дескриптор Р имеет вид или или где - простые дескрипторы. Простой дескриптор - это список элементарных пар, в которых первый член

- либо выражение - атом (метка), базовая переменная (пример или вторичная переменная (пример

либо функция фильтрации вида процедура) где

процедура не содержит базовой переменной; второй член - атом (имя при необходимости составного атрибута, например ЕСТЕСТВЕННЫЕ НАУКИ). Формы используются тогда, когда стремятся подчинить данные некоторой логической комбинации дескрипторов

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

Сравнение пар и (а А) (принадлежащих соответственно дает значения показателей, равные 1, и назначает значение а переменной X: в случае, когда пара сравнивается с парой (а А), переменной X приписывается предварительно определенное значение и пара сравнивается с парой

В случае использования некоторой функции фильтрации перед тем, как применить процедуру к элементарной паре, соответствующей данным происходит ее инстанциация. Функции фильтрации используются для выражения простых условий вида или где в — отношение сравнения, отличающееся от равенства Тогда процедуры позволяют уточнить характер выполняемых операций над значениями так, чтобы получить показатели, соответствующие этим различным условиям (см разд. 2 1 и 2 1)

Упрощенные дескрипторы отличаются от обычных дескрипторов лишь выражением их возможных функций фильтрации; функция ДЕСКРИПТОР предназначена для построения процедуры вида процедура) исходя из содержания соответствующего простого дескриптора

Ниже приводится фрагмент файла ДАННЫЕ, содержащий дескрипторы

3. ОПИСАНИЕ ВКЛЮЧЕННЫХ В ПРОГРАММЫ ПРОЦЕДУР

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

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

ФУНКЦИЯ ОТБОР

вызывает функцию ДЕСКРИПТОР, которая преобразует упрощенный дескриптор в дескриптор Р;

последовательно обрабатывает каждый элемент отношения с помощью фильтра

возвращает список, составленный из двух списков оцениваемых данных: представляет представляет .

ФУНКЦИЯ ФИЛЬТР работает с содержанием свойства данных и дескриптором Р; производит разложение дескриптора Р на элементарные дескрипторы; последовательно обрабатывает каждую элементарную пару дескриптора Р с помощью функции и комбинирует получаемые результаты посредством операции

ФУНКЦИЯ ФИЛЬТР () проверяет, является ли атрибут элементарной пары Р составным, и если да, то вызывает процедуру

ищет в элементарную пару, соответствующую Р, и, если такая существует, вызывает процедуру сравнения COMPARE.

ФУНКЦИЯ СРАВНЕНИЕ

имеет своими аргументами две элементарные пары с одним и тем же вторым членом;

возвращает список с двумя степенями в интервале [0,1], характеризующими возможность и необходимость того, что содержание будет совместимым;

вызывает процедуры сравнения, адаптированные к виду первого члена если это вторичная переменная, то сравнение данных и представления Р осуществляется с помощью ;

если это атом, то также вызывается

если это функция фильтрации, то процедуру, которую она содержит, обрабатывают с помощью функции и применяют ее к посредством

Механизм представления основан на использовании -списка который содержит различные представления переменных.

ФУНКЦИЯ СОЕДИНЕНИЕ

преобразует упрощенный дескриптор в дескриптор Р; непосредственно производит соединение на и без вычисления их декартова произведения;

работает с дескриптором Р и списками данных отношений и с помощью функции

Алгоритм

пробегается список

пробегается список

вычисляются степени, соответствующие результатам сравнения содержания Р с содержанием

формируется произведение с помощью функции (если ни одна из этих степеней не равна 0);

к результату добавляются эти оцененные данные.

Следующие процедуры используются для построения проекции результатов отбора или соединения на атрибут.

ФУНКЦИЯ ПРОЕКЦИЯ

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

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

Следующие процедуры связаны с эффективной обработкой информации в виде нечетких значений.

(см. скан)

ФУНКЦИЯ вычисляет меру возможности и меру необходимости где метка переменной XI, а метка переменной вызывает для этого функции если универсальное множество переменных XI и непрерывно, и в противном случае. Вышеуказанные вычисления производятся в кодах, связываемых с метками с помощью функций в случае непрерывного универсального множества и в случае дискретного универсального множества.

ФУНКЦИЯ

вычисляет условные меры возможности где в — отношение сравнения, обозначаемое через использует коды связанные с и функции и использует для вычисления кода, связанного с о в.

ФУНКЦИЯ

вычисляет условную меру возможности с помощью

вычисляет условную меру необходимости с использованием

ФУНКЦИЯ

вычисляет условную меру необходимости в виде

использует функцию для вычисления кода, связанного с отношением сравнения 0, определяемым соотношением —

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

(см. скан)

Функции и имеют своими аргументами списки пар. Пусть

Функция вычисляет величину функция вычисляет величину

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

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

Дескриптор связан с условием отбора имеет вид и для каждой строки х отношения требуется вычислить: П («хороший” и («хороший” о где через обозначается отношение сравнения «значительно лучше, Значит, для этих расчетов необходимо воспользоваться процедурой откуда следует общий вид дескриптора который содержит лишь элементарную пару процедуру обработать Вызов функции ДЕСКРИПТОР преобразует в другую элементарную пару (обработать

Фильтрация данных с помощью дескриптора Функция ищет в значении в! элементарную пару, связанную с и вызывает функцию Тогда функция фильтрации применяет процедуру, которую она содержит вместе с параметром равным Обработка данных происходит за счет поиска кодов следующим образом:

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