KorNet
Корочков А.В.
KorNet - модель данных и система
программирования
семантической сети для платформы
Win32/PC
// Методы и средства управления
технологическими
процессами: Сб. тр. III Междунар.науч.
конф. -
Саранск: Изд-во Мордов. ун-та, 1999. -
С.148-152.
А.В.Корочков
Описывается модель данных и основанная на ней система программирования, которая позволяет реализовать семантическую (ассоциативную) сеть как в оперативной памяти компьютера - обозначается АС (Ассоциативная Сеть), так и в его внешней памяти – обозначается АСБД (Ассоциативно-Сетевая База Данных). Может быть использована при программировании на языке С++ как средство для представления понятий (знаний) в системах искусственного интеллекта. Является развитием системы KorNet для MS/PC DOS [1].
Под моделью данных в статье подразумевается совокупность типов данных и операций над ними. Для построения семантической сети в системе KorNet используются следующие три типа данных или сущности: именующая(имя), соединяющая (соединительный объект) и атрибут.
Имя - совокупность символов, входящих в ограниченный набор. Символьное наполнение имени служит средством различения имен. С точки зрения программной реализации (языка С++) имеется два типа имен: строка символов произвольной длины (в АСБД до 2 147 483 647 символов), состоящая из букв английского и/или русского алфавита и/или цифр (далее - строка), и целое неотрицательное число (unsigned long) от 0 до 4294967295 (далее - число). При достаточности с точки зрения модели одного типа (строки), второй введен для обеспечения более эффективной реализации в тех случаях, когда программисту не важно мнемоническое значение имени.
Соединительный объект - базовая сущность, которую можно представить, как нечто, состоящее из носителя с неопределенной (с точки зрения сети) внутренней структурой и неограниченного числа внешних стыковочных узлов, к которым могут быть присоединены атрибуты. Для обозначения важности наличия именно стыковочных узлов у такого объекта он называется узлом.
Атрибут - составная сущность, построенная по принципу ассоциативной пары "ключ-значение", в которой в качестве ключа может выступать только имя, а в качестве значения - либо имя, либо узел. В последнем случае получается однонаправленная связь между исходным узлом и тем, который является значением атрибута. Исходя из того, что ключ может быть только именем, атрибут представляется как составная сущность, имеющая имя (первый элемент ассоциативной пары) и значение (2-й элемент пары). С точки зрения языка реализации (С++) имеется 3 типа значений: указатель на строку, число (реализация имени, см. выше) и ссылка на узел (как другой, так и тот же самый, к которому присоединен атрибут). Система допускает интерпретацию строки как названия функции, находящейся в динамически загружаемой библиотеке, для чего поддерживается специальная операция запуска таких функций ( из Procs.dll или библиотеки, заданной значением атрибута с именем "lib" того же узла, к которому присоединен атрибут, задающий имя вызываемой функции).
Помимо использования в атрибуте имя может также сочетаться с узлом, т.е. именовать узел. Именованный узел в KorNet называется атомом.
В контексте узла (множестве его атрибутов) имена атрибутов должны быть уникальными, чтобы обеспечить различимость атрибутов узла. Для представления в контексте узла однотипной информации, т.е. одноименных атрибутов с неодинаковыми значениями, используется особое применение одного из возможных имен. В качестве такого зарезервированного имени выбрано числовое имя 0. Система допускает наличие в контексте любого узла неограниченного количества одноименных атрибутов с таким именем. Как следствие значения таких атрибутов, условно называемых далее "безымянными", могут быть получены только их последовательным перебором. Вне контекста узла, т.е. у разных узлов, одноименные атрибуты с одинаковыми значениями называются совпадающими, а с неодинаковыми – противоречащими.
Система поддерживает следующие операции над выделенными типами данных и их конгломератами: создание, удаление, изменение, поиск, получение (просмотр), копирование, обобщение, выявление различий, наследование и отождествление. Последние пять операций вовлекают в действие два исходных узла, а остальные работают с одним исходным узлом. Операции с двумя исходными узлами называются межузловыми, а с одним – одноузловыми. Сфера действия как тех, так и других операций может быть ограничена контекстом узла или выходить за его пределы, т.е. операция может распространяться на другие узлы и их атрибуты, первоначально не заданные как объекты операции. Последняя ситуация может возникнуть в том случае, если значением хотя бы одного атрибута узла, первоначально вовлеченного в операцию, является узел. Операции, не выходящие за контекст исходного узла, называются узловыми, а выходящие - сетевыми. Каждая из последних 4-х операций может модифицироваться задаваемыми условиями разрешения коллизий с противоречащими атрибутами, условиями, определяющими необходимость присутствия и/или отсутствия определенных атрибутов у второго узла, типом операции (узловая или сетевая) и типом результата операции. Как результат межузлового взаимодействия может быть задано отсутствие модификации задействованных в операции узлов (тестовый режим), модификация первого узла, модификация нового (третьего) узла или слияние исходных узлов. При слиянии обращение к одному из объединенных узлов одновременно приводит к обращению к другому узлу и, соответственно, наоборот, что позволяет сохранить все ранее существовавшие в сети ссылки на исходные узлы правильными без их корректировки. Далее упомянутые выше операции рассматриваются подробнее.
Операция создания может быть применена к узлам, как именованным, так и неименованным, и к атрибутам. Имя создается в процессе создания именованного узла или атрибута в качестве собственно имени или значения атрибута. Отдельная операция создания имени не выделяется, т.к. имя вне связи с называемым объектом, будь то узел, атрибут или его значение, не используется. Соответственно в системе существуют операции создания узла и присоединения атрибута к узлу. После создания узел не имеет атрибутов.
Следующая операция - удаление - также может быть применена к атрибутам и узлам, но при этом не допускается применение операции к атомам. При удалении узла удаляются и все его атрибуты. Если значением удаляемого атрибута является узел, то при сетевом (полном) удалении и отсутствии других ссылок на этот узел, он также становится объектом удаления.
Операция "изменение" применяется явным образом при изменении имени атрибута (переименование) и неявно при присоединении к узлу атрибута с существующим уже в контексте узла именем, но с другим значением.
Операция поиска применяется к атому или определенному значению среди множества значений всех либо только безымянных атрибутов какого-либо узла.
Операция получения применяется к значениям атрибутов.
Операция копирования применяется к узлам (при копировании атома его имя не копируется, т.е. его копия будет безымянным узлом). Операция реализована в сетевом варианте, т.е. если значением какого-либо атрибута копируемого узла является также узел, то по отношению к последнему будет применена такая же операция копирования, как и к исходному узлу.
Операция обобщения выявляет совпадающие атрибуты двух исходных узлов (пересечение множеств атрибутов). Реализована в узловом и сетевом вариантах.
Как следует из названия, следующая операция выявляет различающиеся атрибуты первого исходного узла по отношению ко второму (разность множеств атрибутов). Также реализована в узловом и сетевом вариантах.
Операция наследования объединяет атрибуты двух исходных узлов, при этом противоречащие атрибуты берутся только от первого узла. Имеет смысл только в узловом варианте.
Операция отождествления объединяет атрибуты исходных узлов при условии отсутствия противоречащих атрибутов. Имеет смысл только в сетевом варианте и требует слияния исходных узлов.
Кроме описанных выше операций, предполагаемых моделью данных "семантическая сеть", система поддерживает и другие ("немодельные") операции. Наиболее важные из них - это операции обмена данными между сетями, расположенными на разных носителях (АС и АСБД).
Система KorNet не имеет специального языка описания данных. Данные в сеть могут быть введены только процедурно, т.е. путем выполнения описанных выше операций. Последовательность необходимых операций может быть либо запрограммирована, для чего система предоставляет собственный подъязык с единым синтаксисом вызова функции ( в описываемой версии поддерживается 159 макрокоманд, определенных через #define), либо задана в специальной визуальной среде KorNet Walker. KorNet Walker является отдельной программной системой, представляющей собой редактор семантической сети KorNet для платформы Win32. Для визуализации данных сети используется табличный способ представления данных. Система поддерживает множественность путей просмотра сети с отображением данных каждого пути в своем собственном окне. Путь может быть как начат, так и продолжен либо с текущего узла, либо с отмеченного узла. Узлы отмечаются пользователем в процессе прохождения сети. Прохождение может быть также начато со списка всех атомов системы. Посредством KorNet Walker пользователь может просматривать и изменять данные в сети параллельно с выполнением другой программы, работающей с этой же сетью, т.е. работать в режиме отладки сети.
К другим средствам отладки может быть отнесена сетевая операция получения в любой момент выполнения программы форматированного представления содержания сети – снимка. Имеется также отдельная программа, создающая снимок содержания АСБД, расположенной в текущем директории.
В заключение несколько слов об аспектах реализации, касающихся эффективности использования памяти и времени доступа к элементам сети.
Для эффективного использования памяти применяются следующие средства: 1) повторное использование памяти, основанное на полном возврате памяти операционной системе при сетевом удалении как в АС, так и в АСБД, а в АСБД - и на поддержании собственной системы управления использованием свободного места внутри файлов АСБД; 2) использование при реализации типов данных вместо имен строкового типа указателей на них; 3) однократное хранение одинаковых имен строкового типа.
Для уменьшения времени доступа к элементам сети в описываемой версии системы (3.0) используется прямой доступ к узлам в АСБД и специальная хэш-функция для доступа к строковым именам.
1. Корочков А.В. Система программирования "KorNet" // XXIV Огаревские чтения: Тезисы докладов научной конференции: В 3 ч. Ч.3 - Саранск: Изд-во Мордов.ун-та, 1995. - С. 15.
