Программные продукты и системы, 2011, № 3

Программные продукты и системы
№ 3, 2011 г.

3

УДК 004.98, 004.652.4

ПОСТРОЕНИЕ ХРАНИЛИЩ 

ОНТОЛОГИЧЕСКИХ БАЗ ЗНАНИЙ

М.Н. Вехорев; М.Г. Пантелеев, к.т.н.

(Санкт-Петербургский государственный электротехнический университет (ЛЭТИ),

mvehorev@gmail.com, mpanteleyev@gmail.com)

Описывается проблема хранения онтологически представленной информации в реляционных БД. Хранилище 

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

Ключевые слова: онтологии, организация хранилищ онтологий, реляционная СУБД, технология хранения RDF
триплетов, хранилище онтологий, язык запросов семантического Веб, движок запросов RDF.

Концепция и технологии семантического Веб 

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

Ключевым элементом информационных сис
тем (ИС), основанных на технологиях семантического Веб, являются  онтологические базы знаний.
При создании крупных информационных систем 
по мере роста объемов используемых онтологий 
их хранение в плоских файлах оказывается непродуктивным. В связи с этим актуальна проблема 
организации эффективных хранилищ онтологических баз знаний (RDF-хранилищ).

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

в семантическом Веб

Под онтологией, согласно общепринятому оп
ределению, понимается явная спецификация концептуализации.

Для автоматической обработки разделяемых 

знаний консорциумом W3C разработаны единые
стандарты
их представления:
RDF
(Resource 

Description Framework) и основанный на нем язык 
веб-онтологий OWL (Ontology Web Language). Под 
ресурсом понимается любая сущность, которой 
сопоставлен универсальный идентификатор URI
(Universal Resource Identificator). Основной конструкцией языка RDF является утверждение, задаваемое тройкой <субъект> <предикат> <объект>
(RDF-триплет), например: <стол> <цвет> <черный>. Использование URI для задания субъектов 
и свойств позволяет связывать отдельные утверждения (RDF-триплеты) в сколь угодно сложные 
семантические сети, имеющие единую интерпретацию в открытой сетевой среде.

Простейшая
форма
хранения онтологий –

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

Однако данный подход имеет недостатки: существенный рост затрат оперативной памяти при работе с большими онтологиями (более 106 триплетов)
вследствие полной загрузки OWL-файла, а также
значительное увеличение времени загрузки OWLфайлов по мере роста количества используемых 
онтологий. Это не позволяет использовать данный 
подход при создании крупных ИС и обусловливает необходимость построения RDF-хранилищ на 
основе реляционных СУБД.

Особенности RDF-хранилищ

Под RDF-хранилищем понимается информа
ционная подсистема, предназначенная для хранения RDF-триплетов и выполнения запросов к ним.

Основными функциями RDF-хранилища яв
ляются:

 организация хранения онтологий в реляци
онной БД с использованием реляционных представлений;

 предоставление программного интерфейса 

для извлечения информации из хранимых онтологий посредством языка структурированных запросов SPARQL или специального API;

 поддержка
функций администрирования 

хранимых онтологий: добавление, удаление, модификация и распределение прав доступа.

Эффективное RDF-хранилище должно удов
летворять следующим требованиям:

 высокая производительность – минимиза
ция времени выполнения запросов;

 минимальные затраты памяти (дискового 

пространства) для хранения онтологий;

 универсальность подхода – возможность

хранения онтологий любой структуры.

При разработке конкретных ИС важны время 

и сложность развертывания RDF-хранилища, а 
также его стоимость.

Обобщенная архитектура RDF-хранилища

В состав RDF-хранилища входят две основные

подсистемы: подсистема хранения онтологий на 

Программные продукты и системы
№ 3, 2011 г.

4

основе реляционной СУБД и подсистема трансляции входных запросов в SQL-запросы (см. рис.).

В качестве подсистемы хранения онтологий

могут использоваться как коммерческие СУБД 
(Oracle, MS SQL Server и др.), так и свободно доступные (PostgreSQL, MySQL и др.).

Прикладные информационные системы могут 

взаимодействовать с RDF-хранилищем посредством специального API или структурированных 
SPARQL-запросов. SPARQL – это стандартный
язык запросов к RDF-данным. Например, простой 
SPARQL-запрос для получения имени и номера 
паспорта некоторой персоны имеет вид:
SELECT ?name ?number
WHERE{ ?someone rdf:type :Person. 

?someone :name ?name.
?someone :passportNumber ?number.}

Отношение rdf:type
является стандартным 

отношением языка RDF и означает принадлежность элемента классу. Класс :Person, отношения
:name и :passportNumber в данном примере взяты из некоторого пространства имен по умолчанию.

Подсистема трансляции входных запросов в 

общем случае может включать два компонента:

 обработчик API-вызовов, предоставляющий

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

 транслятор SPARQL↔SQL, выполняющий

преобразования SPARQL-запросов в SQL-запросы 
и обратные преобразования результатов, возвращенных SQL-запросами в результат SPARQL-запроса. 

Недостаток специального API состоит в при
вязке к конкретному языку программирования. 
Пример такого API – библиотека Jena. Интерфейс
SPARQL-запросов является универсальным решением, не зависящим от языка программирования.
Поэтому рассмотрим работу с RDF-хранилищем с 
использованием именно этого интерфейса. Преобразования SPARQL-запросов в набор SQL-запросов 
будем обозначать SPARQL→{SQL}.

Очевидно, что формальная грамматика преоб
разования SPARQL→{SQL} зависит от принятой в 
RDF-хранилище схемы РБД. Вопросы оптимиза
ции функционирования транслятора SPARQL↔
↔SQL рассмотрены, в частности, в [2, 3]. Настоящая статья посвящена определению зависимости 
производительности RDF-хранилища от принятой 
схемы РБД. 

Организация хранения онтологий в БД

Можно выделить два базовых подхода к орга
низации хранения онтологий в РБД:

1) использование единственной таблицы для 

хранения всех RDF-триплетов (подход «вертикальная таблица»);

2) отображение
иерархии онтологических 

сущностей (классов, свойств, экземпляров) в схему РБД.

В соответствии с первым подходом все RDF
триплеты хранятся в унифицированной таблице 
БД, содержащей в общем случае четыре колонки: 
«граф», «субъект», «объект» и «предикат». Данный подход реализован, в частности, в Jena SDB и
3store. Он характеризуется достаточно высокой 
временной сложностью выборки RDF-триплетов.

Особенностью второго подхода является оп
ределение схемы БД в соответствии с конкретной 
предметной областью, что позволяет оптимизировать выполнение запросов. Реализация данного 
подхода для больших онтологий предполагает 
создание большого числа таблиц БД со сложными 
связями между ними. Известно несколько частных 
решений, отличающихся способом формирования 
схемы БД [4, 5]. 

Анализ факторов, влияющих 

на эффективность RDF-хранилищ

Эффективность RDF-хранилища при исполь
зовании SPARQL-запросов
определяется двумя 

основными взаимосвязанными факторами: принятой схемой БД и грамматикой преобразования 
SPARQL→{SQL}. 

Исходя из представленной на рисунке обоб
щенной 
архитектуры 
RDF-хранилища,
время

Тsparql обработки SPARQL-запросов в общем виде определяется формулой

Тsparql=Тtrans+Tsql_seq,
(1)

СУБД

Транслятор SPARQL↔SQL

RDF-хранилище

ИС

SPARQL-запрос

API-вызовы
Обработчик API-вызовов

SQL-запрос

Результат 
запроса

RDF-данные

Архитектура RDF-хранилища

Программные продукты и системы
№ 3, 2011 г.

5

где Тtrans – время трансляции SPARQL-запроса в 
последовательность SQL-запросов в соответствии 
с принятой трансформационной грамматикой; 
Tsql_seq – время обработки СУБД построенной 
последовательности SQL-запросов.

Введем определения и примем базовые допу
щения, необходимые для анализа временных затрат на обработку SPARQL-запросов.

SQL-запрос в общем случае имеет следующую 

структуру:

SELECT
<кортеж 
выбираемых
полей>

FROM <кортеж таблиц> WHERE <кортеж условий>.

Построение SQL-запроса на основе входного 

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

Пусть T – среднее время формирования эле
ментов кортежа выбираемых полей и кортежа
условий в процессе построения SQL-запроса. Тогда 
время формирования SQL-запроса линейно зависит от числа элементов в кортежах выбираемых
полей и условий.

Допустим, что обработка SQL-запроса требует 

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

Обозначим T среднее время выборки записи 

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

Зависимость времени трансляции SPARQL→

{SQL} от принятой трансформационной грамматики оценивается формулой

N

i 1

Тtrans
 
Тsql _def  i




,
(2)

где N – количество результирующих запросов 
SQL, 
получаемых
в 
результате 
трансляции;

Tsql_def i – время построения i-го SQL-запроса.

Зависимость времени формирования очеред
ного SQL-запроса от количества полей, содержащихся в кортеже результата, и количества условий
будет следующей:

Тsql _def
Nres*Тres _def

Ncond*Тcond _def.





(3)

Исходя из принятых допущений, можно запи
сать:

T
Тres_def
Тcond_def
 

.
(4)

Подставив (3) и (4) в (2), получим

N

i 1

N

i 1

Тtrans
 
Тsql _def  i

 
(Nres i
Ncond i)*T  .
















(5)

Аналогично зависимость времени обработки 

набора SQL-запросов может быть выражена формулой

N

i 1

Tsql _seq
 k
Тsql i



 
,
(6)

где k – коэффициент схемы БД, численно равный 
количеству таблиц БД (Ntbl); N – количество результирующих SQL-запросов, построенных при
трансляции; Тsql i – время выполнения i-го SQLзапроса к СУБД.

Время, необходимое на выполнение одного 

SQL-запроса, может быть оценено по формуле



Тsql
Тrecord
Тfield


,
(7)

где Trecord – время на анализ записей в таблице;
Tfield – время на сопоставление условий запроса с 
текущими значениями в строке таблицы. 

Исходя из принятых допущений, можно запи
сать:

Тrecord
Ntbl _rec*T

,
(8)

где Ntbl_rec – количество записей в таблице БД;

Тfield
Ntbl _fld*T

,
(9)

где Ntbl_fld – количество проверяемых условий в 
SQL-запросе.

Подставив (7–9) в (6), получим:

N

i 1

Tsql _seq
 k
Тsql i










N

i 1

Ntbl*
Тrecord
Тfield i







(10)




N

i 1

  Ntbl*
Ntbl _rec
Ntbl _fld  i*T .








Подставив (5) и (10) в (1), получим:

N

i 1

Тsparql
(Nres i
Ncond i)*T   Ntbl*












N

i 1

*
Ntbl _rec
Ntbl _fld  i*T






.
(11)

Формула (11) выражает зависимость времени

выполнения SPARQL-запроса от особенностей 
принятой схемы БД и соответствующей трансформационной грамматики.

Рассмотрим влияние схемы БД на трансфор
мационную грамматику для двух вариантов схем –
«вертикальная таблицa» и «таблицы свойств классов». Схема БД «вертикальная таблица» предполагает создание единой таблицы для хранения 
RDF-триплетов, а схема БД «таблицы свойств 

Программные продукты и системы
№ 3, 2011 г.

6

классов» – отдельных таблиц для хранения экземпляров каждого из классов онтологии.

Для сравнения этих вариантов рассмотрим 

простую онтологию, содержащую четыре класса –
classHuman, classMan, classWoman, classChildren.
Будем считать, что каждый из них имеет два экземпляра, за исключением родительского класса 
classHuman. Каждый экземпляр класса обладает 
свойствами propertyName и propertyAge.

Структура хранения данной онтологии на ос
нове схемы «вертикальная таблица» представлена 
в таблице 1. 

Таблица 1

table_Triples

Subject
Predicate
Object

classHuman
subClassOf
classThing

classMan
subClassOf
classHuman

classWoman
subClassOf
classHuman

classChildren
subClassOf
classMan

classChildren
subClassOf
classWoman

classHuman
hasProperty
propertyName

classHuman
hasProperty
propertyAge

instanceMan1
instanceOf
classMan

instanceMan2
instanceOf
classMan

instanceWoman1
instanceOf
classWoman

instanceWoman2
instanceOf
classWoman

instanceChild1
instanceOf
classChildren

instanceChild2
instanceOf
classChildren

instanceMan1
propertyName
Andry

instanceMan2
propertyName
Maxim

instanceWoman1
propertyName
Maria

instanceWoman2
propertyName
Julia

instanceChild1
propertyName
Michael

instanceChild2
propertyName
Regina

instanceMan1
propertyAge
35

instanceMan2
propertyAge
46

instanceWoman1
propertyAge
45

instanceWoman2
propertyAge
33

instanceChild1
propertyAge
16

instanceChild2
propertyAge
8

Реализация хранения данной онтологии на ос
нове схемы «таблицы свойств классов» предполагает создание таблицы иерархии классов онтологии (табл. 2) и отдельных таблиц для каждого из 
классов (табл. 3–5).

Таблица 2

table_Hierarhy

ID_Hierarhy
subClass
Class
tableName

1
classHuman
classThing

2
classMan
classHuman
table_classMan

3
classWoman classHuman
table_classWoman

4
classChildren classMan
table_classChildren

5
classChildren classWoman table_classChildren

Таблица 3

table_classMan

ID_Man
Name
Age

1
Andry
35

2
Maxim
46

Таблица 4

table_classWoman

ID_Woman
Name
Age

1
Maria
45

2
Julia
33

Таблица 5

table_classChildren

ID_children
Name
Age

1
Michael
16

2
Regina
8

Примеры преобразования 

SPARQL→{SQL}

Рассмотрим возможные варианты трансляции 

SPARQL-запросов к онтологии в набор SQL-запросов в зависимости от используемой схемы БД на 
конкретных примерах и оценим влияние принятой 
схемы 
БД 
на
сложность
преобразования 

SPARQL→{SQL}.

Пример 1. 
SELECT ?x {WHERE ?x a classMan} // Опре
деление всех экземпляров класса

Преобразование SPARQL→{SQL} для схемы 

БД «вертикальная таблица» включает следующие 
шаги.

1. Определение 
всех 
подклассов 
класса 

classMan:

SELECT result1(subject) FROM table_Triples 
WHERE 
(predicate='subClassOf' 
AND 

object='classMan') OR (subject='classMan');

2. Выбор экземпляров классов, определенных 

на шаге 1:

SELECT result2(subject) FROM table_Triples 
WHERE 
predicate='instanceOf' 
AND 

object=result1(subject);

3. Выбор значений свойств propertyName эк
земпляров, полученных на шаге 2:

SELECT 
result3(subject,
object) 
FROM 

table_Triples 

WHERE 
(subject= 
result2(subject)) AND 

(predicate='propertyName');

4. Выбор значений свойств propertyAge эк
земпляров, полученных на шаге 2:

SELECT 
result4(subject,
object) 
FROM 

table_Triples 

WHERE 
(subject= 
result2(subject)) AND 

(predicate='propertyAge');

5. Объединение результатов, полученных на 

шагах 3 и 4:

JOIN result3,result4 BY subject;
Аналогичное преобразование SPARQL→{SQL}

для схемы БД «таблицы свойств классов» включает следующие шаги.

1. Выбор имен таблиц для класса classMan и 

его подклассов:

SELECT result1(tableName) FROM table_

Hierarhy 

Программные продукты и системы
№ 3, 2011 г.

7

WHERE 
class='classMan' 
OR 
subClass=

='classMan';

2. Выбор значений свойств propertyName, 

propertyAge из таблиц, определенных на шаге 1:

SELECT result2(name, age) FROM result1

(tableName);

Пример 2. 
SELECT ?name WHERE { ?x а classHuman. 

?x propertyAge “35”. ?x propertyName ?name}

// Определение объектов по значению свойства
Преобразование SPARQL→{SQL} для схемы 

БД «вертикальная таблица» включает следующие 
шаги.

1. Определение 
всех 
подклассов 
класса 

classMan:

SELECT result1(subject) FROM table_Triples 
WHERE 
(predicate='subClassOf' 
AND 

object='classHuman') OR (subject='classHuman');

2. Выбор экземпляров классов, определенных 

на шаге 1:

SELECT result2(subject) FROM table_Triples 
WHERE 
predicate='instanceOf' 
AND 

object=result1(subject);

3. Выбор среди полученных на шаге 2 экземп
ляров со значением свойства возраст, равным 35:

SELECT result3(subject,object) FROM table_

Triples 

WHERE 
(subject= 
result2(subject)) AND 

(predicate='propertyAge') AND (object = „35‟);

4. Определение имени экземпляров, если ре
зультат шага 3 не пустой:

SELECT result4(object) FROM table_Triples 
WHERE (subject = result3.subject AND predi
cate='propertyName');

Аналогичное преобразование SPARQL→{SQL}

для схемы БД «таблицы свойств классов» включает следующие шаги.

1. Выбор имен таблиц для класса classMan и 

его подклассов:

SELECT result1(tableName) FROM table_

Hierarhy 

WHERE class='Human' OR subClass='Hu
man';

2. Выбор
экземпляров
со значением поля 

propertyAge, равным 35, из таблиц, определенных 
на шаге 1.

SELECT result2(name) FROM result1(table
Name) 

WHERE age=35;
Пример 3.
SELECT 
?x 
WHERE{ 
?x 
subclassOf 

classHuman} // Определение классов потомком

Преобразование SPARQL→{SQL} для схемы 

БД «вертикальная таблица» содержит такой шаг, 
как выбор из таблицы триплетов всех подклассов 
класса classHuman.

SELECT result1(subject) FROM table_Triples 
WHERE 
(predicate='subClassOf' 
AND 

object='classHuman');

Аналогично
и
преобразование 
SPARQL→

→{SQL} для схемы БД «таблицы свойств классов»: выбор из таблицы иерархии классов всех 
подклассов класса classHuman:

SELECT result1(subClass) FROM table_Hie
rarhy

WHERE class='Human';
Оценки времени выполнения рассмотренных 

запросов на основе формул (5) и (10) в сопоставимых условных временных единицах представлены
в таблице 6, где ВТ – вертикальная таблица, ТСК –
таблица свойств классов. Анализ полученных результатов показывает, что трансляция SPARQLзапросов при втором подходе выполняется приблизительно в три раза быстрее. Время обработки 
последовательностей SQL-запросов во втором 
случае в два раза меньше. 

Таблица 6

Временные затраты на выполнение 

SPARQL-запросов

Этап

Условие

Эталонный запрос
Среднее
значение
Пример 

№ 1

Пример 

№ 2

Пример 

№ 3

Тtrans
(в T)

ВТ
17
15
3
11,7

ТСК
5
5
2
4

Tsql_seq
(в T)

ВТ
98
106
26
76,7

ТСК
44
52
30
42

Полученные результаты позволяют сделать 

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

Обратим внимание, что теоретические оценки 

хорошо согласуются с экспериментальными результатами, представленными в [5–7].

В заключение отметим, что предложенный 

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

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

Программные продукты и системы
№ 3, 2011 г.

8

также на оптимизацию
выполнения SPARQL
запросов к хранилищам, обладающим определенной схемой БД.

Литература

1. Пузанков Д.В. [и др.]. Интеллектуальные агенты, мно
гоагентные системы и семантический Web: концепции, технологии, приложения. СПб: Изд-во «Технолит», 2008. 292 с.

2. Chebotko A. [et al.]. Semantics preserving SPARQL-to
SQL translation // Data & Knowledge Engineering. 2009. Vol. 68. 
Is. 10, pp. 973–1000.

3. Richard Cyganiak. A relational algebra for SPARQL. HP 

Labs, Bristol, 2005.

4. Velegrakis Yannis. Relational Technologies, Metadata and 

RDF. Semantic Web Information Management // Springer-Verlag 
Berlin Heidelberg, 2010, p. 41. 

5. Theoharis Yannis, Christophides Vassilis, Karvounarakis 

Grigoris. Benchmarking Database Representations of RDF/S Stores
// Springer-Verlag Berlin Heidelberg, 2005, pp. 685–701.

6. Yuanbo Guo, Zhengxiang Pan, and Jeff Heflin. An 

Evaluation of Knowledge Base Systems for Large OWL Datasets. 
Computer Science and Engineering Department, Lehigh University, 
Bethlehem, USA, 2004.

7. Hondjack Dehainsala, Guy Pierra, Ladjel Bellatreche. 

OntoDB: An Ontology-Based Database for Data Intensive 
Applications. 
Proc. 
Of 
Database 
Systems 
for 
Advanced 

Applications (DASFAA’2007) // Bangkok, Thailand, 2007.

УДК 681.3.07

ПАРАЛЛЕЛЬНЫЙ ВЫВОД 

В МЕТОДЕ АНАЛИТИЧЕСКИХ ТАБЛИЦ

В.Н. Вагин, д.т.н.; Зо Мьо Хтет 

(Московский энергетический институт (технический университет), vagin@appmat.ru)

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

Ключевые слова: аналитические таблицы, параллельный метод, фиктивная переменная, наибольший общий 

унификатор, подстановка.

Известно, что система дедуктивного вывода 

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

Говоря о стратегии поиска, прежде всего сле
дует упомянуть о стратегиях, основанных на упорядочении (ordering-based strategies). Необходимо 
отметить, что среди них имеются стратегии, ориентированные как на расширение множества 
дизъюнктов для метода резолюции, так и на его 
сокращение путем поглощения. Упорядочение 
здесь понимается как наличие обоснованного порядка выражений, подлежащих процедуре поиска 
вывода. Стратегии, основанные на упорядочении, 
используют поиск только наилучшего (с примене
нием эвристик) и, как правило, не очень восприимчивы к разрешению целей. Однако использование в них семантических (например в семантической резолюции) или поддерживающих (например 
в резолюции множества поддержки) требований 
настраивает поиск на разрешение целей. Стратегии, основанные на упорядочении, являются синтетическими, получаемыми образованием одних 
цепочек вывода из других.

Иной тип стратегий – стратегия редукции 

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

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

Программные продукты и системы
№ 3, 2011 г.

9

на ряд подпространств положен в основу распределенного поиска, в котором существенную роль 
играет организация связи между порциями пространства.

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

Метод 

аналитических таблиц

Настоящий метод является эффективной про
цедурой доказательства теорем и для логики высказываний, и для логики предикатов первого 
порядка. Как и метод резолюции, он относится к 
методам опровержения, то есть когда для доказательства общезначимости формулы A доказывается ее противоречие (¬A) [2, 3]. Но если метод резолюции работает с формулами, представленными 
в конъюнктивной нормальной форме, то метод 
аналитических таблиц оперирует формулами в 
дизъюнктивной нормальной форме. Вывод осуществляется на бинарных деревьях, вершины которых отмечены формулами, причем вершина 
называется концевой, если не имеет потомков, 
простой, если у нее только один потомок, и дизъюнктивной, если два потомка. Каждая ветвь дерева представлена конъюнкцией формул, а само дерево – дизъюнкцией своих ветвей.

Известно, что в методе аналитических таблиц 

четыре правила вывода, два из которых относятся 
к логике высказываний (α, β), а два – к логике
предикатов первого порядка (γ, δ) [2, 3].

Правило α: если формула Х есть α, то к дереву 

надо добавить вершину, отмеченную формулой 
α1, и затем на этой же ветви другую вершину, от
меченную α2:

1

2






, где α – формула конъюнктив
ного типа, состоящая из компонент α1 и α2.

Правило β: если формула Х есть β, надо рас
щепить идущую от вершины β ветвь на две ветви, 
вершину на левой ветви отметить формулой β1, а 

на другой – β2:

1
2

β

β | β , где β – формула дизъюнк
тивного типа, состоящая из компонент β1 и β2.

Правило δ: если формула X есть δ, то к дереву 

надо добавить вершину, отмеченную формулой 
δ(с). Это означает, что к формуле Х применена 
подстановка с вместо всех вхождений переменной 

x в X: 
δ

δ(c) , где δ – формула экзистенционального 

типа, имеющая кванторы  или , c – новый параметр, не входящий в исходную формулу, чья
невыполнимость доказывается. 

Правило γ: если формула X есть γ, то к дереву 

надо добавить вершину, отмеченную формулой 
γ(a). Это означает, что к формуле Х применена 
подстановка а вместо всех вхождений переменной 

x в X:
γ

γ(a) , где γ – формула универсального ти
па, имеющая кванторы  или , a – любой параметр. 

Назовем правила α, β, γ, δ правилами расши
рения таблицы. Доказано, что метод аналитических таблиц обладает непротиворечивостью, то 
есть этим методом невозможно доказать формулу 
и ее отрицание одновременно. Кроме того, метод 
полон, то есть, если формула Х общезначима, то 
она доказуема (выводима) методом аналитических 
таблиц [3, 4].

В общем случае правила расширения таблицы 

недетерминированы. Но в отличие от пропозиционального случая в логике предикатов возможно многократное (в худшем случае бесконечное) 
повторение правил расширения таблицы без получения замкнутого дерева, хотя оно может существовать. Источником такой трудности является 
γ-правило. Если правила α, β, δ применяются 
к формуле X только один раз, то в случае с 
γ-правилом это не так. Предположим, например, 
что формула x1, …, xn F(x1, …, xn) содержит m
констант. Тогда потребуется добавить mn различных замкнутых предложений к пути в таблице 
(функциональные символы в подстановке отсутствуют), то есть количество формул, которое нужно добавить, возрастает экспоненциально в зависимости от количества кванторов.

Для уменьшения недетерминированности вы
бора правил сначала используем все α- и δ-правила (нет ветвления). Затем применим β-правила и 
только после этого γ-правила.

Назовем таблицу атомарно замкнутой, если 

каждая ветвь дерева содержит некоторую атомарную формулу и ее отрицание (то есть контрарную 
пару P и P). Таким образом, если формула Х
общезначима или X невыполнима, то существует атомарно замкнутая таблица для Х.

Метод фиктивных переменных

Для избежания комбинаторных проблем, вы
званных многократным добавлением к пути экземпляров универсальных формул, рассмотрим 
предложенный Р. Джонсоном метод фиктивных
переменных [4].

Вместо 
квантифицированных 
переменных, 

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

Обозначим фиктивные переменные как dx или 

dx, где х – положительное целое число.

Программные продукты и системы
№ 3, 2011 г.

10

Введем несколько определений.
Определение 1 (Редукция). Редукция – упоря
доченная пара вида <d, t>, где d – переменная, t –
терм. Это означает, что t будет подставлен вместо 
фиктивной переменной d в любое множество термов или формул, к которым подстановка применима.

Определение 2 (Подстановка). Подстановка

– конечная последовательность редукций (множество редукций).

Необходимо различать два вида редукций 

<d, t>: константная, где t – константа, и фиктивная, где t – фиктивная переменная. Очевидно, что 
подстановка – это конечная последовательность 
редукций, а унификация определяется обычным 
образом: если имеются термы t и v, содержащие 
переменные, то подстановка ζ, такая, что tζ=vζ, 
называется унификатором для t и v. 

Подстановка ζ={<x1, t1>, …, <xn, tn>} называ
ется идемпотентной, если для 1≤i,j≤n xi не входит 
в ti, поэтому переменные в идемпотентной подстановке не появляются одновременно на левой и 
правой сторонах любой редукции или различных 
редукций [4, 5]. Естественно, что интерес представляют только непротиворечивые идемпотентные подстановки (НИП). Следовательно, всякий 
раз, когда в результате композиции получается противоречивая подстановка θ, где <d1, a>, 
<d1, b>θ, a и b – константы и a≠b, θ будет исключена.

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

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

Опишем схему, позволяющую справиться с 

этой проблемой [4].

Имеем формулу F и подстановку ζ={<x0, t0>, 

<x1, t1>, …, <xn-1, tn-1>}, Fζ – результат применения каждой редукции {<xp, tp>} к F для 0≤p≤n-1, 
то есть в F каждое вхождение xp заменяется на tp.

Унификация формул или множества формул 

подразумевает
унификацию 
соответствующих 

термов в формулах. Например, рассмотрим формулы F(a, x)→G(x) и F(y, b)→G(b), где x и y –

фиктивные переменные. Эти формулы унифицируются подстановкой {<x, b>, <y, a>}. Рассмотрим 
ограниченное множество подстановок. Если любая переменная xp входит в левую часть константной редукции в ζ, это будет ее единственным 
вхождением в ζ. Данное обстоятельство гарантирует, что xp может быть связана только единственной константой, ζ также не содержит тождественных редукций, то есть редукций вида <d, d>. 
Если есть подстановки вида ζ={<d1, d2>} и θ={<d2, 
a>}, то ζθ={<d1, a>, <d2, a>}. Однако ζ={<d1, d2>}
является двунаправленной, так, если θ={<d1, a>}, 
тогда ζθ={<d1, a>, <d2, a>} дает такой же результат. Будем ссылаться на этот процесс как на внесение констант.

В данном случае представляют интерес только 

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

Параллелизм в методе 
фиктивных переменных

Опишем метод, который параллельно пытает
ся построить подстановки, способные замкнуть 
таблицу. Отметим, что в таблице могут существовать пути, не требующие унификации, то есть когда контрарная пара F и F не нуждается в унификации. Если на пути существуют две формулы, 
замыкающие его без унификации, это называется 
константным замыканием. Однако, если на пути 
присутствуют формулы типов F(a, x) и F(y, b), 
где a и b – константы, x и y – фиктивные переменные, то их необходимо унифицировать, то есть
применить к ним подстановку {<x, b>, <y, a>} и 
получить контрарную пару F(a, b) и F(a, b).

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

Как было отмечено, две или более редукций 

являются противоречивыми, если пытаются связать одну и ту же фиктивную переменную с различными константами. Противоречивая подстановка – это подстановка, содержащая одну или 
более пар противоречивых редукций. Рассмотрим 
пути Р1 и Р2 таблицы Т, где путь Р1 может быть 
замкнут после унификации формул F(a, x) и 
F(y, b), а путь Р2 – после унификации формул 
G(a, x) и G(y, c). 

Путь Р1 требует подстановки {<x, b>, <y, a>}

для замыкания, в то время как Р2 требует {<x, c>, 
<y, a>}. Очевидно, что эти подстановки противоречивы, поэтому замыкание путей с ними несостоятельно и невозможно.

Программные продукты и системы
№ 3, 2011 г.

11

Введем еще несколько определений [4].
Определение 3 (П-множество). Возможное 

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

Отметим, что Т′ может быть частью таблицы 

Т, всей таблицей Т или только единственным путем.

Определение 4 (N-множество). Необходимое 

унифицирующее множество N (N-множество) является множеством из П-множеств.

N-множество содержит полное множество 

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

N- и П-множества будут описаны следующим 

образом: N={П0, …, Пn}, где n≥0, N – N-множество, П – П-множество.

Отметим, что N-множество – это множество, 

состоящее из П-множеств, в то время как П-множество – это множество, состоящее из редукций:
П={<d0, t0>, …, <dp, tp>}, где p≥0, di≠dj и di≠tj (i≠j, 
0≤i, j≤p). П-множество – это подстановка, которая 
унифицирует соответствующие аргументы x1, …,
xn и y1, …, yn для двух формул, делая их контрарными. 

У всякого N- и П-множества есть соответст
вующая таблица или подтаблица Т.

Применяя П к формулам на каждом пути в Т, 

получаем контрарную пару формул, замыкая Т. 
Аналогично применение любого из П-множеств в 
N замыкает Т. В итоге получаем замкнутую таблицу Т.

Опишем некоторые свойства подстановок и 

выполняемых над ними операций.

Определение 5 (Композиция). Если ζ и θ –

две подстановки, то их композиция ζθ является 
подстановкой, определяемой как (Fζ)θ=F(ζθ) для 
всех формул F.

Определение 6 (Допустимость). Даны две 

подстановки ζ1 и ζ2, их композиция θ=ζ1ζ2 допустима тогда и только тогда, когда для любой 
формулы F Fζ1ζ2=Fζ2ζ1 (то есть θ коммутативна) 
и все редукции в θ непротиворечивы.

Результатом допустимой композиции является 

НИП. Необходимо гарантировать, что в итоге
композиции будет получена НИП. Для этого к допустимой композиции θ следует применить операцию внесения констант. Такая операция, примененная к редукции, замещает редукции вида 
={<d1, d2>, <d1, a>} на две редукции вида ={<d1, 
a>, <d2, a>}.

Введем два понятия непротиворечивости.

Определение 7 (Сильно непротиворечивы).

Две подстановки ζ и θ сильно непротиворечивы, 
если ζθ.

Определение 8 (Слабо непротиворечивы).

Две подстановки ζ и θ слабо непротиворечивы, 
если <v, a> ζ, <v, b>θ, a≠b и a или b – переменные.

Сильная и слабая непротиворечивости состав
ляют условия, которые проверяются при построении подстановок в композициях. Если замыкающие подстановки для всех путей в таблице сильно 
непротиворечивы, таблица замыкается немедленно. Если замыкающие подстановки слабо непротиворечивы, тогда таблица все еще может быть 
замкнута, однако необходимо выполнить композицию замыкающих подстановок, чтобы проверить наличие в них скрытых противоречий. Рассмотрим случай, когда три пути замыкаются с 
подстановками: ζ={<x, a>}, γ={<x, y>} и λ={<y, 
b>}. Композиция (ζγ)λ дает противоречивую подстановку, содержащую редукции <x, a> и <x, b>. 
Однако, если γ={<x, z>}, композиция будет непротиворечивой.

Любое
N-множество содержит множество 

П-множеств, каждое из которых унифицирует по 
крайней мере одну пару контрарных формул на 
всех путях конкретной таблицы. Операция согласования объединяет N-множества N1 и N2, соответствующие паре таблиц, выводя единственное 
N-множество, содержащее П-множества, которые 
замыкают обе таблицы. Унификация N-множеств 
называется согласованием [4, 5].

Определение 9 (Наиболее общий унифика
тор). Говорят, что подстановка θ, унифицирующая формулы F1 и F2, называется наиболее общим 
унификаторам (НОУ), если для всех унификаторов ζ формул F1 и F2 существует такая подстановка γ, что ζ=θγ.

Рассмотрим формулы F1(x, b, z) и F2(a, y, c). 

Они могут быть унифицированы подстановкой 
θ={<x, a>, <y, b>, <z, c>}. Здесь θ – НОУ для этих 
формул, так как не существует такой подстановки 
γζ, что F1(x, b, z)γ=F2(a, y, c)γ, и θ=γζ, где ζ≠∅. 
Когда N-множество сгенерировано в концевой 
вершине, каждое П-множество в N-множестве составляет НОУ для пары контрарных формул на 
этом пути.

Определение 10 (Наиболее общая подста
новка). Если дано множество подстановок θ={θ1, 
…, θn}, то θi (i=1, n ) – наиболее общая подстановка (НОП) в θ, если не существует никакой 
θjθ, где θi – экземпляр для θj. Заметим, что может быть больше одной НОП в θ. N-множество 
является множеством НОУ. Каждый НОУ множества термов является НОП, которая унифицирует 
множество. 

Авторы стремятся составить множества под
становок, поддерживая непротиворечивость каж

Программные продукты и системы
№ 3, 2011 г.

12

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

путь, поэтому N-множество может содержать более одного П-множества.

Процесс согласования N-множеств требует 

создания всех перестановок пар П-множеств из 
двух N-множеств (по одному П-множеству из каждого N-множества). Затем любое из результирующих П-множеств, которое содержит несогласованные подстановки или экземпляры какихлибо П-множеств из того же самого N-множества, 
исключаются из этого множества. Несогласованные редукции – результат возникновения конфликтов при присвоении фиктивным переменным 
значений, то есть одна и та же переменная унифицируется с разными константами при замыкании 
таблицы. Для поддержки полноты замыкания сначала включаются все возможные подстановки, 
часть которых при обнаружении противоречий 
позже будет исключена. Очевидно, что П-множество всегда будет непустым, поскольку пустая 
подстановка говорит, что замыкание пути происходит без подстановки.

Определение 11 (Согласование). Согласова
ние N1N2 двух N-множеств N1 и N2 – это множество, полученное композицией всех пар П-множеств, входящих в N1 и N2. N1N2 также является 
N-множеством [4].

Множество N0 получается из согласования N
множеств N1 и N2. N1 – множество подстановок, 
каждая из которых вызывает замыкание всех ветвей левой части таблицы (антецедента), находящейся ниже ветвления. Аналогично N2 – множество подстановок, которое замыкает все ветви в правой части таблицы (консеквента), находящейся 
ниже ветвления. Таким образам, согласование 
двух N-множеств N1={П 

 , ...,  П   

 } и N2={П 

 , 

...,  П   

 
} состоит в композиции каждого члена N1

с каждым членом N2. Это потребует создания n
подстановок, где n=j*k (j – количество П-множеств в N1, k – количество П-множеств в N2). Для 
сокращения числа подстановок N0 следует исключить все конфликтующие подстановки и те, которые являются экземплярами других членов N0 (то 
есть не являются НОУ в N0).

Корневое N-множество – это N-множество, 

полученное согласованием N-множеств наибольшей пары частей таблицы (то есть парой, непосредственно находящейся ниже самого верхнего 

ветвления). Каждое П-множество в корневом 
N-множестве является НОУ для таблицы, которое 
приведет к замыканию каждого пути таблицы.

Метод фиктивных переменных для аналити
ческих таблиц полон и непротиворечив, что доказывается соответствующими теоремами [4, 6]. 
Проиллюстрируем параллельный метод аналитических таблиц с фиктивными переменными (см. 
рис.).

Прокомментируем полученное решение. Пер
вые 14 шагов проходят в соответствии с последовательным алгоритмом метода аналитических 
таблиц с фиктивными переменными. В универсальных формулах с кванторами ∀x или ¬∃x осуществляются подстановки фиктивных переменных 
вместо x, y и z, то есть x=d1, x=d2, x=d3, y=d4 
и z=d5. Затем в экзистенциональных формулах с 
кванторами ∃x или ¬∀x реализуются подстановки 
констант вместо переменных, то есть y=a (для 
F(d1, y)), y=b (для G(d2, y)) и x=c (для H(x, y)).

После этого идет разветвление. Применение 

результатов композиции подстановок дает следующее: 

{{F(d1, a), ¬F(d3, a)}, {G(d2, b), ¬G(d3, b)}}.
Отсюда N1={{<d1/d3>}, {<d2/d3>}}.

В отличие от левого пути правый еще раз раз
ветвляется. Имеем:

{{F(d1,a), ¬F(a,d5)}, {G(d2,b), ¬G(b,d5)}}, 
N2={{<d1/a>, <d5/a>}, {<d2/b>, <d5/b>}}.
{{¬H(c,d4), H(d3,d5) }},
N3={{<d3/c>, <d4/d5>}}.
Применяем операцию согласования, которая 

объединяет N2 и N3, получая N-множество N4:

N4={{<d1/a>, <d5/a>}, {<d2/b>, <d5/b>}} ⨁

⨁ {{<d3/c>, <d4/d5>}}.

Процесс согласования N-множеств, как уже 

упоминалось, требует создания всех перестановок 
пар П-множеств из двух N-множеств, причем несогласованные подстановки или экземпляры любых П-множеств из одного и того же N-множества
будут исключены:

N4={{<d1/a>, <d5/a>}, {<d3/c>, <d4/d5>}}

{{<d2/b>, <d5/b>}, {<d3/c>, <d4/d5>}}={{<d1/a>, 
<d3/c>, <d4/a>, <d5/a>}, {<d2/b>, <d3/c>, <d4/b>,
<d5/b>}}.

Выполняем согласование между левой и пра
вой ветвями:

N1={{<d1/d3>}, {<d2/d3>}};
N4={{<d1/a>, <d3/c>, <d4/a>, <d5/a>},
{<d2/b>, <d3/c>, <d4/b>, <d5/b>}}.

N1⨁N4={{<d1/d3>}, {<d1/a>, <d3/c>, <d4/a>,

<d5/a>}} {{<d1/d3>}, {<d2/b>, <d3/c>, <d4/b>,
<d5/b>}}  {{<d2/d3>}, {<d1/a>, <d3/c>, <d4/a>,
<d5/a>}}  {{<d2/d3>}, {<d2/b>, <d3/c>, <d4/b>,
<d5/b>}} = {{<d1/a>, <d3/a>, <d3/c>, <d4/a>,
<d5/a>} {<d1/c>, <d2/b>, <d3/c>, <d4/b>, <d5/b>},
{<d1/a>, <d2/c>, <d3/c>, <d4/a>, <d5/a>} {<d2/b>,
<d3/b>, <d3/c>, <d4/b>, <d5/b>}}.