Лекции.ИНФО


Метаструктура базы данных и операций



Как уже было сказано, модуль базы данных предназначен для размеще­ния данных, обрабатываемых в процессе, реализуемом ПСМ. Основными параметрами, определяющими организацию конкретной базы данных, являются объем и характер данных, тип операций над ними, а также стратегия управления процессом вывода.

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

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

Характер организации данных

Данные в базе организованы в структуру, называемую основной. Эле­ментами этой структуры являются компоненты. Компонента, в общем случае, является структурной единицей произвольной сложности и пред­ставляет собой четверку:

- имя (идентификатор);

- тип — каждому типу сопоставляется характеристика (фиксиро­ванный набор переменных) и структура. В характеристику может входить информация о некоторых стандартных для данного типа отношениях с другими компонентами;

- описание — определяет конкретные значения для каждой перемен­ной в характеристике данного типа;

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

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

Операции над базой данных

Стандартным способом доступа к данным базы является вход по ассоци­ативному адресу {образцу), осуществляемый операцией "поиск по образ­цу". Аргумент операции "поиск по образцу" представляет собой структу­ру, характер которой может меняться в достаточно широком диапазоне в зависимости от функций, выполняемых базой данных. Результатом этой операции является множество (возможно, пустое — негативный резуль­тат) всех референтов образца-аргумента, т.е. фрагментов базы данных, каждый из которых представляет собой ответ на запрос, специфициро­ванный в форме этого образца.

Можно выделить несколько типов образцов.

Простой образец — это фрагмент структуры того же типа, что и каркас. В вершинах простого образца компоненты могут указываться частично, например, только имя или только тип. Характер процедуры, реализуемой операцией "поиск по образцу", может быть двух видов:

- точное совпадение — референты изоморфны образцу с точностью до отсутствующих элементов в образце;

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

Разрывный образец — это совокупность простых образцов, свя­занных дугами специального вида, отсутствующими в каркасе. В этом случае графы образца и референта не являются изоморфными, посколь­ку в последнем отсутствуют специальные дуги. Можно сказать, что при разрывном образце поиск происходит не на самом каркасе, а на его тран­зитивном замыкании по одному или нескольким типам отношений. В. Образец с отрицательным контекстом представляет собой пару

< положительный образец, отрицательный образец >,

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

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

Сложный образец — представляет собой совокупность видов образ­цов, перечисленных выше. Результатом поиска по сложному образцу является сочетание процедур поиска по каждому из образцов совокуп­ности.

Будем делить операцию "поиск по образцу" на два основных вида: одновариантный и многовариантный поиск.

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

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

Еще одной операцией над базой данных является добавление. Смысл этой операции — присоединение новых данных к данным, находящимся в базе. Аргумент этой операции состоит из двух частей: первая пред­ставляет собой тот фрагмент, который присоединяется к базе данных, и имеет ту же организацию, т.е. состоит из каркаса и набора компонент, сопоставленных его вершинам; вторая часть является, в общем случае, ассоциативным адресом, указывающим, к каким вершинам каркаса бу­дет присоединяться новый фрагмент.

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

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

Контроль несовместимости

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

Контроль несовместимости может осуществляться несколькими спо­собами:

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

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

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

Ассоциативная надстройка

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

Очевидно, что при изменении состояния базы данных (при добавле­нии и исключении компонент) требуется затрата дополнительных уси­лий на редактирование ассоциативной надстройки. Таким образом, со­кращая затраты, связанные с операцией "поиск по образцу", введение этой подсистемы увеличивает затраты на остальные две операции.

Метаструктура модуля правил

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

Основные составляющие этого модуля — аппарат активации, база правил (П-база) и интерпретатор. Опишем выделенные составляющие более подробно.

Аппарат активации

В ПСМ, не включающем аппарата управления активацией, все правила находятся в активированном состоянии в течение всего процесса. Это означает, что условия применимости каждого правила проверяются при каждом изменении состояния базы. Такая организация естественна при небольшом числе правил, отсутствии достаточных оснований для содер­жательного структурирования правил по их функциям и удовлетвори­тельной эффективности ПСМ.

В общем случае возникает необходимость ограничивать совокупность правил, проверяемых на текущем этапе процесса, для чего в ПСМ вво­дится аппарат управления активацией.

Очевидно, что существует множество способов организовать такое ограничение. Механизм активации может быть:

- статическим, т.е. определенным заранее и не меняющимся в про­цессе работы ПСМ;

- динамическим, т.е. управляемым ходом процесса;

- смешанным, комбинирующим статические и динамические элемен­ты управления активацией.

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

Другим средством управления активацией является включение в опе­ратор правила указания о переходе к одному или нескольким следующим правилам. В случае, если такое указание зависит от условия, проверяе­мого оператором, оно относится к динамической составляющей аппарата активации.

Одним из широко распространенных средств активации правил явля­ется использование метаправил (правил над правилами), при котором правила разбиваются на классы и в зависимости от состояния базы дан­ных активируется тот или иной класс [84].

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

Структура правил

Как уже отмечалось, продукция представляет собой тройку:

< имя, условие применимости, оператор >,

где имя однозначно специфицирует правило. Условие применимости пра­вила может быть разделено на две части:

- условия к базе данных,

- внешние условия.

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

В самом общем виде условия к базе данных представляют собой конъюнкцию двух типов условий, которые называются положительны­ми (+УП) и отрицательными (-УП). Первые специфицируют сочетания компонент, наличие которых в базе означает выполнение соответствую­щего положительного образца, а вторые — сочетание компонент, наличие которых означает невыполнение данного отрицательного образца.

Как +УП, так и -УП представляют собой совокупность условий:

- на компоненты, входящие в данное сочетание, взятые в отдельно­сти;

- на согласование значений тех или иных характеристик этих ком­понент в случаях, когда эти значения взаимосвязаны;

- на отношения, связывающие соответствующие компоненты в кар­касе базы.

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

- редактированию базы данных;

- воздействию на аппарат активации;

- обращению вовне данного ПСМ;

- редактированию системы правил.

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

Для операции "добавление" — это новый фрагмент, добавляемый к базе данных, и адрес его подклейки к вершинам каркаса базы данных. Описание нового фрагмента и его адреса могут быть включены в опера­тор либо вычисляться на основании информации о компонентах, описан­ных в условиях применимости.

Для операции "исключение" — это фрагмент, который следует уда­лить из базы. Вместе с удалением фрагмента происходит корректировка каркаса базы.

Воздействие на аппарат активации определяется выбором конкретно­го варианта управления активацией. Это может быть:

- явное указание о переходе на определенное правило или группу правил;

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

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

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

2.5.6.3. Представление правил и интерпретатор

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

Уровень внутреннего представления может быть самым разным, на­пример:

- язык типа специализированного автокода. В этом случае интерпрета­тор представляет собой программную машину с автокодом в качестве языка команд;

- правила написаны на том же языке, на котором реализуется весь ПСМ, при этом интерпретатор становится излишним.

Очевидно, что здесь перечислены лишь самые общие точки специ­фикации П-модуля, которые в значительной степени взаимообусловлены. Например, существует тесная связь между аппаратом активации и ассо­циативной надстройкой.









Читайте также:

Последнее изменение этой страницы: 2016-03-17; Просмотров: 96;


lektsia.info 2017 год. Все права принадлежат их авторам! Главная