Введение к работе
Актуальность исследования. Методы проектирования баз данных (БД) имеют большое практическое значение при создании любых информационных систем. Как известно, два важнейших этапа проектирования БД - это логическое и физическое проектирования. Целью логического проектирования является создание абстрактной логической модели предметной области, которая не зависит от способов реализации и использования данных. Физическое проектирование является главнейшим этапом, влияющим на производительность будущей системы, которая достигается за счет рационального отображения логической схемы данных на структуры, поддерживаемые целевой СУБД.
Задача построения логической схемы в теории проектирования БД обычно не имеет единственного решения. Одной из задач администратора БД является целенаправленная модификация логической схемы, если во время эксплуатации появилась информация о том, что другая логическая схема будет обеспечивать большую производительность работы всех или важнейших приложений.
Задача модификации логической схемы в соответствии со спецификой приложений является достаточно общей и поэтому имеет большое теоретическое и практическое значение.
Существуют три основных метода решения этой задачи: денормали-зация, горизонтальная кластеризация и вертикальная кластеризация. Вертикальная кластеризация является задачей NP-сложности и представляет наибольший интерес для научного исследования. По сути, этот метод является развитием классической теории нормализации, который также реализуется через декомпозицию отношений, но с учетом распределения частот требования атрибутов приложениями. Цель этой декомпозиции -повышение общей производительности приложений и производительности системы в целом. Эта проблема достаточно хорошо исследована в зарубежной литературе. К сожалению, на русском языке редко встречаются даже переводы зарубежных работ по данной тематике. Следует отметить, что в существующих в настоящий момент зарубежных работах рассматривается проектирование только систем распределенных БД. Но очевидно, что доля централизованных систем реляционных БД значительно больше, чем распределенных.
Это обстоятельство делает актуальным теоретическое и практическое исследование применения методов вертикальной кластеризации отношений для централизованных систем БД.
Целью диссертационного исследования является разработка и исследование метода повышения эффективности использования кэшпамяти с помощью бинарной вертикальной кластеризации отношения для централизованных систем реляционных БД.
Для достижения данной цели необходимо решить следующие основные задачи:
-
проанализировать существующие методы применения вертикальной кластеризации отношений при проектировании систем баз данных;
-
разработать математическую модель задачи бинарной вертикальной кластеризации отношений для повышения эффективности использования кэш-памяти в централизованных системах баз данных;
-
разработать алгоритмы решения задачи бинарной вертикальной кластеризации отношений для повышения эффективности использования кэш-памяти в централизованных системах баз данных.
-
разработать программные средства для экспериментального исследования предложенного метода вертикальной кластеризации и эффективности алгоритмов его реализации.
Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и систем БД, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, методы математического программирования и эвристические методы оптимизации.
Существенные научные результаты, полученные в диссертации:
-
Критерий оценки частоты кэш-попаданий для метода вертикальной кластеризации отношений при заданном потоке запросов и условии равной вероятности обращений к кортежам отношения, экспериментальная проверка которого установила, что оценка относительного отклонения от теоретического значения не превышает 2% с математическим ожиданием 0,1% и средним квад-ратическим отклонением 0,23%.
-
Метод повышения эффективности использования кэш-памяти в централизованных системах БД, основанный на декомпозиции отношений с использованием критерия оценки частоты кэш-попаданий, позволяющий найти рациональную декомпозицию при заданном потоке запросов и при условии равной вероятности обращений к кортежам отношения.
-
Метод нахождения решения задачи целочисленного программирования применительно к специфике метода декомпозиции отношений с критерием оценки частоты кэш-попаданий при заданном потоке запросов и при условии равной вероятности обращений к кортежам отношения.
-
Алгоритм приближенного решения задачи декомпозиции отношений с критерием оценки частоты кэш-попаданий при заданном потоке запросов и при условии равной вероятности обращений к кортежам отношения, для которого на репрезентативной выборке
оценка математического ожидания отклонения от точного решения составляет 5%, а среднее квадратическое отклонение 1%.
Практическая значимость диссертационной работы заключается в следующем:
-
Предложенный метод бинарной вертикальной кластеризации отношения для модификации логической схемы, полученной традиционным методом логического проектирования БД, позволяет продолжить декомпозицию отношений с целью повышения эффективности использования кэш-памяти и, следовательно, повышения производительности централизованных баз данных.
-
Зарегистрированный в Отраслевом фонде алгоритмов и программ (ОФАП) "Программный стенд для исследования алгоритмов кэширования" позволяет исследовать частоты кэш-попаданий при кэшировании различных схем декомпозиции отношения. Зарегистрированная в ОФАП "Программа для вертикального бинарного разбиения отношений РБД" позволяет исследовать эффективность приближенного решения задачи декомпозиции отношения в сравнении с алгоритмом полного перебора.
-
Предложенный метод бинарной кластеризации и две программные разработки имеют ценное практическое приложение в учебном процессе, так как исследуемая проблема впервые рассматривается в русской литературе.
Апробация диссертационной работы. Основные результаты диссертационной работы получили апробацию на следующих международных конференциях:
на XX Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-20), ЯГГУ, Ярославль, 2007;
на XXI Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-21), СГТУ, Саратов, 2008;
V Spring young researchers' colloquium on database and information systems (SYRCoDIS V), Saint-Petersburg, 2008;
на I международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2006);
на II международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2007);
Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского госу-. дарственного технического университета.
Публикации. Всего по теме диссертации опубликовано 16 печатных работ (одна в издании, включенном в перечень ВАК), в которых отражены основные результаты диссертации.
