Б.И. Рабинович

Хранение Баз Знаний в

современных СУБД

Введение

Одной из особенностей систем, основанных на знаниях, является наличие в них Баз Знаний (БЗ). Причем в отличие от Баз Данных (БД), для управления которыми используются современные СУБД, такие как Oracle, MSSQL, MySQL и т.п. для управления БЗ используются специальные языки программирования, где знания представляются с помощью логики предикатов, а управление знаниями осуществляется системой продукций. Разработка таких языков программирования получила широкое распространение в 80-90 гг. Именно тогда была начата разработка декларативного языка ДЕКЛ [1].

Основная проблема, с которой сталкиваются разработчики систем, ядром которых является БЗ, это способ хранения знаний. В технологии, которая предусмотрена ДЕКЛом, знания находятся в «плоских файлах» (flat-file databases). Этот способ хранения обладает такими недостатками, как медленная обработка при больших объемах данных, трудоемкость удаления, сложность поиска. Так же не решены проблемы защиты данных и управления, в то время как в системах с БД все эти задачи эффективно решаются в рамках СУБД.

В отличие от БД, содержащих совокупность фактов о качественных и количественных характеристиках конкретных объектов, БЗ содержат концептуальные, понятийные знания о программном обеспечении (ПО), обычно выражаемые именно в терминах данной ПО [2]. Т.е. представление знаний в БЗ гораздо более информативно. Для повышения эффективности работы систем на БЗ необходимо обеспечить синтез этих двух способов хранения информации: БД в СУБД и БЗ на «плоских файлах» - взять надежность и удобство СУБД и понятийность знаний БЗ. Попробуем описать такую модель.

Язык ДЕКЛ

Этот язык был создан для построения систем, основанных на знаниях. Он обеспечивает работу с расширенными семантическими сетями и обладает гибкими возможностями при работе с ними, с помощью него относительно легко решать различные аналитические задачи, реализация которых на других языках программирования потребовала бы существенно больших временных и умственных затрат [3].

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

Продукции  записываются  в  форме, приближенной к нотации языка ПРОЛОГ, однако формы его несколько  отличаются  от  форм последнего.  В  ДЕКЛ  условная часть записывается первой, т.е. слева, а следствие -  справа  (в  языке  ПРОЛОГ  -  наоборот). Соответственно,  выбрана  другая  процедура применения правил, которая управляется  индикаторами и сводится к проверке  условия с порождением следствий. С помощью продукций реализуется как прямой, так и обратный вывод. При этом язык обладает существенно меньшими ограничениями, характерными для языка ПРОЛОГ.         

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

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

В-третьих, процедура  вычисления не носит "жесткого" характера, как в языке   ПРОЛОГ. Правила  при  применении осматривают все знания, находящиеся в ОП, а не только предикаты запроса. Можно легко управлять такой процедурой, заставляя правила осматривать только нужную часть знаний [4].

В связи с этим, язык ДЕКЛ представляется более удобным для представления знаний, и соответственно, для разработки экспертных и других систем. Хотя формы языка ДЕКЛ далеки от конструкций  естественного языка. Такие формы больше  приближены к логическим (Пример 1).

Пример 1. Процедуры на ДЕКЛе

Расширенные семантические сети

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

РСС состоят из однотипных N-арных фрагментов. В каждый из них введена вершина, называемая кодом фрагмента и соответствующая всей представленной в нем информации [5]. Помимо этого, вводится множество "внутренних" вершин, которые порождает сама система по мере необходимости, и которые сопоставляются неименованным объектам.

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

Содержательные портреты (как и сами документы) помещаются в БЗ, ориентированную на большие потоки информации (сотни мегабайт) и обеспечивающую их быстрый выбор - за счет индексных файлов. Такие портреты «подкачиваются» в оперативную память по мере необходимости, образуя активную часть БЗ [6].

FIO(МАЛЬЦЕВ,ТАТЬЯНА,ЮРЬЕВНА/0+)  0-(4,FIO)

ДОКУМ_(ПАСПОРТ,XXIV,ИК,N_631339/1+)  1-(4,ДОКУМ_)

ИМЕТЬ(0-,1-)

АДР_(ДОЛГОПРУДНЫЙ,СПОРТИВНЫЙ,ДОМ,5,КОРП.,2,КВ.,110,408/2+) 

2-(4,АДР_)

ИМЕТЬ(0-,2-)

Пример 2. РСС

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

Лингвистический процессор

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

Морфологический анализ необходим, чтобы избавиться от различных форм написания слов, и облегчает поиск. Синтактико-семантический анализ служит для выделения из документа значимых объектов и связей.

Блок лексикографического анализа обеспечивает:

Автоматическое деление текста на самостоятельные части (нап­ример, выделение документов из сводок)

Определения начала и конца предложения, а также начала и конца абзаца.

Блок морфологического анализа обеспечивает преобразование слов к единому виду (каноническому) и дает их признаки:

Для каждого слова текста определяется его часть речи, род, число, падеж и другие морфологические характеристики (они зависят от части речи);

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

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

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

Блок синтактико-семантического анализа выполняет следующие функции:

По признакам и контексту выделяет значимые объекты (ФИО людей, организации и др.);

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

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

Такие портреты «подкачиваются» во временные файлы, которые представляют собой «рабочее пространство» (РП) системы, по мере необходимости образуя активную часть БЗ[6].

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

Структура Базы Знаний

БЗ представляет собой набор плоских файлов, в которых хранятся следующие данные: тексты загруженных в систему документов, семантические сети, каталоги и индексы, которые автоматически строятся на их основе. Кроме этого, есть еще два типизированных файла, в которых хранится информация о том, на какой строке файлов БЗ с текстами и семантическими сетями начинаются документы, и какая у них длина. Это сделано для организации более быстрого доступа к данным [4].

В БЗ есть два индексных файла. Первый представляет собой перечень ключевых слов, найденных в семантических сетях, частоту их появления во всех документах и адрес (смещение) списка документов во втором файле, в которых были найдены эти слова. Ключевыми словами являются имена и существительные, такие как: адрес, факс,  номер счета и т.п.

Также на этапе загрузки строятся файлы с каталогами основных объектов, по которым проводится быстрый поиск по БЗ. Такими объектами могут быть, например, адрес, телефон, ФИО.

Работа с БЗ осуществляется с помощью стандартных функций языка ДЕКЛ. Вот перечень основных функций и процедур:

Запись семантической сети

Запись текста загруженного файла

Запись индексов

Извлечение текста любого документа

Извлечение семантической сети любого документа

Удаление текста

Удаление семантической сети

Удаление индексов

Поиск по индексам

Построение каталогов

Представим даталогическую модель БЗ:

Таблица 1. Даталогическая модель.

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

Приведем примеры фрагментов некоторых из файлов БЗ.

19. Мальцева Татьяна Юрьевна Долгопрудный Спортивная д.5, кор.2, кв.110 408-38-15; паспорт XXIV-ик №631339 выдан 28.03.1985 ОВД Долгопрудненского горсовета МО 

Пример 3. Фрагмент файла текстов db_txt.db.

ДОК_(4,"2.TXT")

FIO(МАЛЬЦЕВ,ТАТЬЯНА,ЮРЬЕВНА/0+)  0-(4,FIO)

ДОКУМ_(ПАСПОРТ,XXIV,ИК,N_631339/1+)  1-(4,ДОКУМ_)

ИМЕТЬ(0-,1-)

АДР_(ДОЛГОПРУДНЫЙ,СПОРТИВНЫЙ,ДОМ,5,КОРП.,2,КВ.,110/2+)2-(4,АДР_)

ИМЕТЬ(0-,2-)

ТЛФ_(Т. 408-38-15/3+) 3-(4,ТЛФ_)

ИМЕТЬ(0-,3-)

ОВД_(ОВД/4+)  4-(4,ОВД_)

МИЛ_(4-,ДОЛГОПРУДНЕНСКИЙ/5+)  5-(4,МИЛ_)

ВЫДАН(1-,5-,ГОРСОВЕТ/6+)  6-(4,ACT_)

ДАТА_(#28.3.1985,1985,3,28/7+)  7-(4,ДАТА_)

Когда(6-,7-)

Пример 4. Фрагмент файла семантических сетей db_zzz.db.

ЖЕНА 1_8380

ЖИВОВА 1_8384

ЖИЗНЬ 3_8388

ЖИЛЕНКО 1_8400

ЖИЛЬЕ 1_8404

ЖИТЕЛЬСТВО 2_8412

Пример 5. Фрагмент индексного файла net2.slv.

Структура остальных трех основных файлов БЗ понятны из даталогической модели (Таблица 1). Приведем пример одного из каталогов.

ПАСПОРТ I СБ N_686599                   

ПАСПОРТ II ЛБ N_573947                  

ПАСПОРТ II СБ N_647684                  

ПАСПОРТ III СБ N_738025                 

ПАСПОРТ IV СБ N_516335                  

ПАСПОРТ IV СБ N_560769                  

ПАСПОРТ IV СБ N_670921 

Пример 6. Фрагмент каталога паспортов.

Примеры поиска в действующей системе

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

FIO(Мальцев, Татьяна, Юрьевна/0+)

Так же формируется внутренняя вершина:

0-(4, FIO)

Где «4» - это номер документа.

Допустим, у нас возникла задача поиска FIO в четвертом документе. После того, как СС этого документа будет загружена в РП, достаточно будет воспользоваться следующим условием:

IF X1(4,FIO) FIO(X2,X3,X4/X1) THEN В:A(X2,X3,X4);

Т.е. будет осуществлен поиск по всем фрагментам в РП, в результате которого будет найден фрагмент четвертого документа, в котором в правой части стоит «FIO». Далее из него будет извлечена вершина X1 (в нашем примере она примет значение «0-»), и с помощью нее мы найдем нужный нам фрагмент, значение которого будут переданы в вершины Х2, Х3, Х4 (в нашем примере Х2 примет значение «Мальцев», Х3 – «Татьяна», Х4 - «Юрьевна»). Далее оператором «A:» вершины (их значения) будут выведены на экран.

Примерно так же происходит и более сложный поиск. Предположим, нам необходимо узнать адрес, по которому проживает человек по фамилии Мальцев. Для этого необходимо будет воспользоваться информацией, которая содержится в индексном файле net2.slv (или в каталоге ФИО). Там мы найдем смещение в файле набора документов net2.ind, по которому находится перечень документов, в которых встречалась фамилия «Мальцев». Далее СС этих документов будет загружена в РП, в котором и будет осуществляться поиск по условию:

IF FIO(Мальцев,_,_/X1) Иметь(X1,X2) АДР_(X3,X4,X5,X6,X7,X8,X9,X10,X11/X2)

THEN B:A(X3,X4);

Естественно, в ДЕКЛе есть более удобные механизмы вывода вершин, чем выше описанный, где для совпадения необходимо перечислить все вершины фрагмента, которые необходимо найти. Видно, что для связи объектов используется отглагольная форма «Иметь», кроме этого могут использоваться любые другие формы: «Жить», «Быть», «Играть» и т.д. –  для РСС нет ограничений в различных способах связи объектов.

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

Удаление и изменение документа

Теперь представим, что у нас возникла необходимость удалить какой-либо документ. Для этого нам надо удалить этот документ из файла с текстами, при этом необходимо открыть файл db_txt.db, в котором находятся все тексты, найти нужную строчку, после этого удалить текст всего документа и, начиная с этой строчки, дописать в файл все оставшиеся документы. При их смещение изменится, а следовательно придется перестраивать файл с типизированным текстом заново, что приведет к существенным временным затратам. Тоже самое придется сделать с файлом семантических сетей db_zzz.db. Так же придется вносить изменения в файл net2.slv и net2.ind. И все эти операции придется выполнять при удалении любого документа. В данный момент в системе реализован следующий механизм удаления – удаляется не сам документ, а его образ, т.е. физически все данные, которые находятся в этом документе остаются «лежать» в файлах, при этом они становятся недоступными для всех аналитических режимов и не могут являться результатом поиска. Система просто будет считать, что этого документа нет. К сожалению, такой путь ведет к тому, что размеры файлов с данными будут расти, расти до тех пор, пока файловая система будет позволять дописывать вышеперечисленные файлы. Понятно, что при этом время открывания и чтения этих фалов будет расти в алгебраической прогрессии.

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

Структура БЗ в реляционной СУБД

Теперь попытаемся спроектировать структуру БЗ нашей системы,  учитывая то, что она будет реализована в современной реляционной СУБД (InterBase, MsSQL, MySQL, Oracle и т.п.). В отличие от вышеописанной модели, где для хранения данных используется шесть файлов, одновременный поиск по которым невозможен, эти СУБД могут связать различные файлы, если  существует  поле,  общее для всех файлов. (Поле - это единственный вход, такой как цифровой код или имя; запись - это группа полей, например, имя, адрес и номер телефона;  файл  -  коллекция записей, таких как список из сотрудников компании). В реляционной СУБД можно получить доступ к нескольким  отдельным файлам сразу. При помощи одного запроса можно найти один файл, который будет содержать описание части продуктов для продажи; другой, содержащий  все  отосланные накладные, и третий, описывающий заказчиков, если каждый файл содержит общее поле (например, номер  кода  части  продуктов). Эта информация может быть использована для отсылки письма каждому заказчику, который всегда заказывает некоторую часть продуктов.

         Базы данных, состоящие из плоских файлов, не связывают отдельные файлы. В  СУБД, построенной по принципу плоского файла, нельзя устанавливать связи между файлами. А в одном файле нельзя практически поддерживать записи и по заказчикам, и по накладным, и  по  инвентарным спискам [8].

 Поскольку быстрый поиск является основным требованием и основным преимуществом СУБД, то можно отказаться от типизированных файлов db_txt.dbi и db_zzz.dbi. Данные, которые хранятся в файлах db_txt.db и db_zzz.db можно объединить, поскольку они являются характеристикой одной и той же сущности «Документ». Так же, для ускорения работы можно отдельно хранить заголовок документа, поскольку в чаще всего отображаются не документы, а именно заголовки, которые представляют собой первые несколько слов документов. Файлы net2.slv и net2.ind представляют собой единую сущность «Слово», которая характеризуется самим словом, частотой и списком документов, в котором оно встретилось. Характеристика «частота» используется для того, чтобы показать сколько раз то или иное слово встречается во всей БЗ, соответственно, когда  в результате удаления какого-то документа эта характеристика становится равной нулю, это слово можно удалить. Для создания экземпляра сущности «Слово», необходимо при загрузке каждого документа разбирать его,  преобразовывать каждое слово в нормальную форму (единственное число, мужской род, именительный падеж для существительных), и уже после этого заполнять соответствующие таблицы.

Представим даталогическую модель такой БЗ:

Таблица 2. Даталогическая модель

Схема такой базы данных представлена на рисунке 1:

Рис. 1. Схема Базы Знаний.

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

Преимущества новой БЗ в СУБД

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

Во-первых, проблема удаления и изменения документов решается сама собой. Поскольку хранить информацию о смещениях теперь не имеет смысла, удаление или изменение скажется только на частоте слов, которые встречаются в этом документе. Но эта проблема решается очень просто: в таблице «Список документов» удаляются все пары код_слова-код_документа, которые относятся к данному документу, в таблице «Слова» уменьшается частота удаляемых слов (или они полностью удаляются, если частота становятся равной нулю) и удаляется сам документ. Т.е. сразу решается основная проблема старой технологии – появляется возможность физического удаления любого документа или целой группы документов.

Во-вторых, значительно возрастет скорость поиска, поскольку одним запросом можно будет проводить поиск по нескольким таблицам сразу. Не говоря уж о возможности использования вложенных запросов, которые позволят выполнять многоуровневый поиск за один сеанс связи с СУБД.

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

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

Примеры поиска в новой системе

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

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

SELECT docs.sem_set

FROM  docs

WHERE docs.id_doc=5

Теперь найдем СС документов, в которых встречается слово «Мальцев». Если СУБД полностью поддерживает стандарт SQL/92 [9], а также возможность использования вложенных подзапросов, то этот запрос будет выглядеть следующим образом.

SELECT docs.sem_set

    FROM docs

    WHERE docs.id_doc in (

SELECT doc_list.id_doc

FROM  doc_list, words

WHERE words.word=”Мальцев”

and words.id_word=doc_list.id_word

                            )

Иначе придется выполнять этот запрос в два этапа: результатом первого этапа будет список id документов, в которых встретилось слово «Мальцев», результатом второго будет уже список СС.

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

Удаление документа

А теперь рассмотрим пример удаление документа из базы. Пусть это будет документ под номером 3. Удаление проходит в пять этапов:

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

UPDATE words

SET words.freq = words.freq –

(SELECT sum(1)FROM doc_list

WHERE doc_list.id_doc=3 and

doc_list.id_word=words.id_word

GROUP BY doc_list.id_word );

Удаление всех записей в doc_list, которые относятся к этому документу.

DELETE FROM doc_list WHERE doc_list.id_doc=3;

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

DELETE FROM words WHERE words.freq=0;

Удаление всех записей в каталогах, которые относятся к этому документу.

DELETE FROM cat_FIO WHERE cat_FIO.id_doc=3;

DELETE FROM cat_pass WHERE cat_FIO.id_pass=3;

Удаление текста, заголовка и СС документа.

DELETE FROM docs WHERE docs.id_doc=3;

Подведение итогов.

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

Также был найден способ синтеза СУБД и БЗ. Хотя говорить о том, что мы создали  Систему Управления Базами Знаний (СУБЗ) еще рано по той причине, что функцию управления Знаниями все еще выполняет ДЕКЛ, в то время, как СУБД выполняет лишь роль хранилища данных.

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

Литература

1. [Кузнецов И.П., 1988]

2. [Григорьев Ю.А., Ревунков Г.И., 2002]

3. [Кузнецов И.П., Шарнин М.М., 1988]

4. [Рабинович Б.И., 2003]

5. [Кузнецов И.П., 1986]

6. [Кузнецов И.П., Мацкевич А.Г., 2003]

7. [Кузнецов И.П., Мацкевич А.Г., 2001]

8. [Джон Блэкфорд]

9. [Кузнецов С.Д., 1999]