Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Метод вертикальной кластеризации для реляционных систем хранения и обработки информации
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Актуальность исследования. Методы проектирования баз данных (БД) имеют большое практическое значение при создании любых информационных систем. Как известно, два важнейших этапа проектирования БД — это логическое и физическое проектирования. Целью логического проектирования является создание абстрактной логической модели предметной области, которая не зависит от способов реализации и использования… Читать ещё >

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

Содержание

  • ГЛАВА 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. АЛГОРИТМ БИНАРНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ В VP
      • 2. 6. 1. Процедура разбиения и критерий оценки качества схемы разбиения
      • 2. 6. 2. Пример выполнения процедуры разбиения
      • 2. 6. 3. Процедура смещения
      • 2. 6. 4. Выводы по алгоритму BVP
    • 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. ПОСТАНОВКА ЗАДАЧИ ПРИМЕНЕНИЯ БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ В ЦЕНТРАЛИЗОВАННЫХ СИСТЕМ БАЗ ДАННЫХ
    • 3. 6. АНАЛИЗ ВОЗМОЖНОСТИ ПРИМЕНЕНИЯ ИЗВЕСТНЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ (II)
    • 3. 7. ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ
  • ГЛАВА 4. РАЗРАБОТКА МЕТОДА БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ
    • 4. 1. РЕШЕНИЯ ЗАДАЧИ (3.5.15 — 3.5.19) АЛГОРИТМОМ ПОЛНОГО ПЕРЕБОРА
    • 4. 2. ФОРМУЛИРОВКА ЗАДАЧИ-ИСТОКА И ЕЕ ОСЛАБЛЕННОЙ ЗАДАЧИ
    • 4. 3. МЕТОД РЕШЕНИЯ ЗАДАЧИ-ИСТОКА ПРИ С *
      • 4. 3. 1. Лемма 1: о нахождении оптимального решения ослабленной задачи на краевой линии (4.2.6)
      • 4. 3. 2. Решение ослабленной задачи
      • 4. 3. 3. Лемма 2: о свойстве оптимального решения задачи-истока
      • 4. 3. 4. Лемма 3: о допустимости решения задачи-истока, полученного целочисленным округлением некоторого допустимого решения ослабленной задачи
      • 4. 3. 5. Лемма
      • 4. 3. 6. Теорема об области, содержащей оптимальное решение задачи-истока
      • 4. 3. 7. Пример реализации метода сужения интервала поиска в среде Maple
    • 4. 4. ЭВРИСТИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ ПОТЕНЦИАЛЬНОГО МНОЖЕСТВА СХЕМ ВЕРТИАКЛЬНОЙ КЛАСТЕРИЗАЦИИ
    • 4. 5. ПРЕДЛОЖЕННЫЙ ЭВРИСТИЧЕСКИЙ АЛГОРИТМ БИНАРНОЙ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ ОТНОШЕНИЯ
    • 4. 6. СРАВНИТЕЛЬНЫЙ АНАЛИЗ РЕАЛИЗАЦИИ АЛГОРИТМОВ ВЕРТИКАЛЬНОЙ КЛАСТЕРИЗАЦИИ
      • 4. 6. 1. Реализация алгоритма BVP
      • 4. 6. 2. Реализация графического алгоритма Наватхе
      • 4. 6. 3. Реализация эвристического алгоритма Ма
      • 4. 6. 4. Реализация предложенного алгоритма HBVP
    • 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. ВЫВОДЫ ПО ПЯТОЙ ГЛАВЕ

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

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

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

Существуют три основных метода решения этой задачи: денормализация, горизонтальная кластеризация и вертикальная кластеризация. Вертикальная кластеризация является задачей NP-сложности и представляет наибольший интерес для научного исследования. По сути, этот метод является развитием классической теории нормализации, который также реализуется через декомпозицию отношений, но с учетом распределения частот требования атрибутов приложениями. Цель этой декомпозиции — повышение общей производительности приложений и производительности системы в целом. Эта проблема достаточно хорошо исследована в зарубежной литературе. К сожалению, на русском языке редко встречаются даже переводы зарубежных работ по данной тематике. Следует отметить, что в существующих в настоящий момент зарубежных работах рассматривается проектирование только систем распределенных БД. Но очевидно, что доля централизованных систем реляционных БД значительно больше, чем распределенных.

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

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

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

1. проанализировать существующие методы применения вертикальной кластеризации отношений при проектировании систем баз данных;

2. разработать математическую модель задачи бинарной вертикальной кластеризации отношений для повышения эффективности использования кэшпамяти в централизованных системах баз данных;

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

4. разработать программные средства для экспериментального исследования предложенного метода вертикальной кластеризации и эффективности алгоритмов его реализации.

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

Существенные научные результаты, полученные в диссертации:

1. Критерий оценки частоты кэш-попаданий для метода вертикальной кластеризации отношений при заданном потоке запросов и условии равной вероятности обращений к кортежам отношения, экспериментальная проверка которого установила, что оценка относительного отклонения от теоретического значения не превышает 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%.

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

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

4. Алгоритм приближенного решения задачи декомпозиции отношений с критерием оценки частоты кэш-попаданий при заданном потоке запросов и при условии равной вероятности обращений к кортежам отношения, для которого на репрезентативной выборке оценка математического ожидания отклонения от точного решения составляет 5%, а среднее квадратическое отклонение 1%.

Практическая значимость диссертационной работы заключается в следующем:

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

2. Зарегистрированный в Отраслевом фонде алгоритмов и программ (ОФАП) «Программный стенд для исследования алгоритмов кэширования» позволяет исследовать частоты кэш-попаданий при кэшировании различных схем декомпозиции отношения. Зарегистрированная в ОФАП «Программа для вертикального бинарного разбиения отношений РБД» позволяет исследовать эффективность приближенного решения задачи декомпозиции отношения в сравнении с алгоритмом полного перебора.

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

Апробация диссертационной работы. Основные результаты диссертационной работы получили апробацию на следующих международных конференциях: на 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 печатных работ (одна в издании, включенном в перечень ВАК), в которых отражены основные результаты диссертации.

Структура и объём работы. Диссертация состоит из введения, 5 глав, заключения, списка литературы и 5 приложений. Основная часть работы изложена на 158 страницах машинописного текста, 34 рисунках, 38 таблицах.

5.6. ВЫВОДЫ ПО ПЯТОЙ ГЛАВЕ.

• Разработаны два программных комплекса для экспериментального исследования теоретических разработок. С их помощью были проведены проверка достоверности разработанного критерия оценки вероятности кэш-попаданий и испытание эффективности разработанного эвристического алгоритма HBVP.

• Результаты экспериментов, проведенных имитационным методом, показали, что относительное отклонение между теоретической и экспериментальной частотой кэш-попаданий составляет, в худшем случае, менее чем 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%, что доказывает высокую достоверность разработанной математической модели и разработанного критерия оценки вероятности кэш-попаданий.

• Результаты испытаний алгоритма HBVP показали, что по точности решения задачи алгоритм HBVP дает совпадающее решение с полным перебором в более 95% случаях, что является высоким показателем для класса эвристических алгоритмов. Это показывает высокую эффективность разработанного алгоритма HBVP.

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

ЗАКЛЮЧЕНИЕ

.

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

2. В работе показано, что в централизованных системах баз данных повышение эффективности использования кэш-памяти непосредственно приведет к повышению производительности системы в целом. Полученный критерий оценки частоты кэш-попаданий при заданной схеме декомпозиции, заданном потоке запросов приложений и условии равной вероятности обращений к кортежам отношения позволяет реализовать метод рациональной вертикальной кластеризации отношений для повышения эффективности использования кэш-памяти в централизованных системах баз данных. Разработана математическая модель задачи бинарной вертикальной кластеризации с использованием критерия оценки частоты кэш-попаданий в централизованных системах при заданном потоке запросов приложений и условии равной вероятности обращений к кортежам отношения. Полученная задача принадлежит к классу задач дискретного нелинейного программирования с четырьмя параметрами (AvA2,NRl, NR2), в которых А, и А2 являются ограниченными дискретными множествами, a NKl и NR2 — целыми ограниченными числами.

3. Предложенный метод (HBVP) решения поставленной задачи дискретного программирования, состоящий из двух этапов, позволяет выполнять рациональную декомпозицию отношений с целью повышения эффективности использования кэш-памяти в системах обработки и хранения информации. При этом для первого этапа разработан алгоритм построения потенциального множества схем декомпозиции (АпА2), который сокращает количество рассматриваемых схем декомпозиции. Алгоритм построен на принципе «жадного выбора» эвристического подхода применительно к специфике данной математической модели. Эффективность алгоритма, т. е. доля полного совпадения полученной этим алгоритмом схемы по сравнению со схемой, полученной полным перебором, составляет более 95%. Для второго этапа разработан метод сужения области поиска значения параметров (Л^,/^), соответствующего оптимальному решению задачи нелинейного целочисленного программирования при известном значении параметров А, и А2. Предложенный метод, реализуя фактически идею метода ветвей и границ, за каждую итерацию позволяет сузить на порядок интервал неопределенности. Метод сужения области поиска параметров (NRl, NR2) и алгоритм построения потенциального множества схем декомпозиции могут быть использоваться как в совокупности между собой, так и в сочетании с другими подходящими существующими методами, что делает их использование более гибким.

4. Для экспериментального исследования предложенных математических моделей и разработанного метода вертикальной кластеризации отношений реализованы два программных комплекса, зарегистрированных в отраслевом фонде алгоритмов и программ. С их помощью были проведены проверка достоверности разработанного критерия оценки вероятности кэш-попаданий и испытание эффективности разработанного эвристического алгоритма HBVP. Результаты экспериментов, проведенных имитационным методом, показали, что относительное отклонение между теоретической и экспериментальной частотами кэш-попаданий составляет, в худшем случае, менее 2% с математическим ожиданием 0,1% и средним квадратическим отклонением 0,23%, что доказывает высокую достоверность разработанной математической модели и критерия оценки вероятности кэш-попаданий. Экспериментально доказана высокая эффективность разработанного метода вертикальной кластеризации. Таким образом, основные задачи диссертационной работы решены полностью и достигнута ее цель.

Показать весь текст

Список литературы

  1. Adrian Sergiu Darabant. A new approach in fragmentation of distributed object oriented databases using clustering techniques. // Studia Univ. Babes-Bolyai, Informatica, Volume L, Number 2, 2005.
  2. Baiao F. A strategy for the Distributed Design of Object Oriented Databases. // Thesis, COPPE/UFRJ, Rio de Janeiro, Brazil, 1997. Bail.
  3. Baiao F., Mattoso M. A Mixed Fragmentation Strategy for Distributed OO Databases. // Proceedings of The second Workshop on CSCW in Design, pp. 42−48, Bangkok, Thailand, 1997. Bai2.
  4. Bellatreche L. et.al. Vertical Fragmentation in Distributed Object Database Systems with Complex Attribute and Methods. // Proceedings of the 7th International Workshop on Database and Expert Systems Applications, 1996. Belli.
  5. Ceri S., Navathe S.B. A Comprehensive Approach to Fragmentation and Allocation of data in a Distributed Databases. // Proceedings of the IEEE COMPCON Conference, 1983. Nav4.
  6. Ceri S., Navathe S.B., and Wiederhold G. Distributed design of Logical database schemas. // IEEE Transaction on Software Engineering, 9 (4), 1983. Nav5.
  7. Ceri S., Negri M., and Pelagatti G. Horizontal data partitioning in database design. // Proceedings if the ACM SIGMOD International Conference on Management of Data. SIGPLAN Notices, 1982. Ceril.
  8. Chakravarthy S., Jeyakumar Muthuraj, Varadarajan R., and Navathe S.B. A formal approach to the vertical partitioning problem in Distributed Database
  9. Design. // Proceedings of Second International Conference on Parallel and Distributed Information. Chakl.
  10. Chu P.C. A transaction-oriented approach to attribute partitioning. // Information Systems, vol. 17, no. 4, pp. 329−342, 1992. Chu2.
  11. Chu W.W., Ieong I.T. A transaction-based approach to vertical partitioning to vertical partitioning for relational databases. //Tech. rep. UCLA, 1991. Chul.
  12. Cornell D.W., Yu P. S. A vertical partitioning algorithm for relational databases. // Proceedings of International Conference on Data Engineering, IEEE, pp. 30−35, 1987. Cornl.
  13. Ezeife C.I., Ken Barker. Vertical Class Fragmentation in a Distributed Object Based System". // Technical Report 94−03, Dept. of Computer Science, Univ. of Manitoba, 1994. Ezeifel.
  14. Ezeife C.I., Ken Barker. A Comprehensive Approach to Horizontal Class Fragmentation in a Distributed Object Based System.// Distributed and Parallel Databases, 3(3), pp. 247−272, 1995. Ezeife2.
  15. Ezeife C.I. and Ken Barker. A Distributed Object Based Design Technique. // Natural Science and Engineering Research Council, Canada, 1995. Ezeife3.
  16. Fernanda Baiao, Marta Mattoso. A Mixed Fragmentation Algorithm for Distributed Object Oriented Databases. // Proceedings of the Ninth International Conference on Computing Information, Winnipeg, Canada, 1998. Bai3.
  17. Fleming C. and Von Halle B. Handbook of Relational Database Design. // Addison-Wesley, 1989. Fleml.
  18. Hoffer J.A. An integer programming formulation of computer database design problems. // Inf. Sci., 11 (July 1976), 29−48. Hoff2.
  19. Hoffer J.A. and Severance D.G. The use of cluster analysis in physical database design. //Proceedings of the 1st International Conference on Very large Databases, Vol. l, No. 1, 1975. Hoffl.
  20. Hui Ma, Klaus-Dieter Schewe and Markus Kirchberg. A Heuristic Approach to Vertical Fragmentation Incorporating Query. // Massey University, 1. formation Science Research Centre & Department of Information Systems. — USA, 2006.
  21. Ismail Hababeh, Muthu Ramachandran and Nicholas Bowring. A Mathematical Approach for Modeling Data Allocation in Distributed Database Systems. // The Seventh Annual U.A.E. University Research Conference, April, 2006. Nicl.
  22. Jain A.K., Murty M.N., Flynn P.J. Data Clustering: A Review // ACM
  23. Computing Surveys, Vol. 31, No. 3, September 1999. Jainl.
  24. Jelenkovic P. R., Radovanovic A. Optimizing the LRU algorithm for Web caching. // 18th. International Teletraffic Congress, Berlin, Germany, 2003.
  25. Jeyakumar Muthuraj. A formal approach to the vertical partitioning problem in Distributed Database Design. // Master of Science Thesis, Dept. of Computer Science, Univ. of Florida. Muthl.
  26. Kennedy R. The Use of Access Frequencies in Database Organization. // Ph. D Dissertation, The Wharton School, Univ. of Pennsylvania, 155 pp, May 1973. Kenl.
  27. Lawrence R. Rabiner. A tutorial on Hidden Markov Models and selected applications in speech recognition. // Proceedings of the IEEE, VOL. 77, NO. 2, Feb 1989. http://www.cs.ubc.ca/~muphyk/Bayers/rabiner.pdf. Rabl.
  28. Lin X., Orlowska M., and Zhang Y. A graph based cluster approach for vertical partitioning in database design. // Data and Knowledge Engineering, vol. 11, pp. 151−169, 1993. Zhang 1.
  29. Lorinda Visnick. Clustering Techniques A Technical Whitepaper. // www.objectstore.net Visnickl.
  30. Malinowski E. Fragmentation Techniques for Distributed Object-Oriented Databases. // Thesis, Univ. of Florida, USA, 1996. Mall.
  31. Matthias Jarke, Jurgen Koch. Query Optimization in Database Systems. // Computing Surveys, Vol. 16, No. 2, June 1984. Jarl.
  32. McCormick W.T., Schweitzer P.J., and White T.W. Problem decomposition and data reorganization by a clustering technique. // Operation Research, vol.20, p.993−1009, 1972. Corml.
  33. Michael J. Franklin, Michael J. Carey, Miron Livny. Local disk caching for client-server database systems. // Proceedings of the 19th VLDB Confidence, Dublin, Irelang, 1993. Frankl.
  34. Narasimhaiah Gorla. A Methodology for Vertically Partitioning in a Multi-Relation Database Environment. // JCS&T Vol. 7 No. 3, 2007. Gorlal.
  35. Natallia Kokash. An introduction to heuristic algorithms. 2005// http://dit.unitn.it/~kokash/documents/Heuristic algorithms. pdf fNatl.
  36. Navathe S.B., Ceri S., Wiederhold G., Dou J. Vertical Partitioning Algorithms for Database Design. // ACM Transactions on Database Systems, vol. 9, no. 4, pp. 680−710, 1984. Navl.
  37. Navathe S.B., Kamalakar Karlapalem, and Minyoung Ra. A Mixed Fragmentation Methodology For Initial Distributed Database Design. // Database Systems R&D Center, University of Florida, USA, 1995. Nav3.
  38. Navathe S.B., Ra M. Vertical partitioning for database design: A graphical algorithm. // Proceedings of ACM SIGMOD International Conference on Management of Data, 1989. Nav2.
  39. Nemhauser G. Integer and Combinational Optimization. / G. Nemhauser, L. Wolsey. New York: Wiley, 1988.
  40. Ngo Thanh Hung, Grankov Michael Vasilevich. New Objective Function for Vertical Partitioning in Database System. // SYRCoDIS, 2008.
  41. Ngo Thanh Hung, Grankov Michael Vasilevich, A1 Zgool M.B. The Framework for Study of Caching Algorithm Efficiency. // SYRCoDIS, 2008.41.0zsu M.T. and Valduriez P. Principles of Distributed Database Systems. // Prentice Hall, 1991. Ozsul.
  42. Parker G. Discrete Optimization / G. Parker, R. Rardin. Orlando FL: Academic Press, 1988.
  43. Pernul G., Karalapalem K., and Navathe S.B. «Relational database organization based on views and fragments.» // Proceedings of the second International Conference on Data and Expert System Applications, Berlin, 1991. Nav6.
  44. Rex Blankinship, Alan R. Hevner, S. Bing Yao. An iterative Method for Distributed Design. // Proceedings of the 17th International Conference on Very Large Data Bases, 1991. Yaol.
  45. Rogers U. Denormalization: Why, what and how? // Database Programming and Design, 2(12), 1989, 46−53. Rogl.
  46. Sanjay Agrawal, Vivek Narasayya, and Beverly Yang. Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design. // The 2004 ACM SIGMOD International Conference on Management of Data. June 2004.
  47. Savonnet, M. et. al. Using Structural Schema Information as Heuristics for Horizontal Fragmentation of Object Classes in Distributed OODB. // Proceedings IX International Conference on Parallel and Distributed OODB, pp. 732−737. France, 1996.
  48. Sharma Chakravarthy, Jaykumar Muthuraj, Ravi Varadarajan, Navathe Shamkant В. An Objective Function for Vertically Partitioning Relations in Distributed Databases and its Analysis // Distributed and Parallel Databases 2(2): 183−207(1994).
  49. Shin D. and Irani K.B. Fragmenting relation horizontally using a knowledge-based approach. // IEEE Transactions on Software Engineering, 17 (9), 1991.
  50. Starobinski D., Tse D. Probabilistic methods for Web caching. // Performance evaluation, 46(2−3):125−137, 2001.
  51. Steve Rozen, Dennis Shasha. Automating Physical Database Design A Universal Approach and Its Evaluation. // 1993.
  52. Steve Rozen. Automating Physical Database Design An Extensible Approach. // PhD thesis/New York University. — New York, 1993.
  53. Suk-Kyu Song and Narasimhaiah Gorla. A Genetic Algorithm for Vertical Fragmentation and Access Path Selection. // The Computer Journal, Vol.43, No.1,2000.
  54. Sylvain Guinepain and Le Gruenwald. Research Issues in Automatic Database Clustering. // SIGMOD Record, Vol.34, No. l, March, 2005.
  55. Wai Gen Yee, Michael J. Donahoo, Shamkant B. Navathe. A framework for server data fragment grouping to improve scalability in intermittently synchronized databases. // In Proc. ACM Conf. on Information and Knowledge Management, 2000.
  56. В.Ю. Комплексное применение методов дискретной оптимизации / В. Ю. Алексеев. М.: Наука, 1987.
  57. Дж. Дискретная математика и комбинаторика / Дж Андерсон. — М.: Вильяме, 2003.
  58. А.А. Методы и модели анализа данных: OLAP и Data Mining /
  59. A.А. Барсегян, М. С. Куприянов, В. В. Степаненко. Санкт-Петербург: изд-во BHV, 2004. — 336с.
  60. В.В., Савинков В. М. Проектирование баз данных информационных систем / В. В. Бойко, В. М. Савинков. Москва, 1989.
  61. JI.A. Генетические алгоритмы / JI.A. Гладков, В. В. Курейчик,
  62. B.М. Курейчик. Москва: ФИЗМАТЛИТ, 2006. — 320с.
  63. О.Л. Основы алгоритмизации и программирования / О. Л. Голицына, И. И. Попов. Москва: изд-во «Высшая школа», 2005. — 320с.
  64. М.В., Нго Тхань Хунг, «Повышение вероятности удачного обращения к кэш-памяти вертикальной кластеризацией», Сборник аспиранта ДГТУ, 2008.
  65. Нго Т. X. Алгоритм рационального разбиения отношения на проекции при использовании ограниченной кэш-памяти / Т. X. Нго // Математические методы в технике и технологиях: сб. тр. XXI меж. науч. кон. Саратов, 2008.
  66. Ю.И. Методы оптимизации / Ю. И Дегтярев. — Москва: изд-во «Советское радио», 1980. 272с.
  67. К. Дж. Введение в системы баз данных. 7-ое издание / К. Дж Дейт. -М.: Вильяме, 2001. 1072с.
  68. В.М. Математическая статистика / В. М. Иванова, В. Н. Калинина, JT.A. Нешумова, И. О. Решетникова. Москва: изд-во «Высшая школа», 1981.-371с.
  69. И.П. Введение в базы данных Учебное пособие / И. П. Карпова // Московский государственный институт электроники и математики. -Москва, 2004.
  70. В.В. Основы проектирования реляционных баз данных/ В. В. Кириллов // Лекции/Санкт-Петербургский Государственный институт точной механики и оптики. Санкт-Петербург, 1995.
  71. Д. Искусство программирования. Том 3. Сортировка и поиск / Д. Кнут. Москва: изд-во «Финансы и статистика», 2002.
  72. М.М. Дискретная оптимизация целочисленное программирование/ М. М. Ковалев. — М.: УРСС, 2003.
  73. Т.М., Бегг К. Э., Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и Практика / Т. М. Коннолли, К. Э. Бегг, А. Страчан // Пер. от англ. М.: Вильяме, 1998.
  74. Г. Математические методы статистики / Г. Крамер. М.: Регулярная и хаотическая динамика, 2003. — 648с.
  75. Н.Ш. Теория вероятностей и математическая статистика / Н. Ш. Кремер. -М.: изд-во «Юнити», 2007. 551с.
  76. Н. Теория графов. Алгоритмический подход / Н. Кристофидес. Москва: изд-во «Мир», 1978.
  77. С.Д. Введение в реляционные базы данных Лекция. // Центр Информационных Технологий, Москва, 2003. Кузн2.
  78. С.Д. Информационно-аналитические материалы: Основы современных баз данных. // Центр Информационных Технологий -http://www.citmgu.ru. Кузн1.
  79. С.Д. Тенденции в мире систем управления базами данных. // Материалы конференции «Корпоративные базы данных '96м, 1996. КузнЗ.
  80. Ю.Н. Математическое программирование / Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Москва: изд-во «Высшая школа», 1976. 352с.
  81. В.М. Дискретная математика. Ч. З. Оптимизационные задачи на графах. Таганрог: Изд-во «ТРТУ», 1998.
  82. Дж., Лондон К. Управление информационными системам, 7-е издание // Питер, 2005, 912с.
  83. Ю.П. Адаптивные методы краткосрочного прогнозирования временных рядов: Учеб. Пособие. М.: изд-во «Финансы и статистика», 203, -416с.
  84. Лю Б. Теория и практика неопределенного программирования. // Москва, БИНОМ, Лаборатория знаний, 2005.
  85. Майкл Блаха. Ссылочная целостность является важной для баз данных. // Пер. Сергеем Кузнецовом, www.citforum.ru, 2005. Майкл1.
  86. Н.Н. Методы оптимизации / Н. Н. Моисеев, Ю. П. Иванилов, Е. М. Столярова. Москва: изд-во «Наука», 1978. 352с.
  87. Нго Т. Х. Разработка методов вертикальной кластеризации отно-шений в реляционных базах данных / Т. Х. Нго // Осенняя школа молодых ученных: сб. тр. / ТГТУ. Тамбов, 2008.
  88. Нго Тхань Хунг. Разработка тестов быстродействия информаци-онных систем с использованием цепей Маркова / Тхань Хунг Нго // Математические методы в технике и технологиях: сб. тр. XX меж. науч. кон. Ярославль, 2007.
  89. Нго Т. X. Программный стенд для исследования эффективности алгоритмов кэширования / Т. X. Нго, Б. М. Аль-Згуль // Математи-ческие методы в технике и технологиях: сб. тр. XXI меж. науч. кон. Саратов, 2008.
  90. JI.A. Теория вероятностей и ее инженерные приложения / JLA. Овчаров, Е. С. Вентцель. Москва: изд-во «Высшая школа», 2007. 491с.
  91. В. И др. Использование Oracle8/8i.: пер. с англ. М.: Вильяме, 2000.- 1024 с. [Вил1]
  92. Петер Пин-Шен Чен. Модель «сущность-связь» шаг к единому представлению о данных. // Пер. ACM Transactions on Database Systems, v. l, № 1, 1976.
  93. K.A. Оценка и планирование эксперимента / К. А. Пупков, Г. А. Костюк. Москва: изд-во «Машиностроение», 1977. 118с.
  94. Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, А. Део. Москва: изд-во «Мир», 1980.
  95. Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Москва: изд-во «Мир», 1986. 320с.
  96. И.М. Метод Монте-Карло / И. М. Соболь. Москва, 1978.
  97. М.Н. Статистические методы обработки результатов механических испытаний / М. Н. Степнов. — Москва: изд-во «Машиностроение», 1985. -232с.
  98. Э. Современные операционные системы. Питер, 2004.
  99. Т., Фрай Дж. Проектирование структур баз данных. Москва, 1985.
  100. А.Т. Введение в исследование операций / А. Т. Хэмди. М: изд-во «Вильяме», 2001. — 912с.
  101. Э.И. Основы теории статистических измерений / Э. И. Цветков. -Ленинград: ЭнергоАтомИздт, 1986. -256с.
Заполнить форму текущей работой

Сессия? Спокойно!