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

ВВЕДЕНИЕ.

Глава 1. АРХИТЕКТУРА СИСТЕМ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ТРАНЗАКЦИЙ.

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

1.2. Сравнительный анализ архитектур параллельных систем баз данных.

1.3. Архитектура системы Омега.

1.3.1. Аппаратная архитектура системы Омега.

1.3.2. Программная структура СУБД Омега.

1.4. Организация обработки транзакций в параллельных СУБД.

1.4.1. Структура СУБД.

1.4.2. Формы параллельной обработки транзакций.

1.4.3. Архитектура параллельного исполнителя запросов.

1.5. Заключительные замечания к главе 1.

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

2.1. Анализ различных подходов к распараллеливанию запросов.

2.1.1. Модели синхронизации операций в дереве запроса.

2.1.2. Модели параллелизации запросов в многопроцессорных системах.

2.1.3. Потоковая модель распараллеливания запросов.

2.2. Синхронизация выполнения операций в системе Омега.

2.3. Параллелизация запросов в системе Омега.

2.4. Заключительные замечания к главе 2.

Глава 3. ПОТОКОВАЯ МОДЕЛЬ.

3.1. Концепция потоков.

3.2. Операторный фрейм.

3.3. Структура оператора Q.

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

3.5. Заключительные замечания к главе 3.

Глава 4. ПРИНЦИПЫ РЕАЛИЗАЦИИ ИСПОЛНИТЕЛЯ ЗАПРОСОВ СИСТЕМЫ ОМЕГА.

4.1. Структура исполнителя запросов.

4.1.1. Класс Stock.

4.1.2. Класс Stream.

4.1.3. Класс Tree.

4.1.4. Модуль интерпретатора операций физической алгебры.

4.1.5. Модуль исполнителя запросов.

4.1.6. Пример использования исполнителя запросов.

4.2. Реализация реляционных операций.

4.3. Заключительные замечания к главе 4.

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

Фактически единственным эффективным решением проблемы хранения и обработки сверхбольших баз данных является использование параллельных систем баз данных [53], обеспечивающих параллельную обработку запросов на многопроцессорных вычислительных системах. Интенсивные научные исследования в области параллельных СУБД были начаты в 80-х годах. В течение последних двух десятилетий параллельные системы баз данных проделали путь от научно-исследовательских прототипов к полнофункциональным коммерческим продуктам, поставляемым на рынок высокопроизводительных информационных систем. В качестве примеров успешных коммерческих проектов создания параллельных систем баз данных можно привести DB2 Parallel Edition [31], NonStop SQL [26, 42] и NCR Teradata [14]. Подобные системы объединяют до тысячи процессоров и магнитных дисков и способны обрабатывать базы данных в десятки терабайт. Тем не менее, в области параллельных систем баз данных до сих пор остается ряд направлений, требующих дополнительных научных исследований [109]. Одной из таких проблем является эффективная организация параллельной обработки потока транзакций. Разработки в этом направлении ведутся по пути совершенствования методов организации параллельного выполнения запросов применительно к новым гибридным архитектурам.

В настоящее время одной из перспективных отечественных разработок в сфере многопроцессорных вычислительных систем является многопроцессорный вычислительный комплекс МВС-100/1000 [13]. МВС-100/1 ООО представляет собой семейство масштабируемых многопроцессорных вычислительных систем с массовым параллелизмом, являющихся совместной разработкой институтов РАН и промышленности. Вычислительные комплексы МВС-100/1000 используются в ряде академических институтов и университетов России для решения широкого спектра фундаментальных научных и прикладных задач в областях управления динамическими системами и дифференциальных игр, механики сплошной среды, математического программирования, обработки изображений и распознавания образов и др. Однако в настоящее время отсутствует специализированное системное программное обеспечение, позволяющее хранить и обрабатывать на МВС-100/1000 сверхбольшие базы данных. В Челябинском государственном университете при поддержке Российского фонда фундаментальных исследований (гранты 97-07-90148, 00-07-90077) ведется работа по созданию прототипа параллельной СУБД Омега [21, 9498] для многопроцессорной вычислительной системы МВС-100/1000. В соответствии с этим актуальной является задача разработки новых моделей параллельного выполнения запросов, ориентированных на архитектуру МВС.

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

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

2) разработка новых моделей и методов параллельного выполнения запросов, ориентированных на иерархические системы с распределенной памятью;

3) разработка на базе предложенных моделей и методов исполнителя запросов СУБД Омега;

4) проведение вычислительных экспериментов по исследованию эффективности разработанных моделей и методов.

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

В первой главе «Архитектура систем параллельной обработки транзакций» формулируются требования к параллельным системам баз данных, приводится классификация архитектур параллельных систем баз данных и производится их сравнительный анализ. Затем описывается трехуровневая иерархическая CD2 архитектура параллельной системы баз данных Омега. Приводится описание аппаратной и программной архитектура системы Омега. Далее дается обзор способов организации параллельной обработки транзакций в параллельных системах баз данных. Затем формулируются требования, которым должен удовлетворять исполнитель запросов, описываются место и роль исполнителя запросов в программной структуре СУБД.

Вторая глава «Методы организации параллельной обработки запросов» посвящена вопросам разработки моделей параллелизации и синхронизации операций в дереве запроса, ориентированных на иерархические архитектуры с распределенной памятью. В начале главы описываются существующие модели синхронизации и параллелизации, анализируются их достоинства и недостатки, совместимость этих моделей с различными типами архитектур параллельных баз данных. Далее вводится новая модель параллельного выполнения запросов, названная потоковой. Потоковая модель является устойчивой к перекосам выполнения и позволяет достичь на Омега-кластерах производительности, сравнимой с производительностью кластеров с разделяемой памятью. Затем описывается предложенная для системы Омега оригинальная модель синхронизации операций, основанная на понятии Т-фактора. Оригинальная модель парал-лелизации запросов, используемая в потоковой модели, базируется на концепциях операторного фрейма, являющегося развитием скобочного шаблона, и оператора Q, инкапсулирующего параллелизм выполнения запросов в потоковой модели.

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

В четвертой главе «Принципы реализации исполнителя запросов системы Омега» описываются подходы, использованные при реализации исполнителя запросов системы Омега. Рассматривается модульная структура исполнителя запросов СУБД Омега, приводятся интерфейсы входящих в него модулей и классов, описывается физическая алгебра, реализуемая исполнителем запросов и методы реализации реляционных операций. 7

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

В приложение вынесены алгоритмы реализации реляционных операций.

Основные результаты диссертации полностью опубликованы в работах [15, 16, 17, 75,76].

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

1) на IV Международной Балтийской конференции IEEE по базам данных и информационным системам - BalticDB&IS'2000 (Вильнюс, Литва, 1-5 мая 2000 г.);

2) на 3-й Международной конференции по программированию и информационным технологиям CSIT'2001 (Уфа, 21-26 сентября 2001 г.);

3) на Международной конференции "Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде" -DSO'2000 (Екатеринбург, 30 мая - 2 июня 2000 г.);

4) на Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения" (Черноголовка, 30 октября - 2 ноября 2000 г.).

Заключение

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

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты 97-07-90148, 00-07-90077, 01-07-06039, 02-07-06028).

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

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

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

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

4. На основе предложенных моделей, концепций и методов спроектирован и реализован исполнитель запросов для многопроцессорного вычислительного комплекса МВС.

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

1. Барон Г.Г. Параллельные архитектуры серверов баз данных // СУБД. -1995. -№2.-С. 32-44.

2. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем. -М: Изд-во МГУ, 1994. -103 с.

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

4. Голъдштейн M.JI. Мультипроцессорная вычислительная система на базе транспьютерной идеологии // Алгоритмы и программные средства параллельных вычислений: Сб. науч. тр. / ИММ УрО РАН. -Екатеринбург: УрО РАН, 1995. -С. 61-68.

5. Дейт К.Дж. Введение в системы баз данных. -М.:Издательский дом «Вильяме», 2001. -1072 с.

6. Дубова Н. Суперкомпьютеры nCube // Открытые системы. -1995. -№2. -С. 42-47.

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

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

9. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. 2-е издание. -М.: Нолидж, 2001. -496 с.

10. Кузнецов С.Д. Стандарты языка реляционных баз данных SQL: краткий обзор// СУБД. -1996. -№2. -С. 78-99.

11. Кузнецов С.Д. Операционные системы для управления базами данных // СУБД. -1996. -№3. -С. 95-102.

12. Кузнецов С.Д. СУБД и файловые системы. -М.: Майор, 2001. -176 с.

13. Левин В. К. Отечественные суперкомпьютеры семейства MB. http://parallel.ru/mys/levm.html

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

15. Лымарь Т.Ю., Соколинский Л.Б. Организация параллельного исполнителя запросов на базе многопроцессорного вычислительного комплекса МВС-100/1000 // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -2002. -№1(6). -С. 177-188.

16. Соколинский Л.Б. Исполнитель физических запросов СУБД Омега. Технич. отчет OMEGA04. ЧелГУ, 1999. -26 с.http: //www .csu.ru/~sok/papers/omegarep/engine. html)

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

18. Соколинский Л.Б. Параллельные машины баз данных // Природа. Естественно-научный журнал Российской академии наук. -2001. -№8. -С. 10-17.

19. Соколинский Л.Б. Система управления файлами СУБД Омега. Технич. отчет OMEGA03. -ЧелГУ, 1998. 25 с. (http://www.csu.ru/~sok/papers/omegarep/filesys.html)

20. Соколинский Л.Б. Структура системного окружения СУБД Омега. Технич. отчет OMEGA02. -ЧелГУ, 1998. (http://www.csu.ru/~sok/papers/omegarep/structuTe.html)

21. Соколинский Л.Б., Цымблер М.Л. Принципы реализации системы управления файлами в параллельной СУБД Омега для МВС-100 // Вестник Челябинского университета. Сер. 3. Математика, механика, информатика. -1999. -№2(5). -С. 176-199.

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

23. Apers P.M.G., van den Berg С A., FlokstraJ., Grefen P. W.P. J., Kersten M.L., Wilschut A.N. Prisma/DB: a Parallel Main-Memory Realational DBMS 11 IEEE Transactions on Knowledge and Data Engineering. -1992. -Vol. 4, No. 6. -P. 541-554.

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

25. Ваги С. K., et al. DB2 Parallel Edition // IBM System Journal. -1995. -Vol. 34, No. 2. -P. 292-322.

26. Bergsten В., CouprieM., Valdurez P. Overview of Parallel Architectures for Databases // The Computer Journal. -1993. -Vol. 36, No. 8. -P. 734-740.

27. В oral H., Alexander W., Clay L., Copeland G., Sanforth S., Franklin M., Hart В., Smith M., Valduriez P. Prototyping Bubba: a Highly Parallel Database System // IEEE Trans, on Knowledge and Data Engineering. -1990. -Vol. 2, No. l.-P. 4-24.

28. Boral H., DeWitt D.J. Applying Data Flow Techniques to Data Base Machines // IEEE Computer. -1982. -Vol. 15, No. 8. -P. 57-63.

29. 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.

30. Chen M.-S., YuP.S., WuK.-L. Optimization of Parallel Execution for Multi-Join Queries 11 IEEE Transactions on Knowledge and Data Engineering. -1996. -Vol. 8, No. 3. -P. 416-428.

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

32. Christodoulakis S. Estimating record selectivities // Information Systems. -1983. -Vol. 8, No. 2. -P. 105-115.

33. 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.

34. 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.

35. Darwen H., Date C.J. The Third Manifesto // ACM SIGMOD Record. -1995. -Vol. 24, No. 1. -P. 39-49.

36. Davison W. Parallel Index Building in Informix OnLine 6.0 // Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. -ACM Press, 1992. -P. 103.

37. DeWitt D.J., et al. The Gamma database machine project // IEEE Transactins on Knowledge and Data Engineering. -1990. -Vol. 2, No. 1. -P. 44-62.

38. DeWitt D.J., Gray J. Parallel Database Systems: The Future of High-Performance Database Systems // Communications of the ACM. -1992. -Vol. 35, No. 6. -P. 85-98.

39. Englert S., Glasstone R., Hasan W. Parallelism and its Price: A Case Study of NonStop SQL/MP // ACM SIGMOD Record. -1995. -Vol. 24, No. 4. -P. 61-71.

40. Flynn M.J., Rudd K. W. Parallel architectures 11 ACM Computing Surveys. 1996. -Vol. 28, No. l.-P. 67-70.

41. Gaponenko /., et al. The BaBar Database: Challenges, Trends and Projections // Proc. of Int. Conf. on Computing in High Energy and Nuclear Physics (CHEP'01), September 3 7,2001, Beijing, China. -Science Press, 2001.

42. Garcia-Molina H., Ullman J.D., Widom J. Database System Implementation. -Prentice Hall, 2000. -653 p.

43. Gibson G.A., Fitter J.S., Wilkes J. Strategic directions in storage I/O issues in large-scale computing // ACM Computing Surveys. -1996. -Vol. 28, No. 4. -P. 779-793.

44. Graefe G. Encapsulation of Parallelism in the Volcano Query Processing Systems I I 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.

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

46. Graefe G. Volcano An Extensible and Parallel Query Evaluation System // IEEE Transactions on Knowledge and Data Engineering. -1994. -Vol. 6, No. l.-P. 120-135.

47. Gray J. Notes on Data Base Operating Systems I I Operating Systems, An Advanced Course.-Springer, 1978 (Lecture Notes in Computer Science; Vol. 60).-P. 393-481.

48. Gray J., Graefe G. The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb // SIGMOD Record. -1997. -Vol. 26, No. 4. -P. 63-68.

49. Hong W., Stonebraker M. Optimization of Parallel Query Execution Plans in XPRS // Distributed and Parallel Databases. -1993. -Vol. 1, No. 1. -P. 9-32.

50. Hsiao H. /., DeWittD. J. A Performance Study of Three High Availability Data Replication Strategies // Distributed and Parallel Databases. -1993. -Vol. 1, No. 1. -P. 53-80.

51. Jarke M., Koch J. Query optimization in database systems // ACM Computing Surveys. -1984. -Vol. 16, No. 2. -P. 111-152.

52. Kim W. Highly Available Systems for Database Applications // ACM Computing Surveys. -1984. -Vol. 16, No. 1. -P. 71-98.

53. King G. M., Dias D. M., Yu P. S. Cluster Architectures and S/390 Parallel Sysplex Scalability// IBM Systems Journal. -1997. -Vol. 36, No. 2. -P. 221-241.

54. Kronenberg N.P., Levy H.M., Strecker W.D. VAXclusters: A Closely-Coupled Distributed System // ACM Transactions on Computer Systems. -1986. -Vol. 4, No. 2. -P. 130-146.

55. Lakshmi M.S., Yu P.S. Effectiveness of Parallel Joins // IEEE Transactions on Knowledge and Data Engineering. -1990. -Vol. 2, No. 4. -P. 410-424.

56. Lohman G.M., et al Query Processing in R* // Query Processing in Database Systems. -Springer, 1985. -P. 31 -47.

57. LorieR., et al. Adding Intra-transaction Parallelism to an Existing DBMS: Early Experience // Data Engineering Bulletin. -1989. -Vol. 12, No. 1. -P. 2-8.

58. Menon J. A Study of Sort Algorithms for Multiprocessor Database Machines 11 VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. -Morgan Kaufmann, 1986. -P. 197-206.

59. Nick J. M., Moore В. В., Chung J.-Y., Bowen N. S. S/390 Cluster Technology: Parallel Sysplex // IBM Systems Journal. -1997. -Vol. 36, No. 2. -P. 172-201.

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

61. Oldehoeft R. R. Multithreaded Computer Systems // Proceedings Supercomputing'92, November 16-20, 1992, Minneapolis, MN, USA. -IEEE Computer Society, 1992. -P. 772-775.

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

63. Pramanik S., Tout W.R. The NUMA with Clusters of Processors for Parallel Join I I IEEE Transactions on Knowledge and Data Engineering. -1997. -Vol. 9, No. 4. -P. 653-666.

64. Query Processing in Parallel Relational Database Systems / edited by. Lu H., Ooi B.-C., Tan K.-L. -IEEE Computer Society Press, 1994. -382 p.

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

66. Sokolinsky L.B. Design and Evaluation of Database Multiprocessor Architecture with High Data Availability // 12th International DEXA Workshop, Munich, Germany, 3-7 September, 2001, Proceedings. -IEEE Computer Society, 2001.-P. 115-120.

67. Sokolinsky L.B. Interprocessor Communication Support in the Omega Parallel Database System// Proc. of the 1st Int. Workshop on Computer Science and Information Technologies(CSIT'99), Moscow, January 18-22, 1999.

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

69. Stonebraker M. Operating System Support for Database Management // Communications of the ACM. -1981. -Vol. 24, No. 7. -P. 412-418.

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

71. Stonebraker M. Inclusion of New Types in Relational Data Base Systems // ICDE 1986: Proceedings of the Second International Conference on Data Engineering, February 5-7, 1986, Los Angeles, California, USA. -IEEE Computer Society, 1986. -P. 262-269.

72. Stonebraker M., Katz R.H., Patterson D.A., Ousterhout J.K. The Design of XPRS 11 Fourteenth International Conference on Very Large Data Bases, August 29 September 1, 1988, Los Angeles, California, USA, Proceedings. -Morgan Kaufmann, 1988. -P. 318-330.

73. Stonebraker M., et al. Third-Generation Database System Manifesto // ACM SIGMOD Record. -1990. -Vol. 19, No. 3. -P. 31-44.

74. Strickland J.P., Uhrowczik P.P., Watts V.L. IMS/VS: An Evolving System // IBM Systems Journal. -1982. -Vol. 21, No. 3. -P. 490-510.

75. Szalay A.S., et al. The SDSS SkyServer Public Access to the Sloan Digital Sky Server Data I I Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6, 2002. -ACM Press, 2002.

76. The Benchmark Handbook for Database and Transaction Processing Systems, Second Edition. -Morgan-Kaufmann, 1993. -592 p.

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

78. Valduriez P. Parallel Database Systems: the case for shared-something // Proceedings of the 9th International Conference on Data Engineering, April 19-23, 1993, Vienna, Austria. -IEEE Computer Society, 1993. -P. 460-465.

79. Valduriez P., Gardarin G. Join and Semijoin Algorithms for a Multiprocessor Database Machine // ACM Transactions on Database Systems. -1984. -Vol. 9, No. 1. -P. 133-161.

80. Van Vleck Т. H., Clingen С. T. The Multics System Programming Process // Proceedings of the 3rd International Conference on Software Engineering, May 10-12, 1978, Atlanta, Georgia, USA. -IEEE Computer Society, 1978. -P. 278-280.

81. Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques. -IEEE Computer society, 1998. -P. 203-218.

82. Wilschut A.N., Flokstra J., Apers P.M.G. Parallel Evaluation of Multi-Join Queries // Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995. -ACM Press, 1995.-P. 115-126.

83. Xu Y., Dandamudi S.P. Performance Evaluation of a Two-Level Hierarchical Parallel Database System 11 Proceedings of the Int. Conf. Computers and Their Applications, Tempe, Arizona, 1997. P. 242-247.

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