Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

62-501.72

ОБНОВЛЕНИЕ МАТЕРИАЛИЗОВАННЫХ ПРЕДСТАВЛЕНИЙ

И ШАБЛОНОВ ЗАПРОСОВ В  РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ

Кунгурцев А.Б.

Использование материализованных представлений (МП) – сохраненных результатов запросов – может существенно повысить производительность информационной системы. Однако при необоснованном применении технологии МП можно получить и противоположный результат [1]. Анализ эффективности применения МП, основанный на исследовании структуры запроса и статистических данных о работе информационной системы (ИС), приведен в [2]. Вместе с тем, остается проблема пересчета МП в случае, когда произошло изменение используемых в нем данных, на что может тратиться значительное время.  В настоящей работе предлагается метод частичного пересчета (коррекции) материализованного представления на основе анализа типа операции над данными, приведшей к их изменению, а также характера использования этих данных в МП. Процедура идентификации запросов или групп «родственных» запросов выходит за рамки данного исследования.

Технология МП применима для  запросов типа «Выборка» (SELECT) [3]. Для других типов запросов возможно использование шаблонов, о которых речь пойдет позже.

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

Постановку задачи обновления МП можно сформулировать в следующем виде. Пусть D  - база данных, V - материализованное представление, определенное на D посредством  некоторой функция (запроса) Х на множестве D.

V = X ( D )

Пусть U – операция обновления D. Её результат

U (D )

Тогда проблема обновления МП сводится к поиску такой операции обновления U’, для которой истинно выражение

U’(V) = X ( U ( D ) )

Проанализируем операции, приводящие к изменению данных в D и используемых в МП, с точки зрения разработки методов частичного пересчета (обновления) МП.

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

Например, следующий запрос может корректировать МП.

DELETE FROM МП

WHERE t1_k = n;

Здесь t1_k = n определяет первичный ключ строки, удаляемой из базовой таблицы t1.

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

Операция UPDATE, примененная для поля, которое не фигурирует в МП (но из таблицы, которую использует МП) никак не влияет на МП.

Операция UPDATE над данными, входящими в условие выборки WHERE, исключает частичный пересчет и требует полного обновления МП.

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

INSERT INTO МП

SELECT . . .

FROM t1, . . .

WHERE . . . AND t1.k = n . .  .

Здесь текст запроса определяется запросом для МП, в котором вместо всей таблицы анализируется только одина строка с первичным ключом t1_k = n.

Операция INSERT, вставляющая новую строку в базовую таблицу, используемую в МП, должна привести к обновлению МП. Если данные из базовой таблицы входят в условия, то требуется полное обновление МП, если же данные используются только в строках  МП, то для каждой новой строки базовой таблицы следует выполнить пересчет в соответствии с  условием выборки  МП и возможно добавить новые строки в МП. Корректирующий запрос для этого случая аналогичен запросу, рассмотренному выше для операции UPDATE над данными базовой таблицы.

Рассмотрим возможность частичного пересчета МП, содержащего агрегирующие функции. Начнем со случая, когда агрегация выполняется без условия (по всей таблице). Для функций MAX(выражение) и  MIN(выражение) при выполнении операции UPDATE корректировка выполняется в соответствии со следующей схемой

 If max < d then max: =d ;

 If min > d then min: =d ;

где d – новое значение поля, а max и min -  значения функций MAX и  MIN соответственно, находившиеся в МП до изменения d.

Вставка новой строки может быть компенсирована в МП по этой же схеме.

Удаление строки может корректироваться двумя способами. Если сохранять первичные ключи строк, чьи поля определяют MAX и  MIN, то достаточно сравнить эти ключи с ключом удаляемого поля. При совпадении значений требуется пересчет агрегирующей функции. В противном случае её значение остается неизменным. Второй способ предусматривает анализ удаляемой строки и может быть выполнен по схеме

If max = d_old then <пересчет MAX() > ;

If min = d_old then <пересчет MIN()> ;

где d_old –  значение поля в удаляемой строке, а max и min -  значения функций MAX и  MIN соответственно, находившиеся в МП до удаления строки.

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

Для функции SUM(выражение) корректировка значения при изменении некоторого поля, входящего в сумму возможна по следующей схеме.

sum:=sum –d_old +d_new,

 где sum –значение суммы в МП; d_old – старое значение поля;  d_new – новое значение поля.

Если произошло удаление строки, поле из которой вошло в сумму, то из суммы нужно вычесть значение этого поля.

sum:=sum –d_old

 Если произошла вставка строки, поле из которой войдет в сумму, то к сумме нужно прибавить значение этого поля.

sum:=sum  +d_new

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

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

Рассмотрим случай, когда агрегация выполняется не по всей таблице, а определяется  предложением GROUP BY <список_полей>.

Для функций MAX() и  MIN() при выполнении операции UPDATE прежде всего необходимо определить, входит ли редактируемое поле в список полей GROUP BY. Если поле входит в список, то должна произойти перегруппировка в таблице. Для выполнения функций MAX() и  MIN() это равносильно выполнению операции DELETE для одной группы и INSERT для другой группы. Корректировка МП для этих операций рассмотрена выше. Если редактируемое поле не входит в список полей GROUP BY, то для той группы, куда входит редактируемая строка, следует выполнить анализ, аналогичный предложенному ранее для операции UPDATE  для всей таблицы.

Для функций MAX() и  MIN() при выполнении операции DELETE можно применить ранее рассмотренную корректировку для DELETE, ограничив её группой, куда входила удаляемая строка.

Для функций MAX() и  MIN() при выполнении операции INSERT можно применить ранее рассмотренную корректировку для INSERT, ограничив её группой, куда войдет вставляемая строка.

Для функции SUM() при корректировке некоторого поля (UPDATE) прежде всего необходимо определить входит ли редактируемое поле в список полей GROUP BY. Если поле входит в список, то должна произойти перегруппировка в таблице. В этом случае можно предложить следующую схему пересчета.

sum1:=sum1 – d;

sum2:=sum2 + d;

 где sum1 –значение суммы в группе, откуда исключается строка, sum2 –значение суммы в группе, куда включается строка, d –  значение поля.

Для функции SUM() при удалении строки (DELETE)  необходимо определить группу, куда входила удаляемая строка. Далее применяется корректировка аналогичная рассмотренной ранее для всей таблицы.

Для функции  SUM()  при выполнении операции вставки строки (INSERT) можно применить ранее рассмотренную корректировку для INSERT для всей базовой таблицы, ограничив её группой, куда войдет вставляемая строка.

Для функции  SUM()  при выполнении операции удаления строки (DELETE)  можно применить ранее рассмотренную корректировку для DELETE для всей базовой таблицы, ограничив её группой, откуда удаляется строка.

Для функции COUNT()  при выполнении операции UPDATE  необходимо определить входит ли редактируемое поле в список полей GROUP BY. Если поле входит в список, то должна произойти перегруппировка в таблице. Это приведет к тому, что количество строк для группы, откуда строка была исключена, уменьшается на единицу, а количество строк в группе, куда она оказалась включенной, увеличилось на единицу. Если редактируемое поле не входит в список полей GROUP BY, то корректировка не нужна.

Операции INSERT и DELETE выполняются аналогично ранее рассмотренной корректировке для всей таблицы, но только для групп, куда попадают вставляемые или удаляемые строки.

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

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

UPDATE t1

SET . . .

WHERE t1.k = n1 OR t1.k = n2 . . .

Здесь значения первичного ключа  t1.k  равное  n1 и n2 определяет строки базовой таблицы, к полям которой применяется редактирование.

     Если в течение периода времени между двумя использованиями шаблона в базовой таблице произошли изменения под действием других запросов (условие выборки в шаблоне не изменилось), то первичные ключи измененных строк включаются в шаблон. Если за этот же период произошло удаление строк, то первичные ключи удаленных строк удаляются  из шаблона, а если произошла вставка строк – то новые первичные ключи добавляются в шаблон. При изменении условия выборки в шаблоне по причине изменения данных, формирующих это условие, шаблон как бы начинает работать «с нуля». Это проявляется в том, что список ключей шаблона обнуляется и выборка выполняется по всем строкам базовых таблиц. Далее процесс повторяется.

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

WHERE field = 0

никакой необходимости в создании шаблонов нет.

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

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

1.                  Кузнецов С. Методы оптимизации выполнения запросов в реляционных СУБД. –www.citforum.ru/database/articles/art_26.html-2003

2.                  Кунгурцев А.Б., Куок Винь Нгуен Чан. Анализ возможности применения материализованных представлений в информационных системах. Труды ОНПУ, 2003, вып 2(20). – C. 102 – 106.

3.                  К. Дж. Дейт Введение в системы баз данных. М.:Вильямс,2000.848с.