Разработка методов распараллеливания запросов в гетерогенных системах реляционных баз данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Локшин, Марк Викторович

• Локшин, Марк Викторович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Локшин, Марк Викторович

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

1. АНАЛИЗ СОВРЕМЕННЫХ МЕТОДОВ ОБРАБОТКИ SQL-ЗАПРОСОВ В СУБД.

1.1 Архитектуры параллельных систем.

1.2 Классификация архитектур параллельных систем баз данных.

1.3 Масштабируемость параллельных систем обработки данных.

1.4 Формы параллелизма. Параллельное исполнение операторов языка SQL

1.5 Методы поиска субоптимальных алгоритмов исполнения запроса.

1.6 Основные понятия и обозначения реляционной алгебры.

Выводы к главе 1.

ГЛАВА 2. ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ ДЛЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ЗАПРОСОВ С ИСПОЛЬЗОВАНИЕМ ИЗБЫТОЧНОСТИ

ДАННЫХ.

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

2.2. Декомпозиция запроса с отображением его в древовидную структуру41 2.3 Доказательства эквивалентности преобразования запросов к запросам, допускающим параллельное исполнение.

2.4. Исследование возможности параллельного исполнения модифицированных запросов.

2.5. Априорные оценки времени исполнения запросов.

Выводы к главе 2.

ГЛАВА 3. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ ЗАПРОСОВ ДЛЯ

ПАРАЛЛЕЛЬНОГО ИСПОЛНЕНИЯ.

3.1 Алгоритм для преобразования запросов с использованием условий фильтрации в инструкции WHERE.

3.2 Алгоритм для преобразования запроса с агрегирующими функциями и оператором группирования атрибутов.

3.3 Алгоритм преобразования запроса с использованием инструкции соединения таблиц JOIN.

3.4 Алгоритмы для преобразования запросов с использованием ограничений на количество кортежей в инструкции SELECT.

3.5 Алгоритм для преобразования запроса с использованием подзапросов

3.6 Применение инструкции ORDER BY при параллельном исполнении запроса.

Выводы к главе 3.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

ЭФФЕКТИВНОСТИ МЕХАНИЗМА РАСПАРАЛЛЕЛИВАНИЯ ЗАПРОСОВ

4.1 Программная реализация распараллеливания 8(ЗЬ-запросов. Структура, особенности реализации, методика выбора алгоритма преобразования

4.2 Проектирование информационной структуры базы данных для проведения тестирования.

4.3 Результаты экспериментального исследования распараллеливания запросов.

Выводы к главе 4.

Введение диссертации (часть автореферата) на тему «Разработка методов распараллеливания запросов в гетерогенных системах реляционных баз данных»

Актуальность темы:

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

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

В настоящее время СУБД используются практически во всех сферах человеческой деятельности, связанных с хранением и переработкой информации. Прогресс, достигнутый в области технологий баз данных, в значительной мере базируется на реляционной модели, предложенной Э. Коддом [57] на рубеже 60-х - 70-х годов XX века. За свою тридцатилетнюю историю реляционные СУБД прошли путь от научно-исследовательских прототипов, наиболее значительными из которых являются System R [18, 43] и Ingres [91, 89], до коммерческих продуктов, способных хранить и обрабатывать терабайты информации. Однако научная и практическая деятельность человека выдвигает все новые масштабные задачи, требующие обработки сверхбольших баз данных.

Анализируя существующие методы работы с данными, можно прийти к выводу, что они не в полной мере отвечают всем предъявляемым к ним в настоящий момент требованиям. Об этом, в частности, свидетельствуют интенсивные научные исследования в области баз данных, проводимые в настоящее время в России и за рубежом [13, 73].

Возникновение сверхбольших баз данных связано с расширением видов и сфер применения СУБД. Примерами новых приложений баз данных являются электронная коммерция [72], электронные библиотеки [14, 63], геоинформационные системы [39], мультимедийные архивы [76], научные базы данных [48, 92].

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

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

Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских прототипов к полнофункциональным коммерческим продуктам, поставляемым на рынок высокопроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести целый ряд продуктов - DB2 Parallel Edition [11], NonStop SQL [37] и NCR Teradata[21]. Однако стоимость такого специализированного программного обеспечения для данных систем сопоставима, а в некоторых случаях и выше стоимости аппаратной составляющей.

Подобные системы объединяют сотни процессоров и жестких дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [97, 10]. Одно из них -дальнейшее развитие методов оптимизации запросов для исполнения в составе параллельных и распределенных систем баз данных. Кроме того, многими исследователями справедливо указывается на ограничения в масштабируемости большинства существующих параллельных баз данных из-за ограничений, присущих архитектуре систем, поддерживающих их работу [20]. При большом количестве процессоров в системах такого рода начинают возникать конфликты доступа к разделяемой памяти, что может привести к серьезной деградации общей производительности системы [95]. В соответствии с этим реальная масштабируемость так называемых SMP систем ограничивается 32 процессорами [98].

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

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

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

Диссертационная работа выполнена в рамках научного направления Воронежского государственного технического университета - «Вычислительные системы и программно-аппаратные электротехнические комплексы».

Цель работы:

Целью работы является разработка методов параллельного исполнения БОЬ-запросов в гетерогенных архитектурах для повышения производительности распределенных СУБД.

Задачи исследования:

Исходя из указанных целей исследования, его основными задачами являются:

1. Выполнить анализ современных архитектур СУБД и методов, применяемых в них для параллельного исполнения БС^Ь-запросов, обобщить анализ современного состояния исследований в области применения методов параллельной обработки запросов.

2. Разработать эффективные методы распараллеливания запросов в гетерогенных средах с доказательством их корректности.

3. Разработать алгоритмы и программные средства для параллельного исполнения БС)Ь-запросов, обеспечить их совместимость с существующими СУБД.

4. На основе полученных результатов реализовать систему для распараллеливания запросов и провести вычислительный эксперимент, используя разработанные методы и алгоритмы. Методы исследования:

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

Научная новизна работы:

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

• метод параллельного исполнения 8(^Ь-запросов, ориентированный на использование источников данных, не поддерживающих параллелизм в гетерогенных средах, отличительной особенностью которого является динамическое разделение отношений запроса на диапазоны обработки;

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

• априорные оценки эффективности распараллеливания запросов, отличающиеся учетом особенностей исполнения запросов в гетерогенных системах с репликацией данных, и позволяющие быстро оценить целесообразность применения созданного метода распараллеливания БС^Ь-запросов на этапе конфигурирования системы;

• структура программного обеспечения препроцессора СУБД, отличающегося возможностью распараллеливания 8(^)Ь-запросов и обеспечивающего ускорение их обработки средствами СУБД, не ориентированных на параллельное исполнение.

Практическая значимость работы.

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

Реализация и внедрение результатов работы. Теоретические и практические результаты работы реализованы в специальном программном комплексе исполнения аналитических запросов в рамках системы автоматизации предприятия. С его использованием разработана программа "Учет потребления электроэнергии абонентами юридическими лицами", которая внедрена в практическую деятельность ОГУП "Западные межрайонные электрические сети" (г. Елец) и зарегистрирована в Государственном фонде алгоритмов и программ [31].

Апробация работы:

Основные результаты работы докладывались и обсуждались на Международной научно-практической конференции «Единое информационное пространство» (Днепропетровск, 2003); ИХ - X Международных открытых научных конференциях «Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях» (Воронеж, 2003-2005); XI Всероссийской научно-методической конференции «Телема-тика'2004» (Санкт-Петербург, 2004); II Всероссийской научно-технической конференции «Вузовская наука - региону» (Вологда, 2004); VIII Международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (Тамбов, 2004).

Публикации:

Основные результаты диссертации опубликованы в 11 научных работах. Список работ включен в список литературы.

Структура и объем работы:

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Локшин, Марк Викторович

Выводы к главе 4

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

В результате проведенного анализа времени исполнения запросов получены следующие выводы:

• при исполнении всех исследуемых запросов оказалось возможным привести их к форме, которая позволила уменьшить время исполнения, с учетом параллельной работы;

- • для большинства запросов, при увеличении количества вычислительных узлов, система демонстрировала расширяемость близкую к линейной;

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

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

ЗАКЛЮЧЕНИЕ

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

1. На основе анализа методов параллельной обработки запросов в существующих СУБД был сделан вывод о том, что в настоящее время при решении задач параллельной обработки данных в недостаточной мере используется потенциал доступных аппаратных архитектур. Отчасти это связано с отсутствием методов и соответствующего программного обеспечения для выполнения задач, поставленных в целях исследования. Методы для параллельной обработки БС^Ь-запросов в гетерогенных СУБД на текущий момент не достаточно развиты. В связи с вышеизложенными фактами была выявлена необходимость создания новых методов параллельной обработки БС^Ь-запросов, которые могли бы эффективно справляться с поставленными целями.

2. Разработан метод распараллеливания БС^Ь-запросов в СУБД на основе эквивалентного преобразования запросов к форме, допускающей параллельное исполнение для применения в гетерогенных средах с использованием массово-параллельных архитектур.

3. Получены априорные оценки общего времени параллельного исполнения преобразованных 8С)Ь-запросов.

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

5. Экспериментальное исследование разработанного метода для распараллеливания 8С>Ь-запросов подтвердило его эффективность на системах с различной конфигурацией.

6. С использованием метода распараллеливания БС^Ь-запросов создана программа для ОГУП «Западные межрайонные электрические сети» (г.

Елец), входящая в состав системы автоматизации работы предприятия, обеспечивающая исполнение аналитических запросов.

Список литературы диссертационного исследования кандидат технических наук Локшин, Марк Викторович, 2005 год

1.Андреев А.Н., Воеводин Вл.В., Жуматий С.А. Кластеры и суперкомпьютеры - близнецы или братья? // Открытые системы. -2000. -№5-6. -С. 9* 14.

2. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы.

4. М.: Издательский дом «Вильяме», 2000. -С. 384.

5. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2002. 608 с.

6. Волков В.В. Тесты ТРС // СУБД. -1995. -№2. -С. 70-78.

7. Вьейра P. SQL Server 2000. Программирование. Часть 1, изд. -М.: Бином, 2004. 736 с.

8. Вьейра P. SQL Server 2000. Программирование. Часть 2, изд. -М.: Бином, 2004. 808 с.

9. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. -М. «Вильяме», 2003. 1088 С.

10. Дейт К. Дж. Введение в системы баз данных. -М. Вильяме, 2000 — 846 с.

11. Зильбершатц А. Стоунбрейкер М, Ульман Д. Базы данных: достижения и перспективы на пороге 21-го столетия // СУБД. -1996. -№3. -С. 103117.

12. Игнатович Н. Семейство реляционных баз данных IBM DB2 // СУБД. -1997. -№2. -С. 5-17.

13. Кнут Д.Э. Искусство программирования, т. 3. Сортировка и поиск, 2-е изд. -М.: Издательский дом «Вильяме», 2000. -832 с.

14. Когаловский М.Р. Энциклопедия технологий баз данных. -М.: Финансы и статистика, 2002. -800 с.

15. Когаловский М.Р., Новиков Б.А. Электронные библиотеки новый класс информационных систем // Программирование. -2000. -№3. -С. 3-8.

16. Коннолли Т., Бегг К, Страчан А. Базы данных: проектирование, реализация и сопровождение. Теория и практика. М.: Вильяме, 2000. -1120 с.

17. Корнеев В.В. Архитектуры с распределенной разделяемой памятью // Открытые системы. -2001. -№3. -С. 15-23.

18. Корнеев В.В. Параллельные вычислительные системы. -М.: "Нолидж", 1999. -320 с.

19. Кузнецов С Д. Развитие идей и приложений реляционной СУБД System R // Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М/.ВИНИТИ, 1989. -С. 3-75.

20. Кузьминский М., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. -1995. -№6. -С. 33-40.

21. Кузьминский М. Архитектура S2MP свежий взгляд на cc-NUMA// Открытые системы. - 1997. № 2. -С. 14-21.

22. Лисянский К, Слободяников Д. СУБД Teradata для ОС UNIX // СУБД. -• 1997.-№5-6.-С. 25-46.

23. Локшин М.В. Модификация деревьев разбора для параллельного исполнения запроса. // Успехи современного естествознания. — 2004. №10. -С. 70-71.

24. Локшин М.В., Кравец О.Я. Построение систем для параллельной обработки запросов к СУБД. // Телематика'2004: Труды XI Всероссийской научно-методической конференции (7-10 июня 2004). -СПб:ИТМО.2004. -С. 94-95.

25. Мамаев Е. Шкарина Л., Microsoft SQL Server 2000 для профессионалов. -СПб: Питер2001. 1088 с.

26. Никитина Г. SQL Server и кластеры // СУБД. -1997. -№3. -С. 65-71.

27. Оззу Т., Валдуриз П. Распределенные и параллельные системы баз данных // СУБД. -1996. -№4. -С. 4-26.

28. Соколинский Л. Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом. Диссертация доктора физико-матаематических наук. - Челябинск, 2003. - 247 с.

29. Соколинский Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой // Программирование. 2001. № 6. - С. 13-29.

30. Хаманн Ф. Отказоустойчивая операционная система Tandem NonStop Kernel // Открытые системы. -1997. -№3. -С. 32-36.

31. Хендерсон К. Профессиональное руководство по Transact-SQL, изд. -СПб.: Издательство «Питер Пресс», 2005. -560 с.

32. Цветков В.Я. Геоинформационные системы и технологии. -М.: Финансы и статистика, 1998.

33. Чаудхари С. Методы оптимизации запросов в реляционных системах // СУБД. -1998. -№3. -С. 22-36.

34. Amza С., et al. ThreadMarks: Shared Memory Computing on Networks of Workstations // IEEE Computer. -1996. -Vol. 29, No. 2. -P. 18-28.

35. Astrakan M.M., et al. System R: Relational Approach to Database Management // ACM Transactions on Database Systems. -1976. -Vol. 1, No. 2. -P. 97-137.

36. Ballinger C., Fryer R. Born To Be Parallel: Why Parallel Origins Give Tera-data an Enduring Performance Edge // IEEE Data Engineering Bulletin. -1997. -Vol. 20, No. 2. -P. 3-12.

37. Baru C. K., et al. DB2 Parallel Edition // IBM System Journal. -1995. -Vol. 34, No. 2. -P. 292-322.

38. Bernstein P.A., et al. The Asilomar Report on Database Research // ACM SIGMOD Record. -1998. -Vol. 27, No. 4. -P. 74-80.

39. Brobst S., Robertson O. Taming Data Giants // DBMS №2. -1997. -C. 3849.

40. Brown P., Stonebraker M. BigSur: A System For the Management of Earth Science Data // VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. -Morgan Kaufmann, 1995. -P. 720-728.

41. Bruno N., Chaudhuri S. Exploiting Statistics on Query Expressions for Optimization // Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 June 2, 2002. -ACM Press, 1989. -P. 98-109

42. Bruno N., Chaudhuri S., Gravano L. Top-k selection queries over relational databases: Mapping strategies and performance evaluation // TODS 27(2), 2002-P. 153-187.

43. Bultzingsloewen G. Optimizing SQL Queries for Parallel Execution // ACM SIGMOD Record. -1989. -Vol. 18, No. 4. -P. 4-11.

44. Carter J., Wegman M. Universal classes of hash functions. Journal of Computer and System Sciences, 1979, № 18. -P. 143-154.

45. Chaudhuri S., Shim K. Including Group-by in Queiy Optimization // VLDB'94, Proceedings of 20th International Conference on Veiy Large Data

46. Bases, September 12-15, 1994, Santiago de Chile, Chile. -Morgan Kaufmann, 1994. -P. 354-366.

47. Chaudhuri S., Shim K. An Overview of Cost-based Optimization of Queries with Aggregates // Bulletin of the Technical Committee on Data Engineering. -1995,-Vol. 18, No. 3.-P. 3-9.

48. Chen M.-S., Yu P.S., Wu K.-L. Optimization of Parallel Execution for Multi-Join Queries // IEEE Transactions on Knowledge and Data Engineering. -1996. -Vol. 8, No. 3. -P. 416-428.

49. Cheng J.M., et al. IBM Database 2 Performance: Design, Implementation, and Tuning // IBM Systems Journal. -1984. -Vol. 23, No. 2. -P. 189-210

50. Codd E.F. A Relational Model of Data for Large Shared Data Banks // Communications of the ACM. -1970. -Vol. 13, No. 6. -P. 377-387.

51. Copeland G.P., Keller T. A Comparison Of High-Availability Media Recovery Techniques // Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 June 2, 1989. -ACM Press, 1989. -P. 98-109.

52. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries

53. That Contain Nested Subqueries, Aggregates, and Quantifiers. // VLDB'87,

54. Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. -Morgan Kaufmann, 1987. -P. 197-208.

55. Fox E.A., Akscyn R.M., Furuta R.K., Leggett J.J. Digital libraries // Communications of the ACM. -1995. -Vol. 38, No. 4. -P. 22-28.

56. Garcia-Molina H., Labio W., Yang J. Fast Incremental Maintenance of Approximate Histograms I I VLDB'98, Proceedings of 24th International Conference on Very Large Data Bases, August 25-29, 1998, New York, USA. -Morgan Kaufmann, 1997. -P. 500-511.

57. Gibbons P. Matias Y. Poosala V. Fast Incremental Maintenance of Approximate Histograms // VLDB'97, Proceedings of 23th International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greese. -Morgan Kaufmann, 1993. -P. 466-475.

58. Graefe G. Encapsulation of Parallelism in the Volcano Query Processing-Systems // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. -ACM Press, 1990.-P. 102-111.

59. Graefe G. Query evaluation techniques for large databases // ACM Computing Surveys. -1993. -Vol. 25, No. 2. -P. 73-169.

60. Ibaraki T. and Kameda. T. On the Optimal Nesting Order for Computing N-Relation Joins // ACM Transactions on Database Systems. -1984, -Vol. 9, No. 3. -P. 482-502.

61. Ioannidisy Y. Poosala V. Histogram-Based Solutions to Diverse Database Estimation Problems // Bulletin of the Technical Committee on Data Engineering. -1995, -Vol. 18, No. 3. -P. 10-18.

62. Kalakota R,, Whinston A. Readings in Electronic Commerce. -Addison-Wesley, 1997.

63. Kim W. On Optimizing an SQL-like Nested Query // ACM TODS, Vol. 9, No. 3, 1982.

64. Lu G. Multimedia Database Management System. -Artech House, 1999.

65. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Local Queries // Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. -ACM Press, 1986. -P. 84-95.

66. Neumann T., Moerkotte G.\ A Combined Framework for Grouping and Order Optimization. // VLDB'04, Proceedings of 30th International Conference on Very Large Data Bases, August 31-September 3, 2004, Toronto, Canada. -Morgan Kaufmann, 2004. -P. 960-971.

67. Norman M. G., Zurek T., Thanisch P. Much Ado About Shared-Nothing // ACM SIGMOD Record. -1996. -Vol. 25, No. 3. -P. 16-21.

68. Palermo F. A Data Base Search Problem // J.T. Tou (ed.). Information System: COINS IV New York, N.Y.:Plenum Press, 1974.

69. Pfister G. Sizing Up Parallel Architectures // DataBase Programming & Design OnLine (http://www.dbpd.com). May 1998. -Vol. 11, No. 5.

70. Rahm E. Parallel Query Processing in Shared Disk Database Systems // ACM SIGMOD Record. -1993. -Vol. 22, No. 4. -P. 32-37.

71. Rosenthal A., Galindo-Legaria C. Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins // Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 2325, 1990. -ACM Press, 1990. -P. 291-299.

72. Shekhar S., Srivastava J., Dutta S.: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. 457-467, VLDB 1988.

73. Sismanis Y., Roussopoulos.: The Complexity of Fully Materialized Coalesced Cubes. // VLDB'04, Proceedings of 30th International Conference on Very Large Data Bases, August 31-September 3, 2004, Toronto, Canada. -Morgan Kaufmann, 2004. -P. 540-551.

74. Stonebraker M. Retrospection on a Database System // ACM Transactions On Database Systems. -1980. -Vol. 5, No. 2. -P. 225-240.

75. Stonebraker M. The case for shared nothing // Database Engineering Bulletin. -1986. -Vol. 9, No. 1. -P. 4-9.

76. Stonebraker M., et al. The Design and Implementation of INGRES // ACM Transactions On Database Systems. -1976. -Vol. 1, No. 3. -P. 189-222.

77. Stonebraker M., Frew J., Gardeis K., Meredith J. The Sequoia 2000 Benchmark // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. -ACM Press, 1993.-P. 2-11.

78. TCP Benchmark D Standard Specification Revision 2.1 http://www.tpc.org

79. Thakkar S. S., Sweiger M. Performance of an OLTP Application on Symmetry Multiprocessor System // Proc. of the 17th Annual Int. Symposium on Computer Architecture. Seattle, WA, June 1990. IEEE Computer Society Press, 1990.-P. 228-238.

80. Valduriez P. Parallel Database Systems: Open Problems and New Issues // Distributed and Parallel Databases. -1993. -Vol. 1, No. 2. -P. 137-165.

81. Valduriez P. Parallel Database Systems: the Case for Shared-something // Proc. of the 9th Int. Conf. on Data Engineering, April 19-23, 1993, Vi-enna, Austria. IEEE Computer Society, 1993. - P. 460-465.

82. Yang H.Z., Larson P.A. Query Transformation for PSJ-queries // VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England. -Morgan Kaufmann, 1987. -P. 245-254.

83. Zipf G., Human Behavior and the Principle of Least Effort: an Introduction to Human Ecology. -Cambridge, Mass.: Addison-Wesley, 1949. -573 P