В статье «Обработка знаний в информационных системах» (см. «Открытые системы», № 7, 2010) был проведен анализ существующих методов представления формализованных данных: среди теоретических подходов были рассмотрены семантические сети, а среди практических – технологии семантической паутины, информационные хранилища и реляционные базы данных. Было показано, что между знаниями и данными нет принципиальной разницы, а выбор конкретного способа представления обусловливается только практическими соображениями разработчиков и делается исходя из того, как часто и как именно будет модифицироваться концептуальная модель информации. Однако все способы имеют один и тот же недостаток — возможна ситуация, когда дальнейшее изменение концептуальной модели потребует корректировки существующих исполняемых модулей. Если речь идет о большой, распределенной системе и нет возможности проконтролировать изменение всех клиентских приложений (например, в случае Semantic Web), то развитие всей информационной системы заходит в тупик.

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

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

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

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

Перечисленные требования сформулированы в терминах систем с двухуровневой архитектурой «клиент-сервер», при которой четко отделены функции хранения информации на сервере и обработки на клиентской стороне. Для проведения более общих рассуждений необходимо сформулировать те же самые требования, но в терминах работы с моделью представления данных или знаний (рис. 1), позволяющей осуществлять следующие базовые действия: чтение модели данных; изменение модели данных; чтение данных; изменение данных.

 

 

Рис. 1. Взаимодействие с моделью данных

 

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

Новая модель

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

 

 

Рис. 2. Пример фрагмента сети

 

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

 

Рис. 3. Фрагмент сети вокруг нулевого узла

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

Очевидно, что можно организовать бесконечномерное множество узлов, однозначно определяемых структурой своих прямых и косвенных связей с нулевым узлом. То есть, зная структуру этих связей, можно двигаться от нулевого узла и найти требуемый, причем он будет определен однозначно. Такие однозначно определяемые узлы можно использовать для обозначения любых понятий: типов объектов и атрибутов, связей, словарных значений и т. д. Это позволит, например, вместо терминов «фамилия», «имя», «отчество» использовать ссылки на конкретные однозначно определяемые узлы, а вместо семантических отношений «муж», «жена» и т. д. ссылаться на соответствующие однозначно определяемые узлы. Под ссылкой узла A на узел B понимается существование узла C, от которого исходят дуги к A и B.

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

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

Получается, что модель хранит не только сведения о предметной области системы, но и все остальные «универсальные» константы: числа, строки, даты и т. д, при этом принципы работы с прикладными и универсальными данными одинаковы. В качестве примера можно рассмотреть поиск всех людей с фамилией «Иванов». Для этого необходимо сначала найти однозначно определяемый узел-понятие «Фамилия» и узел-значение «Иванов», а затем все остальные узлы, связанные с «Фамилия» и «Иванов». Структура взаимосвязей определяется клиентским приложением и может варьироваться. Получается, что любой запрос на поиск информации представляется в виде структуры искомых фрагментов сети, задаваемых аналогично самой сети, отталкивающихся от нулевого узла и содержащих конечное число узлов.

 

Рис. 4. Представление таблиц значений функций

Аналогичным образом могут быть представлены таблицы значений функций — каждая строка каждой таблицы будет выглядеть в виде фрагмента графа из семи узлов (рис. 4).

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

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

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

Реализация модели

Множество узлов и связей между ними представимо как множество троек чисел, каждая из которых соответствует некоему узлу A, от которого исходят связи к узлам B и C. Первое число тройки является идентификатором узла A, а два других числа — идентификаторами узлов B и C. Начальный узел сети задается тройкой чисел, равных нулю. Предложенной модели хранения информации достаточно для работы с сетью, накопления данных и выполнения запросов, но с практической точки зрения удобно реализовать еще две вспомогательные структуры, предназначенные для работы с уникально определяемыми узлами, которые соответствуют атомарным значениям (числам, строкам, данным, функциям и т. д.) или используются при моделировании предметной области. Первая такая структура данных — хеш-таблица, содержащая идентификаторы узлов для различных атомарных значений. Если приложению необходимо получить идентификатор узла, соответствующего, например, числу 123, то оно обращается к данной хеш-таблице и по ключу «число 123» получает числовой идентификатор требуемого узла. Вторая вспомогательная структура данных тоже является хеш-таблицей и позволяет выполнить обратную операцию: получить по уникальному идентификатору узла сопоставленное с ним атомарное значение. Эти две таблицы служат для удобства работы и могут быть удалены, поскольку каждое приложение «знает», как, отталкиваясь от начального узла, найти требуемый однозначно определяемый узел, и может это проделать самостоятельно.

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

Физическая реализация трех перечисленных структур данных может быть различной, вплоть до РСУБД, но для достижения высокой скорости работы лучше использовать специализированные методы хранения и обработки информации, похожие на подходы, разработанные при построении хранилищ троек (TripleStorages), используемых в семантической паутине.

Множество узлов и связей хранится как набор B-деревьев, содержащих одни и те же множества троек (A,B,C), но использующих разные способы упорядочения. Как уже было сказано, первое число (A) тройки является уникальным идентификатором узла, а два других числа (B и C) — идентификаторами связанных узлов, среди которых можно выделить большее и меньшее число. Будем считать, что в каждой тройке всегда выполняется B>=C, и тогда получается, что каждая тройка состоит из идентификатора узла (A), большего идентификатора связанного узла (B) и меньшего идентификатора связанного узла (С). Наличие трех компонентов дает шесть различных способов сравнения двух троек (ABC, ACB, BAC, BCA, CAB и CBA) и, соответственно, все множество узлов и связей хранится в виде шести B-деревьев. Далее эти деревья будут называться по используемому критерию сортировки (ABC-дерево, ACB-дерево и т. д.).

Выполнение запроса происходит по указанной ранее схеме, но при переборе значений идентификаторов используются B-деревья, отсортированные необходимым образом. Это позволяет существенно сузить пространство поиска и ускорить работу всего алгоритма. Например, пусть происходит поиск троек узлов (P,Q,R), связанных как узлы «0», «1» и «1-1» (рис. 3), причем P сопоставляется с узлом «0», Q — с узлом «1» и R – с узлом «1-1». Идентификатор узла P всегда находится быстро (используется ABC-дерево), а вот поиск идентификаторов Q и R может происходить двумя способами, использующими различные деревья сортировки. Первый вариант — сначала искать Q (используется BCA-дерево), а затем R (используется BCA-дерево). Второй вариант — перебирать узлы R (у них одна связь указывает на начальный узел и можно использовать BCA- и CBA-деревья), затем определять Q и анализировать его связи (они должны указывать на начальный узел всей сети (P), а для проверки использовать любое из деревьев). Очевидно, что первый вариант выполнения запроса перебирает меньшее число вариантов и работает быстрее второго.

Применение модели

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

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

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

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

***

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

Константин Селезнев (skostik@relex.ru) — старший инженер-программист НПП «Релэкс» (Воронеж).