Инструменты пользователя

Инструменты сайта


examination:rsubd:question8

Вопрос №8. Двенадцать основных принципов. Независимость от фрагментации


Независимость от фрагментации

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


Рис. 2. Пример фрагментации

В системе, которая поддерживает независимость от фрагментации, два фрагмента этой переменной отношения можно определить следующим образом:

FRAGMENT EMP AS
    N_EMP AT SITE ‘New York’ WHERE DEPT# = DEPT#('Dl')
	                        OR DEPT# = DEPT#('D3')
     L_EMP AT SITE 'London'  WHERE DEPT# = DEPT#('D2')


Здесь подразумевается, что кортежи с данными о служащих переменной отношения ЕМР отображаются в физической памяти каким-то непосредственным способом, причем D1 и D3 – отделы, расположенные в Нью-Йорке, a D2 – отдел, расположенный в Лондоне. Таким образом, кортежи с данными о служащих из Нью-Йорка хранятся на узле в Нью-Йорке, а кортежи с данными о служащих из Лондона – на узле в Лондоне. Отметим, что внутрисистемные имена фрагментов – N_EMP и L_EMP.

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

В случае операции сокращения это должна быть ортогональная декомпозиция. В случае операции проекции это должна быть декомпозиция без потерь.

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

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

Необходимо сказать еще несколько слов относительно вертикальной фрагментации. Как утверждалось выше, несомненно, что такая фрагментация должна выполняться без потерь. Поэтому разбиение переменной отношения ЕМР, показанной на рис. 2, на фрагменты-проекции, например, вида {EMP#, DEPT#} и {SALARY} было бы недопустимым. Однако в некоторых системах хранимые переменные отношения рассматриваются как имеющие скрытый, предоставляемый системой атрибут идентификатор кортежа, или сокращенно – атрибут TID (Tuple ID). Для каждого хранимого кортежа атрибут TID, грубо говоря, является адресом. Очевидно, что он является одним из потенциальных ключей для соответствующей переменной отношения. Поэтому, например, если бы переменная отношения ЕМР содержала такой атрибут, то она могла бы быть фрагментирована на проекции {TID, EMP#, DEPT#} и {TID, SALARY}, поскольку такая фрагментация уже, безусловно, выполняется без потерь. Также обратите внимание на то, что если, например, атрибут TID является скрытым, то это никак не нарушает информационный принцип, поскольку независимость от фрагментации означает, что пользователь не должен знать о существовании фрагментации.

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

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

Таким образом, если обеспечивается независимость от фрагментации, пользователи получают данные в виде некоторого представления, в котором фрагменты логически скомбинированы с помощью соответствующих операций соединения и объединения. К обязанностям системного оптимизатора относится определение фрагментов, к которым требуется физический доступ для выполнения любого из поступивших запросов пользователя. Например, в случае варианта фрагментации, показанного на рис. 2, допустим, что пользователь выдает следующий запрос:

ЕМР WHERE SALARY > 40K AND DEPT# = DEPT#('Dl')


Из определений фрагментов (которые хранятся, конечно же, в каталоге; оптимизатору должно быть известно, что весь требуемый результат может быть получен только по данным узла в Нью-Йорке, а значит, нет никакой необходимости обращаться к узлу в Лондоне.

Рассмотрим этот пример более подробно. Переменная отношения ЕМР с точки зрения пользователя может рассматриваться (упрощенно) как некоторое представление, сформированное на основе базовых фрагментов N_EMP и L_EMP, следующим образом:

VAR ЕМР «VIEW»	
    N_EMP UNION L_EMP ;


Тогда оптимизатор преобразует исходный запрос пользователя в следующее выражение:

(N_EMP UNION L_EMP) WHERE SALARY > 40K AMD DEPT# = DEPT#('Dl')


В процессе дальнейшей оптимизации это выражение будет преобразовано в следующее выражение (поскольку операция сокращения распределяется по объединению):

(N_EMP WHERE SALARY > 40K AND DEPT# = DEPT# ('Dl'))
UNION ( L_EMP WHERE SALARY > 40K AND DEPT# = DEPT# ('Dl'))


Из определения фрагмента L_EMP в каталоге оптимизатору будет известно, что второй из этих двух операндов объединения UNION эквивалентен следующему выражению:

EMP WHERE SALARY > 4OK AND DEPT# = DEPT# ('Dl') AND DEPT# = DEPT# ('D2')


Это выражение в результате вычисления даст пустое отношение, поскольку соответствующее условие в конструкции WHERE никогда не может стать истинным (TRUE). Таким образом, весь первоначальный запрос может быть приведен к следующему виду:

N_EMP WHERE SALARY > 40К AND DEPT# = DEPT# ('Dl')


Теперь оптимизатор определит, что требуется доступ лишь к данным узла в Нью-Йорке. Из предыдущего обсуждения следует, что проблема поддержки операций на фрагментированных переменных отношения в некоторых аспектах имеет много общего с проблемой поддержки операций с представлениями, определенных с помощью операций соединения и объединения (фактически это одна и та же проблема – она лишь проявляется на разных уровнях общей системной архитектуры). В частности, проблема обновления фрагментированных переменных отношения аналогична проблеме обновления представлений, определенных с помощью операций соединения и объединения. Отсюда следует, что обновление некоторого кортежа (опять же, если говорить нестрого) может привести к тому, что кортеж будет перенесен из одного фрагмента в другой (и, возможно, даже с одного узла на другой), если обновленный кортеж больше не удовлетворяет предикату для того фрагмента, которому он принадлежал ранее.

examination/rsubd/question8.txt · Последние изменения: 2014/01/15 08:21 (внешнее изменение)