Введение в системы БД (542480), страница 178
Текст из файла (страница 178)
1995 АСМ 510МОР 1пк Сопб оп Мапа8ешепг об Рага. — Зап )озе, Са)!1:, Мау, 1995. Это не научная статья, а расширенная аннотация для презентации учебного пособия. По сути, основная идея параллельных систем заключается в разбиении большой задачи на несколько малых задач, которые могут решаться одновременно, что способствует общему повышению производительности.
В частности, реляционные системы баз данных прекрасно подходят для распараллеливания обработки по самой природе реляционной модели. Дело а том, что концептуально легко выполняются следующие действия: разбиение отношения несколькими разными способами на несколько подчиненных отношений; разбиение реляционного выражения на несколько подчиненных выражений также несколькими разными способами. В духе заголовка этой статьи следует отметить некоторые важные концепции параллельных систем баз данных. Прежде всего, сама по себе архитектура используемого аппаратного обеспечения должна предполагать возможность параллельной работы.
Ниже перечислены три основных типа такой архитектуры, каждая из которых включает несколько процессоров, несколько жестких дисков, а также сеть для обмена данными. ° С разделением оперативной памяти. Сеть позволяет всем процессорам обращаться к общей оперативной памяти. ° С разделением дисковой памяти. Каждый процессор обладает собственной оперативной памятью, но сеть позволяет всем процессорам обращаться к обшей дисковой !внешней) памяти. ° Без разделения. Каждый процессор обладает собственной оперативной и дисковой памятью, но сеть позволяет всем процессорам обмениваться данными между собой. На практике обычно используется архитектура "без разделения", по крайней мере для больших систем (поскольку в двух других подходах при возрастании числа процессоров очень скоро начинают появляться конфликтные ситуации).
Если говорить точнее, то архитектура "без разделения" обеспечивает линейное ускорение, т.е. повышение времени отклика в 8 раз при увеличении вычислительной мощности аппаратного обеспечения в 8 раз, и линейное масштабирование (зса!аЪ!!!гу), т.е. время отклика остается постоянным при увеличении вычислительной мощности аппаратного обеспечения и объема данных в одинаковое количество раз. Ниже представлены некоторые способы свкчианирования данных (дага раг18!оп!п8), т.е, разбиения отношения г на секции или подчиненные отношения и распределение этих секций между п различными процессорами.
Глава 17. Оптимизаг/ил 689 ° Секцианиравание диапазона (гапйе рап!с!оп!п8). Отношение г делится на непересекающиеся секции 1, 2, ..., и на основе значений некоторого подмножества в атрибутов отношения г (концептуально отношение г отсортировано по подмножеству атрибутов в, а результат разделен на и секций равного размера). Секция Ь при этом соответствует процессору Ь Данный подход очень удобен для запросов с выборками на основе условий равенства или соответствия диапазону для подмножества атрибутов отношения в. В Хеиысвкцианиравание (ЬазЬ рап!с!оп!пй).
Каждый кортеж с отношения г соответствует процессору Ь(с), где Ь вЂ” некоторая хеш-функция. Этот метод прекрасно подходит для запросов с выборками на основе условий равенства для одного или нескольких хеш-атрибутов, а также для запросов с последовательным доступом ко всему отношению г.
° Круговое секцианиравание (гоцпд гоЬсп рагййощп8). Концептуально отношение г отсортировано некоторым образом, а з-й кортеж в отсортированном результате соответствует процессору с номером, вычисленным как результат деления з по модулю и. Этот подход прекрасно подходит для запросов с последовательным доступом ко всему отношению г. Распараллеливание обработки можно применять для выполнения отдельной операции (интраанерацианнае распараллеливание), для выполнения разных операций внутри одного запроса (межаперацианнае или интразанраснае распараллеливание) и для выполнения разных запросов (межзанраснае распараллеливание). Эти варианты рассмотрены в учебных пособиях !17.4), !17,61); некоторые методы и алгоритмы обсуждаются в 117,59), [!7.60).
Следует отметить, что параллельная версия хеш-саединения (см, раздел 17.7) особенно эффективна и широко используется на практике. 17.59.В!поп О., Вага! Н., Ое%!сс ОД., ФПСс!пзоп К. Рагайес А!8ог!сЬщз сог сЬе Ехесщюп ор Ке!анапа! ОасаЬазе А18опсйгпз й АСМ ТОПЯ. — БерсешЬег, 1983. — 8, № 3. Здесь описаны алгоритмы реализации операций сортировки, проекции, соединения, обобщения и обновления в многопроцессорных средах. Представлены также общие формулы стоимости, учитывающие операции ввода-вывода, загрузку процессора и обмен сообщениями.
Эти формулы можно адаптировать к различным многопроцессорным архитектурам. 17.60.Назап !н'., Мосвап! К. Орйппгабоп А18опс)ипз сог Ехр!о!с!п8 сйе рагайейвщСопппцпгеасюп Тгадео(Т !п Рсре!шес1 Рагайейяп О Ргос. 201Ь 1псегп. СопГ. оп Чеку Ьагйе Вага Вазез. — Яапйайо, СЬПе, БергещЬег, 1994. 17.6ЬЗПЬегзсЬасг А., Копй Н.Г., ВцдагзЬап Б. ОасаЬазе Буспегп Сопсерсз (Згд ес(!с!оп).— Нези Уог!с, ЬС.У.: Мсбгасн-НП1, 1997. Это общий учебник по управлению базами данных, который включает целую главу о параллельных системах баз данных, а также главу о различных архитектурах систем баз данных (централизованных, клиенЫсерверных, параллельных и распределенных). 690 Часть Р'.
Дополнительные аспекасьс Ответы к некоторым упражнениям 17.1. а — эквивалентны; б — эквивалентны; в — эквивалентны; г — не эквивалентны; д — эквивалентны; е — не эквивалентны (эти выражения будут эквивалентными, если заменить операцию АМО операцией ОК); ж — не эквивалентны; з — не эквивалентны; и — эквивалентны. 17.2.
В демонстрационных целях покажем, что соединение является коммутативным. Соединение А 001М В отношений А(Х, 1) и В(1, Х) — это отношение с заголовком (Х, У, Х) и такими кортежами (Х:х, усу, Х:х), что кортеж из значений х (для Х) и у (для У) должен присутствовать в отношении й, а кортеж из значений у (для У) и х (для Х) лолжен присутствовать в отношении В. Это определение абсолютно симметрично относительно й и В. Поэтому А 101М В тождественно В 101Ы А. ° 17.3. Для примера покажем ассоциативность операции объединения. Объединение А ОМ10Ы В двух отношений й и В совместимых типов — это отношение с тем же заголовком, что А и В, и телом из всех кортежей С., принадлежащих отношению А, В или им обоим одновременно.
Таким образом, если С вЂ” еще олно совместимое по типу отношение, то: ° объединение ( А ОЫ10Ы В ) ОМ10Ы С вЂ” это отношение с тем же заголовком и телом, состоящим из всех кортежей с, которые принадлежат отношению А ОМ10М В, отношению С или им обоим одновременно; ° объединение й ОМ10Ы ( В ОМ10Ы С ) — это отношение с тем же заголовком и телом, состоящим из всех кортежей 1, которые принадлежат отношению В ОЫ10Ы С, отношению А или им обоим одновременно. Эти два отношения имеют одинаковые заголовки, а тело в каждом случае состоит из всех кортежей, принадлежащих хотя бы одному из отношений А, В или С. Поэтому привеленные отношения тождественны.
° 17.4. Г!окажем, что объединение распределяется по пересечению. ° Если Е и А ОЫ10Ы ( В 1ЫТЕКЯЕСТ С ), то с и й или Е и В 1МТЕКЯЕСТ С. ° Если с и А, то с и А ()Х!ОХ В и с и А (ЭХ!ОХ С, и, следовательно, с и ( А ()Х!ОХ В ) !ХТЕКЯЕСТ ( А (!Х!ОХ С ). ° если!и В1хтеквестс, тосе В и сп с. тогда!и (А(сх!Ох В) и си ( А ОМ10М С ).
Следовательно, Е и ( й ОМ10М В ) 1МТЕКЯЕСТ ( й ОМ10М С ). ° И обратно, если с и ( й ОЫ10М В ) 1МТЕКЯЕСТ ( й ОЫ10М С ), то Е и ( А ОМ10М В ) не и ( А ОЫ10Ы С ). Из этого следует, чтоб и А или Е принадлежит обоим отношениям, В иС. Следовательно, Е и А ОМ10М ( В 1МТЕКЯЕСТ С ). ° 17.5. Покажем,что А ОЫ10Ы ( А 1МТЕКЯЕСТ В ) и А. Если с и А,то ясно,чтоб и А ОЫ10М ( А 1ЫТЕКЯЕСТ В ). И обратно, е ли Е и А ОЫ1ОЫ ( А 1ЫтЕКЯЕСт В ), то С и й С принадлежит обоим отношениям, А и В.
В любом случае получим, что Е и й. ° 17.6. Два случая с условиями уже рассмотрены в разделе 17.4. А случаи без условий достаточно просты. Покажем, что проекция не распределяется по разности на основе следующего обратного примера. Пусть отношения А(Х,Х) и В(Х,1) содержат Глава 17. Оптимизация б91 по одному кортежу, а именно — кортежи (Х:х, У:у» и (Х:х, У:г» соответственно (уиг).
Тогда (А М1МВВ В) (Х» дает отношение, содержащее только кортеж (Х:х), тогда как А(Х» М1МВЯ В(Х» дает пустое отношение. ° 17.9. Хороший набор подобных правил можно найти в 117.3». 17.10.Хороший набор подобных правил можно найти в 117.3]. 17.11. а) Выбрать сведения о поставщиках не из Лондона, не поставляющих деталь с номером ' Р 2 '1 б) выбрать сведения о поставщиках из Парижа; в) выбрать сведения о поставщиках не из Лондона, причем таких, для которых не существует других поставщиков, поставляющих меньше различных типов деталей; г) выбрать пустое множество сведений о поставщиках; д) упрощение невозможно; е) выбрать пустое множество сведений о парах поставщиков; ж) выбрать пустое множество сведений о деталях; з) выбрать сведения о таких поставщиках не из Парижа, которые поставляют наибольшее количество различных видов деталей.
Заметьте, что результаты выполнения некоторых запросов (если быть точным, то результаты запросов б, г, е и ж) можно получить непосредственно нз ограничений целостности. 17.15.Исходя из особенностей методов обработки, настоящие максимальное и минимальное значения иногда являются в некотором роде фикеивныии. Например, максимальным значением атрибута "еюр1оуее паше" (имя сотрудника) будет строка из букв с (или букв Я), а ее минимальным значением — строка, составленная из пробелов.
Если исходить из этих значений, то оценка, например, среднею расстояния между разными значениями атрибута в таблице может быть вычислена некорректно. 692 Часть К Дополнительные аспекты Глава 18 Отсутствующая информация 18.1. Введение В повседневной жизни часто приходится сталкиваться с проблемой отсутствия некоторой информации. Весьма типичны ситуации, когда, например, "дата рождения неизвестна", "имя докладчика будет объявлено дополнительно", "местонахождение объекта в данный момент неизвестно" и т.д. Поэтому в системах баз данных должен существовать механизм обработки подобных ситуаций. На практике наиболее типичный подход к решению этой проблемы (используемый, в частности, в языке Я;Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
