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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

— " ^ * *

' ' На правах рукописи

КАЗАРЦЕВ Алексей Александрович

АЛГОРИТМ ПОИСКА В БАЗЕ ДАННЫХ, ОСНОВАННЫЙ НА АППРОКСИМАЦИИ РАСПРЕДЕЛЕНИЯ АДРЕСОВ В

ИНДЕКСЕ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 1995

Работа выполнена в Полоцком Государственном университете

Научный руководитель

Официальные оппоненты:

Оппонирующая организация -

доктор технических наук, профессор В.В. Трофимов

доктор физико-математических наук, профессор И.Л. Братчиков

кандидат технических наук Е.С. Янчук

Институт проблем транспорта Российской академии наук

Защита состоится декабря 1995г. в

час

на заседании диссертационного совета К.063.57.48 по защите диссертаций на соискание ученой степени кандидата

наук в

Санкт-Петербургском Государственном университете. Адрес совета: 198904 Санкт-Петербург, Старый Петергоф, Библиотечная

площадь 2, факультет

ПМ-ПУ СПбГУ

С диссертацией можно ознакомиться в библиотеке им М.Горького Санкт-Петербургского Государственного университета. Университетская набережная 7/9.

Автореферат разослан

- /* - ноября 1995г. Ученый секретарь диссертационного совета

к.т.н. М.А. Галактионов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы. В современной практике СУБД применяются несколько видов поиска, использующихся для различных БД. Однако до настоящего времени не существует удовлетворительного алгоритма поиска, который бы превосходил по быстродействию поиска двоичное дерево, но имел бы меньшее время модификации чем хешированный файл.

В частности, интерес к таким методам поиска обусловлен широкой сферой применения технологических БД, требующих, более высокого быстродействия процедур модификации, чем хешированный файл (например БД нештатных ситуаций ПО "Нафтан"). Отсутствие в настоящее время такого алгоритма поиска позволяет считать проведенные исследования и на их основе алгоритмическое решение проблемы поиска актуальными. Кроме того, диссертационная работа показывает возможности моделирования работы БД (с учетом известных статистических закономерностей, как то: пуассоновское распределение заявок на запись в БД и т. д.), на ЭВМ типа IBM. Актуальность такого алгоритмического решения очевидна, поскольку в настоящее время, при переводе алгоритмов поиска из программной области в аппаратную, становится острой проблема нахождения оптимального алгоритма, наиболее пригодного для аппаратной реализации.

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

Цель и задачи исследования. Определение закономерностей распределения адресов в индексном файле; разработка математической модели функционирования статичной БД; разработка нового алгоритма поиска по БД с целью уменьшения времени поиска в сравнении и известными алгоритмами поиска в индексе.

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

значений ключа;

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

3. Исследование закономерностей поиска и модификации в

им О II ИТ", И II и

индексном файле, вида разреженный индекс , В-дерево , разреженный индекс с аппроксимацией", "В-дерево с аппроксимацией".

Практическая значимость полученных результатов состоит в разработке нового метода поиска по БД, позволяющем получить значительное быстродействие по индексу при меньшем времени модификации, чем у хешированного файла, оценке возможности реализации разработанного алгоритма с использованием СУБД С-Тгее, и БД нештатных ситуаций (ПО "Нафтан").

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

Аппробация результатов диссертации. Результаты исследований, включенные в диссертацию докладывались на конференциях:

1. XXX научно - техническая конференция аспирантов и студентов, посвященная 30 - летию БГУИР. Минск, БГУИР, апрель 1994г.

2. Межгосударственная научно-практическая конференция творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение". Минск, БГУ, май 1994г.

3. Республиканская научно-методическая конференция, посвященная 25-летию факультета прикладной математики и информатики г. Минск, БГУ, 10-14 апреля 1995г.

4. I общеуниверситетская научно-техническая конференция , г. Новополоцк, ПГУ, 16-20 мая 1995г..

Опубликованность результатов. По основным результатам работы имеется 9 публикаций, в том числе 5 статей, 1 отчет по научно-исследовательской работе, 1 материалы и 2 тезисов докладов на кондеренциях.

Структура и обьем диссертации. Диссертация состоит из введения, 3 глав, заключения и приложения. Работа изложена на 105 листах

машинописного текста (из них 91 лист - основной текст), содержит 20 таблиц и 25 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе диссертации дан обзор методов и систем поиска, применяемых в современных СУБД, в котором содержатся сведения о: направлениях разработки; видах поиска в БД; видах и структуре индексных файлов в БД; приводятся анализ и оценка результатов тестирования популярных СУБД с точки зрения поиска по БД; оптимизации и совершениствования алгоритмов поиска по БД.

Анализ рассмотренных методов и систем поиска позволяет заключить:

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

2. Наиболее широко используется поиск по разреженному индексу и двоичному дереву (даже в БД, представляющих собой слабоизменяющуюся структуру). Главная причина использования этих видов поиска в приемлемом времени модификации при удовлетворительном времени поиска.

3. Отсутствуют результаты исследований по распределения адресов в индексе и математическому моделированию БД индивидуального и группового обслуживания.

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

В связи с вышеизложенным в работе сформулированы следующие цели и задачи исследований:

1. Разработать математическую модель типичного представителя большой слабоизменяющейся БД;

2. Исследовать статистические закономерности распределения адресов в индексе - как в разреженном, так и на нижних уровнях индексирования двоичного дерева с целью создания алгоритма поиска, основанного на апроксимауии распределения адресов в индексе;

3. Используя статистические данные и математическую модель БД, разработать алгоритм поиска, основанный на апроксимации распределения адресов в индексе;

4. Использовать разработанный алгоритм для разработки соответствующего программного обеспечения на базе одной из уже функционирующих СУБД.

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

Рис. 1

Описание системы. Рассмотренная система из т = 10 блоков каждый из которых имеет п = 7 каналов, не является единственной, в которой может быть использована БД с предлагаемым алгоритмом поиска. Для тестирования распределения адресов и различных алгоритмов поиска требуется лишь смоделировать пуассоновское и равномерное распределение заявок на запись и удаление для симуляции группового и единичного воздействия на БД. Выбор системы с предложенным количеством блоков

и каналов вытекает из априорных данных реальной системы по которой создается модель.

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

Период времени работы БД был выбран исходя из реальных данных о функционировании БД - 1 месяц. Индексирование БД проводилось ежечасно и, следовательно, было набрано по 720 индексных файлов каждого вида для работы с несколькими блоками (пуассоновское распределение) и по 720 файлов каждого вида для работы с одним блоком (равномерное распределение).

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

Над каждым индексным файлом была проведена операция сплайновой аппроксимации. Если представить сплайн функцией S(x), то при небольших наклонах 2-я производная S"(x) приблизительно равна кривизне, а дифференциал дуги можно приближенно представить как dx. Если в качестве узлов сплайна взять значения ключа-адреса (xj.yj), (х2,У2)> ••• (хп,уп), то аппроксимированный индекс - линеаризованный сплайн S(x) есть

функция для которой S(xi)=yi, (i=l,2,...,n), и при этом:

имеет минимальное значение. Аппроксимировать индекс этим методом удобно еще и потому, что построение сплайна - простой и численно устойчивый процесс.

Таким образом была произведена аппроксимация каждого индекса и на каждый индексный файл был получен файл, содержащий 400 значений

2

d х

О)

* 1

"х-у" и представляющий собой табличную реализацию построенного сплайна.

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

1) Гипотеза Н-}. Р = 1/п; - равномерное распределение. Это распределение

предположительно могло быть реализовано когда БД работает:

1) С заделом (ЭЫ) - перед включением функции удаления один час происходит накопление данных. В этом случае возможны два режима работы БД:

А) Запись в БД происходит по пуассоновскому распределению (АР). В этом случае возможно разделение режимов работы на три варианта:

1) Стопроцентное удаление всех записей из БД (ОА). Очевидно, что при таком режиме работы БД маловероятно получение равномерного распределения.

2) Пуассоновское удаление из БД с различными степенями пропорциональности записи-удаления (ОР).

3) Равномерное удаление из БД с различными степенями пропорциональности записи-удаления (ОЕ).

Б) Запись в БД происходит по равномерному распределению (АЕ). В этом случае возможно разделение режимов работы на три варианта: ОА,

ЭР,БЕ.

2) БД работает без задела (WS). В этом случае возможны два режима работы:

А) Запись в БД происходит по пуассоновскому распределению (АР). В этом случае возможно разделение режимов работы на три варианта:

ОА, DP.DE.

Б) Запись в БД происходит по равномерному распределению (АЕ). В этом случае возможно разделение режимов работы на три варианта:

ОА, ОР, ОЕ.

Исходя из вышеизложенного:

#1 =

SUKJAPUDP

SU и APuDE

SUAEvjDA

SUuAEuDP

SU и AE и DE

WSuAPuDP

WS и APuDE

WSu AEKJDA

WSkjAEKJDP

WSVAEkjDE, к -к

2) Гипотеза HР(к) = (ае )/к! при a=M(k)=D(k); -пуассоновское

распределение. Зависимость индекс-адрес близка к зависимости вида 2

у=ах +Ьх+с при положительном значении коэффициента "а". Эту гипотезу можно описать следующей системой:

(2)

Я2И

SUuAEuDP WS и АР vj DP WS и АЕ и DP

г.

(3)

к -к.

3) Гипотеза Н3. Р(к) = М - (а е )/к! при a=M(k)=D(k), где М -

максимальное значение адреса в индексном файле. Зависимость индекс-

2 ,

адрес близка к зависимости вида у=ах +Ьх+с при отрицательном значении коэффициента "а". Эту гипотезу можно описать следующей системой:

я, =

и

' Би и АРиБР 811 и АР и ОЕ 811 и АР и О А ^и АР и йР ' (4) 1¥ЗиАРиОЕ ШиАРиОА ,

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

В результате проведения анализа, полученные данные показали, что гипотеза Н| подтвердилась в четырех случаях из шести, гипотеза Н3 подтвердилась в двух случаях из шести, а гипотеза Н2 - не подтвердилась ни в одном случае. Следовательно:

'Ш'иАРиОР'

Н*=<

Я3* =

(5)

(6)

ИЯиАЕиОР ЖБиАЕиОА ШиАЕиОЕ

жя^АР^ПЕ)

Ш^АРиЯА,

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

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

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

Сплайновый алгоритм аппроксимации описан выше, поэтому далее приводится краткое описание полиномиального способа аппроксимации. Значение адреса здесь представляется вычисленным значением полинома Лагранжа:

В этих формулах Рп(х) - многочлен п степени, интерполирующий на

[х()...хп] , х^- заданные начальные значения, по которым производится

аппроксимация, х - значение индекса, для которого значение многочлена будет значением адреса. У^- значение соответствующее х^. Таким образом

сетка значений, по которым производится интерполяция представляет собой

« . « индексный файл.

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

Динамику изменения времени аппроксимации можно проследить при помощи диаграммы (рис. 2).

Ук

(7)

здесь:

\^(х)=(х-хо)(х-х!)...(х-хп); (8)

Следующим этапом эксперимента является выбор оптимального из

Рис. 2

81-сплайновый алгоритм, 32-полиномиальный алгоритм.

Ось ОХ - количество значений сетки (7..... 60).

Ось ОУ - время аппроксимации (сек.)

Здесь явно лидирует сплайновый алгоритм 10 - 20 % от времени полиномической аппроксимации, которая медленнее из-за множества операций умножения. На основании перечисленных данных тестирования алгоритмов имеет смысл остановить выбор на сплайновом методе аппроксимации, несмотря на его определенную алгоритмическую (но не вычислительную) сложность.

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

На диаграмме (рис. 3) представлена динамика изменения времени поиска в зависимости от накопления значений индекса.

10

50

Линейный поиск на диаграмме не изображен.

Ось ОХ - количество значений индекса (5000 - 50000).

Ось ОУ - время поиска (количество обращений к жесткому диску).

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

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

Основываясь на вышеизложенных данных имеет смысл предложить:

1) Разработать алгоритм поиска по БД, основанный на аппроксимации распределения адресов в индексе, объединенной с алгоритмом поиска по разреженному индексу методом дихотомии.

2) Разработать алгоритм поиска в БД, основанный на аппроксимации распределения адресов в индексе, объединенной с алгоритмом поиска по В-дереву.

Далее приводятся соображения по построению предложенных комбинированных алгоритмов.

Для использования предложенного метода предлагается стратегия

II oll Т/ч

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

Предлагаемый алгоритм представлен на рис.4.

индекс иров ания Рис. 4

Алгоритм дихотомического поиска с фрагментом аппроксимации.

Р-[ - аппроксимирующая функция

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

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

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

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

Результаты тестирования реальных систем поиска СУБД с разработанным программным модулем показали, что численные соотношения характеристик рассмотренных алгоритмов поиска соответствуют ожидавшимся. Аппроксимационный алгоритм дает 34% выигрыш по времени поиска и 32% пройгрыш по времени модификации по сравнению с двоичным поиском и В-деревом. Однако, необходимо заметить, что соотношения могут изменяться, если:

1. СУБД выполняет одновременно несколько процедур и процедура поиска задерживается для выполнения другой, приоритетной в данный момент, процедуры.

2. СУБД при модификации записывает не только полученный файл-сетку, но и заново перезаписывает индексный файл.

3. СУБД обращается к устройствам, имеющим низкое быстродействие (кроме учтенного жесткого диска), например, к сетевому адаптеру АгсКеЬ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

2. Исследовано влияние на индексные файлы плотности распределения входных заявок на запись и удаление, что позволило определить вид функции распределения адресов в индексе.

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

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

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

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

7. Предложены способы построения новых алгоритмов поиска в БД, представляющих собой дихотомический алгоритм поиска по разреженному индексу с аппроксимацией и алгоритм поиска по B-дереву с частично аппроксимированными уровнями индексирования.

Основное содержание работы опубликовано:

1. Казарцев A.A. Анализ методов поиска, применяемых в современных СУБД/ Полоцкий гос. университет. -Новополоцк 1995. -19 е.: -Деп. в ин-те "Белинформпрогноз".

2. Казарцев A.A. Математическая модель функционирования технологической базы данных/ Полоцкий гос. университет. -Новополоцк 1995. -И е.: -Деп. в ин-те "Белинформпрогноз".

3. Казарцев A.A. Статистические закономерности распределения адресов в индексном файле/ Полоцкий гос. университет. -Новополоцк 1995. -21 е.: -Рус. -Деп. в ин-те "Белинформпрогноз".

4. Казарцев A.A. Реорганизация индексных файлов на основе аппроксимации распределения адресов/ Полоцкий гос. университет. -Новополоцк 1995. -18 е.: -Библиогр. 8 назв. -Рус. -Деп. в ин-те

Белинформпрогноз "

5. Казарцев A.A. Программный модуль системы поиска Spline / Полоцкий гос. университет. -Новополоцк 1995. -18 е.: -Библиогр. 17 назв. -Рус. -Деп. в ин-те "Белинформпрогноз".

6. Трофимов В.В., Оськин А.Ф., Казарцев A.A. Разработка методологии проектирования систем реального времени. Отчет по НИР. /Новополоцк, ПГУ, 1993. УДК 658.28.

7. Казарцев A.A. Алгоритмы поиска в базе данных, основанные на аппроксимации плотности распределения адресов данных и индексных адресов. Материалы доклада на Межгосударственной научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" /Минск, БГУ, 1994. с.11.

8. Казарцев A.A. Анализ систем управления базами данных (СУБД), используемых в системах реального времени (СРВ). Тезисы доклада на XXX научно - технической конференции аспирантов и студентов, посвященной 30 - летию БГУИР. /Минск, БГУИР, 1995. с.60.

9. Казарцев A.A. Алгоритм поиска в базе данных, основанный на аппроксимации плотности распределения адресов в индексе. Тезисы доклада на XXX научно - технической конференции аспирантов и студентов, посвященной 30 - летию БГУИР. /Минск, БГУИР, 1995. с.61.