Средства и методы ускорения дедуктивного вывода в информационных системах с большим объемом данных

• Автор: Катериненко, Роман Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Санкт-Петербург
• Количество страниц: 90 с. : ил.

СОДЕРЖАНИЕ
ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ, СИМВОЛОВ, ЕДИНИЦ И ТЕРМИНОВ
ВВЕДЕНИЕ
1 Анализ дедуктивного вывода методом
«снизу вверх»
1.1 Актуальность исследования дедуктивного вывода
1.2 Основные определения
1.3 Анализ основных принципов, особенностей и тенденций
в области дедуктивных систем
1.4 Анализ теоретических основ метода «снизу вверх» —
Теорема Эрбрана
1.5 Анализ подходов к реализации дедуктивного вывода
методом «снизу вверх»
1.6 Анализ алгоритма Rete
1.7 Выводы
2 Применение бинарных диаграмм решений для
ускорения дедуктивного вывода
2.1 Анализ применимости бинарных диаграмм решений для
дедуктивного вывода
2.2 Разработка общей стратегии применения
бинарных диаграмм решений

2.3 Разработка характеристической функции отношения
с применением булевых операций
2.4 Анализ операций над бинарными диаграммами решений
для дедуктивного вывода
2.5 Анализ сложности операций над бинарными диаграммами
решений для дедуктивного вывода
2.6 Разработка бинарной диаграммы решений для отношения
2.7 Разработка бинарной диаграммы решений для дизъюнкта
2.7.1 Назначение доменов переменным
2.7.2 Переименование переменных в теле правила
2.7.3 Построение бинарной диаграммы решений для
тела правила
2.7.4 Построение бинарной диаграммы решений для
головы правила
2.8 Выводы
3 Разработка метода верификации систем отслеживания задач и его применение для экспериментального исследования
производительности дедуктивного вывода
3.1 Анализ актуальности верификации систем отслеживания задач .
3.2 Постановка задачи верификации систем отслеживания задач
3.3 Основные обозначения
3.4 Построение дедуктивной модели для верификации
систем отслеживания задач
3.5 Разработка алгоритма верификации систем отслеживания задач .
3.6 Реализация алгоритма в виде программного приложения
3.7 Постановка эксперимента исследования
производительности дедуктивного вывода
3.8 Проведение экспериментального исследования
производительности дедуктивного вывода

3.9 Выводы

4 Применение модели вертикальных баз данных для ускорения дедуктивного вывода
4.1 Анализ применимости вертикальных баз данных для дедуктивного вывода
4.2 Применение модели вертикальных баз данных для ускорения дедуктивного вывода
4.3 Экспериментальное исследование дедуктивного вывода на основе
баз данных с вертикальной архитектурой
4.4 Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ
ДИССЕРТАЦИИ
ЛИТЕРАТУРА

Для наглядности поясним формулы простым примером из одной таблицы и трех доменов Д), , Д. Для простоты положим, что в г-ой строке таблицы
находится г-ый элемент домена (Таблица 2.1). Таблица 2.2 схематически изоб-
Таблица 2.1. Пример г-ый элемент таблицы
N Do D - d

г хф

ражает характеристическую функцию г-го элемента домена. Таблица 2.3 схе-
Таблица 2 2 Пример характеристическая функция г-го элемента домена
N D0 D ! d

г Д(Д)

матически изображает характеристическую функцию г-го кортежа таблицы.
Таблица 2 3* Пример характеристическая функция г-го кортежа таблицы
N Do . . D1 ; D

г хРЧДДл хДО

В статье [71] приводится анализ логарифмического и линейного методов кодирования множеств для использования в БДР. Логарифмический способ заключается в последовательном сопоставлении каждому элементу множества порядкового номера, записанного двоичным числом. Для введенных выше обозначений это можно записать как xDk — xDk, где Д-произвольный домен. Имея n-битное двоичное число, можно закодировать log п элементов - отсюда и название метода. При таком подходе хг переменная-решение принимает значение 1, если на г-ом месте в двоичном числе находится 1, в противном случае хг = 0.
При линейном способе кодирования каждый элемент множества разбивается на последовательность символов или, в случае многослойного линейного кодирования, на группы символов. При таком подходе хг переменная-решение