раздел 2
модель представления и анализа запросов
Необходимость сравнения запросов
Сравнение запросов – одна из основных операций в механизме МП.
В существующей практике применения МП сравнение необходимо для определения
таблиц, к которым следует обратиться для получения ответа на запрос
пользователя. При совпадении текущего запроса и запроса, представляющего МП,
происходит обращение не к БТ, а к таблице соответствующего МП.
Если допустить, что различные пользователи системы могут посылать идентичные по
семантике, но отличные по форме записи запросы, то задача сравнения запросов
уже не сводится к простому совпадению текстов. Кроме того, в соответствии с
задачами, сформированными в разделе 1, необходимо предусмотреть возможность
формировать группы подобных запросов, т.е. таких, для которых возможен пересчет
с использованием или без использования некоторых дополнительных данных.
Исходя из приведенных соображений необходимо разработать модель представления
запросов и математический аппарат, позволяющий не только определять
идентичность запросов, но и определить такие характеристики как «перекрытие»,
стоимость пересчета и т.п.
Группировка запросов
В больших АКС количество запросов, для которых целесообразно создать МП, может
оказаться очень большим. Соответственно и число МП может значительно превысить
количество БТ. В результате могут потребоваться значительные дополнительные
ресурсы, что косвенно может повлиять на эффективность работы системы в целом.
Решением проблемы является объединение запросов в группы. Основанием для
объединения запросов является наличие общей части в
результатах выполнения запросов, составляющих группу.
С другой стороны, группировка обеспечивает при эксплуатации МП значительное
сокращение числа операций по обновлению МП. Можно предположить, что число
операций и время обновления МП пропорционально количеству МП. Следовательно,
увеличивается количество запросов, для которых целесообразно создавать МП.
Для группы запросов предлагается выбрать или создать «центральный» запрос. МП
для центрального запроса будет единственным и общим для всех запросов группы.
При выборе центрального запроса возможны следующие варианты (рис. 2.1):
– центральный запрос «перекрывает» все запросы группы;
– центральный запрос является общей частью всех запросов группы;
– центральный запрос выбран как один из запросов, входящих в группу.
Увеличение времени на обработку запроса при наличии группы определяется
пересчетом МП в ответ на каждый запрос и зависит от выбранного способа
пересчета.
Рис. 2.1 Принцип группировки запросов
Представление запроса
С точки зрения сравнения запросов, с каждым из них должна быть связана
следующая информация:
– тип запроса;
– используемые таблицы;
– используемые поля таблиц;
– стоимость выполнения.
Если учесть, что сравниваются только однотипные запросы (обычно SELECT),
используемые таблицы и их поля можно объединить в одну характеристику, то
каждый запрос можно охарактеризовать тройкой:
(, ,),
где = (,...,,...,) – вектор полей таблиц, которые выбирает запрос ,
= (,...,,..., ) – вектор условий выбора,
– стоимость выполнения запроса .
Каноническая форма фразы WHERE
Наибольшую сложность при сравнении запросов представляет анализ фразы WHERE,
структуру которой можно представлять в следующем виде:
V AND V ...AND (V OR V) OR (V OR...V AND V) AND…, (2.1)
где V – любое выражение, которое не содержит логических операций AND и OR.
Для выполнения операций над запросами предлагается преобразовывать фразы WHERE
в каноническую форму представления, которая может быть дизъюнктивной:
(V AND V ...AND V) OR (V AND...AND V) OR… (2.2)
или в конъюнктивной:
(V OR V…OR V) AND (V OR V…OR V) AND… (2.3)
Для этой цели предлагается специальная функция (приложение E), в соответствии с
которой в качестве операций рассматриваются только логические операции AND и
OR, а все остальные компоненты фразы условий выбора WHERE в качестве операндов.
Например, выражение NOT(T1.p1 > T1.p2 + T2.p3) является операндом, где T1, T2 –
таблицы, а p1, p2, p3 – поля таблицы.
Таким образом, каждая из фраз условий выбора Ci, Cj представляется в виде:
OR OR…OROR…OR, (2.4)
OR OR…OROR…OR, (2.5)
где , не содержат операций OR.
Определим компоненты выражений (2.4) и (2.5).
ANDAND…ANDAND…AND, (2.6)
ANDAND…ANDAND…AND, (2.7)
где , – выражения отношений.
Например, запрос: select a, b, c from T1, T2 where (a + b> c) AND (a?b) AND b?2
преобразуется в запрос:
select a, b, c from T1, T2 where (a+b>c AND b?2 AND ac AND b? 2 AND
a*c? b).
Тогда вектор =(,),
где =(a+b>c, b?2, ac, b?2, a*c?b).
Сравнения фраз WHERE в форме (2.2) или (2.3) затруднительны, поэтому введем
понятие логической структуры фразы WHERE.
Под логической структурой фразы WHERE понимается каноническая форма, в которой
не раскрывается содержание V.
Введем оценку сложности канонической формы как число выражений отношений V в
канонической форме.
Исходный вид фразы WHERE определяет сложность канонической формы, трудоемкость
процесса ее построения и дальнейшего использования. Чем больше количество V и
чем глубже находится выражение типа (V OR…OR V) в исходной фразе WHERE, тем
сложнее будет каноническая форма в виде (2.3), и проще, в виде (2.2).
Аналогично, чем больше количество V и чем глубже находится выражение типа (V
AND…AND V) в исходной фразе WHERE, тем сложнее будет каноническая форма в виде
(2.2), и проще в виде (2.3).
Оценка сложности преобразования фразы WHERE в каноническую форму
Сложность канонических форм (2.2) и (2.3) можно вычислить, основываясь на
исходной фразе условий выбора, благодаря правилам раскрытия логических
выражений. Для каждого зап
- Київ+380960830922