Структурно-лингвистические, алгоритмические и аппаратные средства акселерации символьной машины баз данных

• Автор: Сорокин, Валерий Евгеньевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Курск
• Количество страниц: 212 с. : ил.

СОДЕРЖАНИЕ щ ВВЕДЕНИЕ

Глава 1. Аналитический обзор современного состояния средств СУБД и машин баз данных

1.1. Общие положения исторический очерк

1.2. Неоднородные многопроцессорные ма шины баз данных МБД

,г 1.3. Параллельные машины баз данных

1.4. Побудительные причины исследования и сущность предлагаемого

подхода к созданию МБД

1.5. Выводы .

Глава 2. Структурно лингвистические средства акселерации

2.. Понятийный базис продукционной алгоритмической системы

2.2. Классификация формул подстановок .

2.3. Способы синтеза акселерационных форм представления продукций .
2.4. Иллюстрация продукционной реализации операций реляционной
алгебры .
2.5. Способы сопоставления поиска по образцу
2.6. Способы сортировки .
2.6.1. Классификация алгоритмов сортировки последовательное
Ф 2.7. Способ парной параллельной сортировочной транспозиции эле
V ментов и слияния отсортированных последовательностей .
2.8. Выводы .
Глава 3. Разработка аппаратных средств акселерации .
3.1. Способ организации машины баз данных 1
3.2. Специализированное устройство сортировки
3.3. Специализированное устройство слияния .
3.4. Специализированное устройство быстрого поиска позиций вхождений образцов
3.4.1. Работа устройства поиска вхождений образца .
3.5. Специализированное устройство модификации слов .
3.6. Выводы .
Глава 4. Алгоритмические средства устройств управления специализированными устройствами МВД и результаты исследования скоростных характеристик .
4.1. Алгоритмы управления устройств сортировки и слияния
4.1.1. Алгоритм управления устройства сортировки
4.1.2. Алгоритм управления устройства слияния .
4.2. Алгоритм управления устройства поиска вхождения
4.3. Алгоритм управления устройства модификации
4.4. Результаты исследования скоростных характеристик .
4.4.1. Сопоставительный анализ ускорений разработанного устройства и аналога
4.4.2. Анализ скоростных характеристик устройства поиска
4.4.3. Анализ скоростных характеристик продукционного символь
ного процессора .
4.5. Выводы .
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


В заключении приводятся основные результаты диссертационного исследования. В приложении размещен листинг программных средств для моделирования работы алгоритмов и устройств. ГЛАВА 1. Данная глава носит обзорный характер и служит целям структурного анализа функциональных особенностей машин баз данных (МБД). Вместе с тем глава содержит изложение сущности и особенностей предлагаемого подхода. В конце -х годов выдвигались идеи многоуровневой архитектуры систем баз данных. Дальнейшее конструктивное развитие эти идеи получили в исследованиях рабочей группы по базам данных Database Task Group, принявшей стандарт CODASYL, в отчёте Американского института стандартов (ANSI), в работах М. Сенко, Я. Палмера, Г. Майсена, Э. Озкарахана, Л. Калиниченко, Д. Поспелова и других специалистов Щ. Разработка новых архитектурных подходов, основанных на многоуровневом представлении данных, породила проблемы отображения данных. В связи с этим конец -х и начало -х годов стали периодом активизации исследований и разработок в области моделей данных [2, 3,4]. Характерной чертой ранних моделей данных - иерархической, сетевой и реляционной - является рассмотрение данных в качестве самостоятельных абстрактных объектов. Их содержательный смысл и связь с объектами предметной области информационной системы остаются при этом за пределами базы данных. С середины -х годов начинаются исследования и попытки разработки моделей данных нового'типа, призванных решить задачу удержания семантики предметной области. Эти модели данных стали называться семантическими. В их создании приняли участие многие крупные научные центры. Тем не менее, эти модели данных еще не стали основой создания коммерческих СУБД для широкого использования [5]. Каждая СУБД может рассматриваться как механизм поддержки некоторой модели данных - инструмента отображения состояний предметной области и её динамики в среде базы данных, управляемой этой системой. Машина баз данных (МБД) - аппаратно-программный комплекс, который является частью вычислительной системы и предназначен для выполнения всех или некоторых функций СУБД. МБД решает две существенные проблемы: повысить коэффициент “производительность СУБД / стоимость СУБД” и надежность ее функционирования [6, 7]. В связи с прогрессом в области СБИС и микропроцессоров стало развиваться еще одно направление в области процессоров для обработки данных -это процессоры-акселераторы, которые выполняют некоторые функции по обработке данных. Они реализуются или в виде приставки для персональных компьютеров (например, плата сортировки фирмы Cadent Data Techn. IBM PC/XT), или в виде процессора, подключаемого к главной ЭВМ. Также в качестве примера можно привести акселератор для сортировки файлов БД DBA- фирмы Accel для подключения к ЭВМ типа VAX. Его скорость обработки составляет 1 Мбайт/с; для сортировки файла, на которую затрачивается - мин в ЭВМ VAX 0, требуется с [8]. Подсоединяется процессор к главной ЭВМ через локальную сеть и одновременно может обслуживать несколько главных ЭВМ. Тем не менее, тенденция развития МБД лежит в области увеличения разнообразия функций БД. Классификация МБД по разнообразию выполняемых функций приведена в таблице 1. Здесь МБД разбиты на 4 класса по мере увеличения объема выполняемых функций [9, 1. Поисковые процессоры RARES и SURE и процессоры-акселераторы для сортировки (DBA-) относятся к первому классу, так как выполняют отдельные автономные функции по обработке данных [П. МБД второго класса выполняют набор операций реляционной алгебры с той или иной степенью эффективности. МБД, не позволяет им полностью и автономно поддерживать СУБД, и такие МБД могут использоваться только в комплексе с универсальной управляющей ЭВМ, функции которой, в основном, берёт на себя главная ЭВМ. Таблица 1. В таблице 1. МБД по структурно-функциональным особенностям [6]. В качестве классификационных признаков выбраны следующие: тип структуры МБД; вид обработки; вид аппаратуры в уровнях обработки; тип возможного параллелизма, обусловленный структурой МБД; способ взаимодействия процессоров обработки.