Управление производительностью параллельной вычислительной системы при обработке запросов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Мьо Тант

• Мьо Тант
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Мьо Тант

Содержание.

Введение.

Глава 1. Архитектура параллельных систем баз данных и обработка оптимизации запросов

1.1. Оптимальная обработка запросов (003).1.

1.1.1. Оптимизация запросов к базам данных.

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

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

1.1.4. Обработка запроса в параллельной СУБД.

1.2. Математические методы для оценки методов 003.

1.2.1. Построение гистограмм для 003.

1.2.2. Глобальные оптимизации в реляционных системах управления БД.

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

1.3.1. Анализа моделей доступа к базам данных распределенных систем обработки данных.

1.3.2. Алгоритмы выполнения запросов к ООСУБД.

1.3.3. Анализ схемы базы данных.

1.3.4. Использование памяти.

1.3.5. Постановка задача.

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

Глава 2. Метод оптимизации однопроцессорной обработки запросов.

2.1. Введение.!.

2.2. Время выполнения запроса для упорядоченных столбцов таблицы.

2.3. Время выполнения запроса для неупорядоченных столбцов таблицы.

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

2.5. Эффективность метода оптимизации.

2.6. Влияние параметров запроса на время выполнения запроса.

2.7. Общий случай задания запроса.

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

3. Оптимизация обработки запросов в многопроцессорной базе данных.

3.1. Введение.

3.2. Влияние числа процессоров на время выполнения запроса.:.

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

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

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

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

3.7. Квазиоптимальный план алгоритма распределения ЭЗ на процессоры.

3.8. Оптимальный алгоритм распределения ЭЗ на процессоры.

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

Глава 4. Модуль формирования и оценки плана времени выполнения запроса.

4.1. Текст программы.

4.2. Описание программы.

4.3. Тестирование работы программы.

4.4. Анализ оптимизации плана выполнения запросов. Моделирование на СРБЗ/Н

4.4.1. Однопроцессорный вариант.

4.4.2. Многопроцессорный вариант.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.ПО

Введение диссертации (часть автореферата) на тему «Управление производительностью параллельной вычислительной системы при обработке запросов»

Типичная БД - это организованный набор связанной информации, которая хранится в виде «записей», которые разделены на «поля» (области информации). Например, БД работников предприятия может иметь запись о каждом работнике, и каждая запись имеет поля, где указаны специфические данные в отношении работника - фамилия, домашний адрес, размер зарплаты и т.д.

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

Одновременно с этим пользователи ожидают от применения СУБД высокой производительности и надежности.

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

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

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

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

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

В простейшем случае запрос к базе данных можно рассматривать как обращение к таблице, содержащий, например, множество записей (строк), характеризующихся одинаковым множеством свойств (столбцов), с целью получения множества записей, удовлетворяющих заданному условию запроса. Будем называть часть запроса, относимую к ¡- му свойству записи ('1 - му столбцу), 1 - ым элементарным запросом (ЭЗО.

При выполнении запроса для каждой строки необходимо выполнить проверку условия, связанного с ЭЗ1, требуемое для этого время обозначим через -л и вероятность успеха выполнения условия через рк Вариация значений времени т1 зависит от формулировки условия Э35 (точечное, интервальное или более сложное условие), а так же от технических и/или программных особенностей реализации (кэширование, диски и др.). Вариация значений вероятности выполнения условия р1 определяется содержимым базы данных.

Основным критерием при определении Плана реализации запроса является время выполнения запроса, которое, вообще говоря, зависит от порядка выполнения элементарных запросов, его составляющих, п указанных параметров элементарных запросов Э31 - времени проверки в строке т1 и вероятности успеха в строке р1. Время выполнения элементарного запроса зависит от метода доступа к столбцу таблицы. Существуют два базовых метода, когда данные в столбцах не упорядочены и когда данные в столбцах упорядочены. Известным методом увеличения производительности является использование многопроцессорных бортовых ВС.

Цель диссертационной работы

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

Методы исследования

Аналитическое и имитационное моделирование. Эксперименты с СУБД.

На защиту выносятся следующие положения:

Метод обеспечения оптимизации многопроцессорной обработки запросов. Утверждение об условиях определения минимального время обработки конъюнктивного запроса для упорядоченных таблиц данных.

Квазиоптимальный план распределения элементарных запросов на процессоры. Оптимальный план распределения элементарных запросов на процессоры.

Научная новизна

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

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

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

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

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

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

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

Разработан модуль формирования и оценки времени выполнения плана выполнения запроса.

Реализация результатов работы

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

Вычислительные машины и системы» Московского авиационного института (государственного технического университета).

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

Основные положения и результаты диссертационного исследования докладывались автором и обсуждались: на всероссийской конференции молодых ученых и студентов «Информационные технологии в авиационной и космической технике», Москва, 2010г. и трех международных конференциях «Авиация и космонавтика», Москва, 8-10 ноября 2011 года, 17-20 апреля и 13-15 ноября 2012 года.

Публикации

Основные материалы диссертационной работы опубликованы в 3 печатных работах.

Структура и объем диссертации

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

• Предложен и обоснован метод оптимизации обработки запросов для упорядоченных таблиц данных.

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

• Проведено сравнение минимального времени обработки конъюнктивного запроса для упорядоченных и неупорядоченных таблиц данных.

• Разработан метод обеспечения оптимизации многопроцессорной обработки запросов.

• Предложен оптимальный алгоритм распределения элементарных запросов на процессоры.

Список литературы диссертационного исследования кандидат технических наук Мьо Тант, 2012 год

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

2. Байкова И., Кулагин М. Современные дисковые системы RAID //Открытые системы. 1995.

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

4. Баженова И. Ю. Основы проектирования приложений баз данных, ИНТУИТ.ру, 2006.

5. Безкоровайный М.М., Костогрызов А.И., Львов В.М. Инструментально-моделирую-щий комплекс для оценки качества функционирования информационных систем "КОК". М.:СИНТЕГ, 2000.

6. Брехов О.М., Мьо Тант. Оптимизация обработки запросов в многопроцессорной базе данных. // Журнал «Вестник Московского Авиационного Института» 2012г. №(5), с. 138-265.

7. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. -М.: Мир, 1985.

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

9. Герберт Шилдт. Полный справочник по С. Изд-во Вильяме, 2009.

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

11. П.Григорьев Ю.А. Разработка научных основ проектирования архитектуры распределенных систем обработки данных: Дис. д-ра техн. наук. МГТУ им. Н.Э. Баумана, 17.10.96 г.

12. H.A. Гребенников, В.М. Постников //Организация баз данных, 2002 г. (Московский государственный технический университет им. Н.Э. Баумана).

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

14. Корнеев В. Архитектуры с распределенной разделяемой памятью // Открытые системы.

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

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

17. Кузнецов С.Д. «Базы данных: языки и модели», Москва, Бином, 2008, 720 с.

18. Кузнецов С.Д. Основы баз данных. М.: Изд-во "Интернет-университет информационных технологий - ИНТУИТ.ру", 2005.

19. Кузнецов С.Д. Логическая оптимизация запросов в реляционных СУБД // Программирование.

20. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД // Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М: ВИНИТИ, 1989.

21. Кузнецов С.Д. Операционные системы для управления базами данных // СУБД.

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

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

24. Лисянский К., Слободяников Д. СУБД Teradata для ОС UNIX // СУБД. 1997.

25. Постников В.М., Гребенников H.A. Технология обработки запросов пользователей в СУБД ORACLE // Вестник МГТУ им. Н.Э. Баумана. Сер. "Приборостроение". 2001. №2. С. 106-126.

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

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

28. Сиротюк В.О. Модели и методы синтеза оптимальных логических структур и базы метаданных репозитария распределенных баз данных в АСУ // Автоматика и телемеханика (М.). 1999. № 1.

29. Хаманн Ф. Отказоустойчивая операционная система TandemNonStop Kernel // Открытые системы.

30. Шмидт В. Системы 1BMSP2 // Открытые системы.

31. Шнитман В. Отказоустойчивые серверы ServerNet // Открытые системы.

32. An Environment for the Design and Performance Evaluation of Portable Parallel Software: Final EDPEPPS Simulator: Report / Center for Parallel Computing University of Westmin-ster. EDPEPPS/41. London, July 1997.

33. Amza C., et al. ThreadMarks: Shared Memory Computing on Networks of Workstations // IEEE Computer. -1996. -Vol. 29, No. 2.

34. Amol Deshpande, Zacchary Ives, Vijayshankar Raman Adaptive Query Processing // Foundations and Trends in Databases. -2007. -Vol.1,No. 1(2007), p. 1-140.

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

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

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

38. Bell C.G., Gray J. What's next in high-performance computing? // Communications of the ACM. -2002. -Vol. 45, No. 2.

39. Bellman R.E. Dynamic Programming, Princeton University Press, Princeton, N; Jersey, 1975.

40. Bergsten B., Couprie M., Valdurez P. Overview of Parallel Architectures for Databases // The Computer Journal. -1993. -Vol. 36, No. 8.

41. Boral H„ Alexander W., Clay L., Copeland G„ Sanforth S., Franklin M., Hart B„ Smith M., Valduriez P. Prototyping Bubba: a Highly Parallel Database System // IEEE Trans, on Knowledge and Data Engineering. -1990. Vol. 2, No. 1.

42. Boral H., De Witt D.J. Applying Data Flow Techniques to Data Base Machines // IEEE Computer. -1982. -Vol. 15, No. 8.

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

44. Bultzingsloewen G.v., et al. KARDAMOM A Dataflow Database Machine For RealTime Applications // SIGMOD Record.-1988. -Vol. 17, No. 1.

45. Codd, Edgar Frank: "Is Your DBMS Really Relational?", Computerworld, 14. October 1985.

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

47. Chen M.-S., Yu P.S., Wu K.-L. Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries // Proceedings of the Eighth International Conference on Data Engineering, February 3-7, 1992, Tempe, Arizona. -IEEE Computer Society, 1992.

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

49. Christodoulakis S. Estimating record selectivities // Information Systems. -1983. -Vol. 8, No. 2.

50. Clay D. Informix Parallel Data Query (PDQ) // Proceedings of the 2nd International Conference on Parallel and Distributed Information Systems (PDIS 1993), Issues,

51. Architectures, and Algorithms, San Diego, CA, USA, January 20-23, 1993. -IEEE Computer Society, 1993.

52. Copeland G.P., Keller T. A Comparison Of High-Availability Media Recovery Techniques // roceedings of the 1989 ACM S1GMOD International Conference on Management of Data, Portland, Oregon, May 3 1 June 2, 1989. -ACM Press, 1989.

53. Dasgupta S. A Hierarchical Taxonomic System for Computer Architectures // IEEE Computer.-1990.-Vol. 23, No. 3.

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

55. DeWitt D.J., Gerber R.H. Multiprocessor Hash-Based Join Algorithms // VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. -Morgan Kaufmann, 1985.

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

57. Effelsberg W., Haerder T. Principles of Database Buffer Management // ACM Trans, on Database Systems. 1984. -Vol. 9, No. 4.

58. E.F. Codd: "Relational Completeness of Data Base Sublanguages" (presented at Courant Computer Science Symposia Series 6, "Data Base Systems", New York City, N.Y., May 24th-25th, 1971).

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

60. Flynn M.J. Computer Organization and Architecture // Operating Systems, An Advanced Course. -Springer, 1978 (Lecture Notes in Computer Science; Vol. 60).

61. Flynn M.J. Very High Speed Computing Systems // Proc. IEEE. -1966. -Vol. 54. -P. 1901-1909.

62. Flynn M.J., Rudd K.W. Parallel architectures // ACM Computing Surveys. 1996. -Vol. 28, No. 1.

63. Gardarin G., Sha F., Tang Z.-H. Calibrating the query optimizer cost model of IRO-DB an objectoriented federated database system // Proceedings of the 22nd International Conference on VLDB. Bombay, 1996. P.378-389.

64. Gibson G.A., Vitter 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.

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

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

67. Graefe G. Volcano An Extensible and Parallel Query Evaluation System // IEEE Transactions on Knowledge and Data Engineering. -1994. -Vol. 6, No. h

68. Graefe G. Query evaluation techniques for large databases // ACM Computing Survey N.Y., 1993. Vol. 25. No. 2. P.73-170.

69. Graefe G. Query Evaluation Techniques for Large Databases // ACM Computing Surveys. -1993. -Vol. 25, No 2. -P. 73-169.

70. Graefe Goetz, Dewitt David J. The EXODUS Optimizer Generator. In Proceedings 1987 ACM SIG-MOD International Conference on Management of Data, San Francisco, 1987. P.387-394.

71. Graefe Goetz, McKenna William. The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proceeding of the 12th International Conf. on Data Engineering, 1993. P.209-218.

72. Graefe G. The Cascades Framework for Query Optimization, Bulletin of the IEEE Technical Committee on Data Engineering, 18(3), September 1995, P. 19-29.

73. Gray J. Notes on Data Base Operating Systems // Operating Systems, An advanced Course.-Springer, 1978 (Lecture Notes in Computer Science; Vol. 60).

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

75. Hasan W. Optimization of SQL Queries for Parallel Machines. (Lecture notes in computer science, Vol. 1182). -Berlin, New York: Springer, 1996.

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

77. Hsiao H. I., DeWitt D. J. A Performance Study of Three High Availability Data Replication Strategies// Distributed and Parallel Databases. -1993. -Vol. 1, No. 1.

78. Hwang H-Y., Yao-Tin Y. An Analytical Method for Estimating and Interpreting QueryTime // Proceedings of the 13th VLDB Conference. Brighton, 1987.

79. Ibaraki T., Kameda T. On the optimal nesting order for computing N-relational joins. //ACM Transactions on Database Systems. 1984. 9(3). P.482-502.

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

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

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

83. Kotsis G. Interconnection Topologies for Parallel Processing Systems // PARS Mitteilungen. -1993.

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

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

86. Lohman G.M., et al Query Processing in R* // Query Processing in Database Systems. -Springer, 1985.

87. Lorie R., et al. Adding Intra-transaction Parallelism to an Existing DBMS: Early Experience// Data Engineering Bulletin. -1989. Vol. 12, No. 1.

88. Lorie R.A., Young H.C. A Low Communication Sort Algorithm for a Parallel Database Machine // Proceedings of the Fifteenth International Conference onVery Large Data Bases, August 22-25, 1989, Amsterdam, The Netherlands. -Morgan Kaufmann, 1989.

89. Lu H., Shan M.-C., Tan K.-L. Optimization of Multi-Way Join Queries for Parallel Execution // 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. -Morgan Kaufmann, 1991.

90. Matthias Jarke, Jürgen Koch. Query Optimization in Database Systems. Computing Surveys, Vol. 16, No. 2, June 1984.

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

92. Method and system for query processing,United States Patent 6757670.

93. Michie D. 'Memo' Functions and Machine Learning, Nature, April 1968. No. 218, P. 1922.

94. Montgomery A.Y.,D'Souza D.J., Lee S.B. The Cost of Relational Algebraic Operations on Skewed Data: Estimates and Experiments // Information Processing 83,

95. Proceedings of the IFIP 9th World Computer Congress, Paris, France, September 19-23, 1983.-North-Holland: IF1P, 1983.

96. Nick J. M„ Moore B. B„ Chung J.-Y., Bowen N. S. S/390 Cluster Technology: Parallel Sysplex // IBM Systems Journal. -1997. -Vol. 36, No. 2.

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

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

99. Ozsu M.T., Valduriez P. Principles of Distributed Database System. Englewood Cliffs, NJ: Prentice-Hall, 1991.

100. Patterson D.A., Gibson G.A., Katz R.H. A Case for Redundant Arrays of Inexpensive Disks (RAID) // Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988. 1988.

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

102. Pirahesh Hamid, Hellerstein Joseph M., Hasan Waqar. Extensible/Rule Based Query Rewrite Optimization in Starburst. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, pages 39-48, San Diego, California, June 1992.

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

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

105. Rahm E. A Framework for Workload Allocation in Distributed Transaction Processing Systems//Journal of Systems and Software. -1992. -Vol. 18.

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

107. Richardson J.P., Lu H., Mikkilineni K. Design and Evaluation of Parallel Pipelined Join Algorithms // Proceedings of the ACM S1GMD 1987 Annual Conference, San Francisco, California, May 27-29, 1987. -ACM Press, 1987.

108. Seiinger P.G., Astrahan M.M., Chamberlin D.D., Lorie R.A., Price T.G. Access Path Selection in a Relational Database Management System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., May 30 June 1, 1979. New York, 1979.- C. 23-34.

109. Skillicorn D.B. A Taxonomy for Computer Architectures // IEEE Computer. -1988.-Vol. 21, No. 1.

110. Sokolinsky L.B. Design and Evaluation of Database Multiprocessor Architecture with High Data Availability// 12th International DEXA Workshop, Munich, Germany, 37 September, 2001, Proceedings. -IEEE Computer Society, 2001.

111. SQLBase. Advanced Topic Guide. 20-2119-9901 SQL designs. Gupta Inc. 2006

112. Sterling T., et all. BEOWULF: A Parallel Workstation for Scientific Computation // Proceedings of the 1995 International Conference on Parallel Processing, August 1418, 1995, Urbana-Champain, Illinois, USA. Volume I: Architecture. -CRC Press, 1995.

113. Stonebraker M., Katz R.H., Patterson D.A., Ousterhout J.K. The Design ofXPRS // Fourteenth International Conference on Very Large Data Bases, August 29 September 1, 1988, Los Angeles, California, USA, Proceedings. -Morgan Kaufmann, 1988.

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

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

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

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

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

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

120. Van Vleck T. H. , Clingen C. T. The Multics System Programming Process // Proceedings of the 3rd International Conference on Software Engineering, May 1012,1978, Atlanta, Georgia, USA. -IEEE Computer Society, 1978.

121. W. Hasan, D. Florescu, P. Valduriez Open Issues in Parallel Query Optimization // ACM SIGMOD Record. -1996. -Vol. 25, No. 3.

122. Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques. IEEE Computer society, 1998.

123. Wong, Eugene, Youssefi, K., Decomposition A Strategy for Query Processing. ACM Transactions on Database Systems, 3 (September) 1976.

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

125. Yannis E. Ioannidis: Query Optimization.ACM Comput. Surv. 28(1): 121-123 (1996)

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

127. Amol Deshpande, Zacchary Ives, Vijayshankar Raman Adaptive Query Processing // Foundations and Trends in Databases. -2007. -Vol.1, No. 1(2007), p. 1-140.