Метод вертикальной кластеризации для реляционных систем хранения и обработки информации

• Автор: Нго Тхань Хунг
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Ростов-на-Дону
• Количество страниц: 159 с. : ил.

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

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

1.1. ОСНОВНЫЕ ПОНЯТИЯ.

1.1.1. Трехуровневая архитектура абстракций базы данных

1.1.2. Разработка внешних представлений баз данных.

1.1.3. Логическое проектирование базы данных.

1.1.3. Физическое проектирование систем реляционных баз данных.

1.2. ПОДГОТОВКА ИСХОДНОЙ ИНФОРМАЦИИ ДЛЯ ФИЗИЧЕСКОГО ПРОЕКТИРОВАНИЯ.

1.3. МЕТОДЫ ДЛЯ ФИЗИЧЕСКОГО ПРОЕКТИРОВАНИЯ

1.3.1. Проектирование с использованием триггеров.

1.3.2. Применение уникальных индексов
1.3.3. Использование снимков.
1.3.4. Применение денормализации.
1.3.5. Горизонтальная н вертикальная кластеризация отношений.
1.3.5.1. Горизонтальная кластеризация
1.3.5.2. Вертикальная кластеризация
1.3.5.3. Сметанная кластеризация.
1.4. ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ.
ГЛАВА 2. ИССЛЕДОВАНИЕ АЛГОРИТМОВ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ В ЗАДАЧАХ ПОВЫШЕНИЯ СИСТЕМНОЙ ПРОИЗВОДИТЕЛЬНОСТИ
2.1. ПОКАЗАТЕЛИ ЭФФЕКТИВНОСТИ СИСТЕМ БАЗ ДАННЫХ.
2.2. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ УЛУЧШЕНИЯ ПОКАЗАТЕЛЕЙ СИСТЕМ БАЗ ДАННЫХ С ПОМОЩЬЮ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ
2.3. РОЛЬ МАТРИЦЫ ОБРАЩЕНИЙ К АТРИБУТАМ ОТНОШЕНИЯ.
2.4. ИСПОЛЬЗОВАНИЕ МАТРИЦЫ РОДСТВЕННОСТИ АТРИБУТОВ ОТНОШЕНИЯ.
2.5. АЛГОРИТМ СОРТИРОВКИ МАТРИЦЫ РОДСТВЕННОСТИ АТРИБУТОВ ВЕА.
2.6. АЛГОРИТМ БИНАРНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ ВУР
2.6.1. Процедура разбиения и критерий оценки качества схемы разбиения
2.6.2. Пример выполнения процедуры разбиения.
2.6.3. Процедура смещения
2.6.4. Выводы но алгоритму БУР.
2.7. ГРАФИЧЕСКИЙ АЛГОРИТМ НАВАТХЕ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ.
2.7.1. Основные понятия и обозначения
2.7.2. Процедура построения остова и кластеров.
2.7.3. Пример применения графического алгоритма Наватхе
2.7.4. Проблема неоднозначности получения результатов кластеризации но графическому алгоритму Наватхе
2.7.5. Уточнение графического алгоритма Наватхе
2.7.6. Выводы по графическому алгоритму Наватхе
2.8. ЭВРИСТИЧЕСКИЙ АЛГОРИТМ МА ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ДЛЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ БАЗ ДАННЫХ
2.8.1. Специфика распределенных систем баз данных
2.8.2. Критерий размещения атрибутов на серверах.
2.8.3. Постановка задачи применения вертикальной кластеризации для уменьшения суммарной стоимости доступов к атрибутам
2.8.4. Алгоритм решения задачи вертикальной кластеризации в распределенных системах баз данных.
2.8.5. Выводы по эвристическому алгоритму Ма.
2.9. ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ.
ГЛАВА 3. МЕТОД ПРИМЕНЕНИЯ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЙ ДЛЯ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ЦЕНТРАЛИЗОВАННЫХ СИСТЕМ БАЗ ДАННЫХ
3.1. ОБОСНОВАНИЕ ВЫБОРА ПОКАЗАТЕЛЯ ПРОИЗВОДИТЕЛЬНОСТИ ДЛЯ ОЦЕНКИ КАЧЕСТВА СХЕМ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ.
3.2. МОДЕЛЬ КЭШСИСТЕМЫ В ЦЕНТР АЛИЗОВАННЫХ СИСТЕМАХ БАЗ ДАННЫХ
3.2.1. Метод физической реализации вертикальных кластеров в централизованных системе баз данных
3.3. ОПИСАНИЕ И ОБОЗНАЧЕНИЕ ПЕРЕМЕННЫХ.
3.4. ВЫВОД ФОРМУЛЫ ОЦЕНКИ ВЕРОЯТНОСТИ КЭШПОПАДАНИЯ ПРИ КЭШИРОВАНИИ БИНАРНЫХ ВЕРТИКАЛЬНЫХ КЛАСТЕРОВ.
3.4.1. Вероятность кэшпопаданий для кэширования исходного отношения
3.4.2. Вероятность кэшнопаданий для кэширования проекций.
3.5. ПОСТАНОВКА ЗАДАЧИ ПРИМЕНЕНИЯ БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ В ЦЕНТРАЛИЗОВАВ 1НЫХ СИСТЕМ БАЗ ДАННЫХ
3.6. АНАЛИЗ ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ ИЗВЕСТНЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ II.
3.7. ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ.
ГЛАВА 4. РАЗРАБОТКА МЕТОДА БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ
4.1. РЕШЕНИЯ ЗАДАЧИ 3.5. 3.5. АЛГОРИТМОМ ПОЛНОГО ПЕРЕБОРА
4.2. ФОРМУЛИРОВКА ЗАДАЧИИСТОКА И ЕЕ ОСЛАБЛЕННОЙ ЗАДАЧИ
4.3. МЕТОД РЕШЕНИЯ ЗАДАЧИИСТОКА ПРИ С 0.
4.3.1. Лемма 1 о нахождении оптимального решения ослабленной задачи на краевой линии 4.2.
4.3.2. Решение ослабленной задачи.
4.3.3. Лемма 2 о свойстве оптимального решения задачиистока.
4.3.4. Лемма 3 о допустимости решения задачиистока, полученного целочисленным округлением некоторого допустимого решения ослабленной задачи.
4.3.5. Лемма
4.3.6. Теорема об области, содержащей оптимальное решение задачиистока
4.3.7. Пример реализации метода сужения интервала поиска в среде Мар1е
4.4. ЭВРИСТИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ ПОТЕНЦИАЛЬНОГО МНОЖЕСТВА СХЕМ ВЕРТИАКЛЬНОЙ КЛАСТЕРИЗАЦИИ.
4.5. ПРЕДЛОЖЕННЫЙ ЭВРИСТИЧЕСКИЙ АЛГОРИТМ БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ
4.6. СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИИ АЛГОРИТМОВ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ
4.6.1. Реализация алгоритма БУР
4.6.2. Реализация графического алгоритма Наватхе.
4.6.3. Реализация эвристического алгоритма Ма
4.6.4. Реализация предложенного алгоритма НВУР.
4.7. СРАНИТЕЛЬНЫЕ ПРИМЕРЫ РЕАЛИЗАЦИИ ГРАФИЧЕСКОГО АЛГОРИТМА НАВАТХЕ С ПРЕДЛОЖЕННЫМ ЭВРИСТИЧЕСКИМ АЛГОРИТМОМ
4.7.1. Первый пример.
4.7.2. Второй пример.
4.7.3. Третий пример.
4.8. ВЫВОДЫ ПО ЧЕТВЕРТОЙ ГЛАВЕ
ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.
5.1. ОПИСАНИЕ ИМИТАЦИОННОЙ МОДЕЛИ КЭШСИСТЕМЫ.
5.2. МОДЕЛИ ПОТОКОВ ЗАПРОСОВ К КЭШСИСТЕМЕ
5.2.1. Специальные случая реализации предложенной модели.
5.3. ОПИСАНИЕ И РЕЗУЛЬТАТ ЭКСПЕРИМЕНТАЛЬНОЙ ПРОВЕРКИ ДОСТОВЕРНОСТИ ФОРМУЛЫ ОЦЕНКИ ВЕРОЯТНОСТИ КЭШПОПАДАНИЙ
5.4. ОПИСАНИЕ И РЕЗУЛЬТАТ ИССЛЕДОВАНИЙ ЭФФЕКТИВНОСТИ ПРЕДЛОЖЕННОГО ЭВРИСТИЧЕСКОГО АЛГОРИТМА БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ
5.5. ПРИМЕР ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ ПРЕДЛОЖЕННОГО МЕТОДА ПРИМЕНЕНИЯ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ
5.5.1. Исходное отношение в момент создания БД.
5.5.2. Улучшение системной производительности
при проведении бинарной вертикальной кластеризации.
5.5.3. Вертикальная кластеризация в системах с нестабильным распределением частот вызовов запросов
5.6. ВЫВОДЫ ПО ПЯТОЙ ГЛАВЕ
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А. РЕАЛИЗАЦИЯ МЕТОДА СУЖЕНИЯ ОБЛАСТИ
ПОИСКА В СРЕДЕ .
ПРИЛОЖЕНИЕ Б. ПРИМЕРЫ РЕЗУЛЬТАТОВ ИСПЫТАНИЙ ДОСТОВЕРНОСТИ ОЦЕНКИ ВЕРОЯТНОСТИ КЭШПОПАДАНИЙ 7 ПРИЛОЖЕНИЕ В. ПРИМЕРЫ РЕЗУЛЬТАТОВ ИСПЫТАНИЙ ЭФФЕКТИВНОСТИ ПРЕДЛОЖЕННОГО ЭВРИСТИЧЕСКОГО
АЛГОРИТМА
ПРИЛОЖЕНИЕ Г. СВИДЕТЕЛЬСТВА ОБ ОФИЦИАЛЬНОЙ
РЕГИСТРАЦИИ ПРОГРАММЫ ДЛЯ ЭВМ
ПРИЛОЖЕНИЕ Д. АКТ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ В УЧЕБНЫЙ ПРОЦЕСС ДГТУ
ВВЕДЕНИЕ
Актуальность


Обосновывается актуальности исследования методов, модифицирующих логическую схему баз данных, особенно метода применения декомпозиции отношений, чтобы обеспечить соответствие физической схемы специфике работы приложений. Вторая глава посвящается обзору существующих методов применения декомпозиции отношений, полученных в результате логического проектирования, с целыо повышения производительности системы при заданной специфике приложений. По результатам проведенного анализа обосновывается необходимость разработки метода, применяющего декомпозицию отношений, для повышения производительности централизованных систем баз данных при заданной специфике приложений. В третьей главе формулируется задача бинарной вертикальной кластеризации отношения для повышения эффективности использования кэшпамяти централизованных систем баз данных при заданном потоке запросов и условии равной вероятности обращений к кортежам отношения и ее математическая модель. В основе математической модели лежит разработанный в данной диссертационной работе критерий оценки частоты кэшпопаданий для различных схем декомпозиции при заданном потоке запросов от приложений и условии равной вероятности обращений к кортежам отношения. Результат анализа показал необходимость разработки методов решения математической модели для формулированной задачи. Четвертая глава посвящено разработке метода решения формулированной в третьей главе математической модели для задачи повешения эффективности использования кэшпамяти централизованных баз данных. В общем случае задача, соответствующей данной математической модели, принадлежит к классу задач дискретного нелинейного программирования. Показано, что разработанный метод является двухэтапной оптимизацией. На первом этапе применяется эвристический подход, а на втором вариант метода ветвей и границ. В конце четвертой главе приводится сравнительный анализ реализации разработанного и известных методов вертикальной кластеризации при решении различных задач, в том числе и взятого из известной литературы. В пятой главе содержится описание разработанного программного стенда и проведенных на нем экспериментов. Приведены результаты статистической обработки экспериментальных исследований. В конце главы проанализированы возможности применения разработанного метода бинарной вертикальной кластеризации отношений как средства автоматизации реорганизации централизованных реляционных систем баз данных с целью обеспечения рациональной производительности. В заключении подводятся итоги диссертационного исследования. ГЛАВА 1. Цель любой информационной системы обработка данных об объектах реального мира. В широком смысле слова база данных эго совокупность сведений о конкретных объектах реального мира в какойлибо предметной области. Таким образом, база данных это информационная модель предметной области. Каждый конечный пользователь должен получать возможность взаимодействовать с информационной системой на понятном ему языке, в соответствии с его представлением о предметной области. Представление каждого пользователя описывает явления и объекты из предметной области лишь с некоторой точностью, необходимой для его деятельности. Получается такое представление путем выделения основных, с точки зрения пользователя, явлений, объектов, свойств и отбрасыванием второстепенных. Процесс отвлечения от ряда свойств и отношений изучаемого явления с одновременным выделением интересующих исследователя свойств называется абстрагированием. Реализуется представление конечного пользователя в информационной системе с помощью приложений. Так как обычно имеется несколько пользователей информационной системы, то в БД должны быть реализованы несколько представлений. Образы объектов и явлений реального мира, выделенные на основании представлений пользователей, записываются в памяти ЭВМ в цифровом виде. При этом возникает задача разработать такую архитектуру баз данных, которая позволила бы весь период эксплуатации БД обеспечивать стабильное развитие и, при необходимости, простую модификацию баз данных, разрабатываемых с помощью различных СУБД. Следовательно, перед разработчиками архитектуры БД стояла задача, аналогичная задаче стандартизации архитектуры компьютерных сетей.