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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⇐ Предыдущая12131415161718192021Следующая ⇒

Поделиться:

Популярное:

1. DFD - диаграмма потоков данных
2. ER-модель и ее отображение на схему данных
3. Анализ биографических данных
4. Анализ данных по теме дипломной работы
5. Анализ и интерпретация данных экспериментально-психологического исследования.
6. Анализ и интерпретация полученных данных
7. Аппаратная реализация передачи данных по сети.
8. База данных «Автопредприятие»
9. База данных «Авторемонтная мастерская»
10. База данных «Картинная галерея»
11. База данных «Личная библиотека»
12. База данных «Обслуживание работы международной конференции»