Logo Host-telecom.com — профессиональный хостинг в Европе! Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
VDS хостинг Облачный сервер в Нидерландах и Украине

Аренда виртуального сервера от $7.91

Партнёрская программа
$20 за клиента

Wildcard сертификаты от $74,97 в год.

Дешевые ssl сертификаты для домена

Sectigo сертификаты от $7,67 в год.

хостинг Украина Виртуальный хостинг для сайта от $4,87

Регистрация домена от $2 в год

Партнерская программа – $20 за клиента

VPS с гибкой конфигурацией: за 1€

Мощные выделенные сервера: от 25€

Собственный Дата-Центр
Поддержка 24/7

2009 г.

Магия сохраняет силу

Индерпал Сингх Мумик, Шелдон Финкельштейн, Хамид Пирамеш, Раджу Рамакришнан

Назад Содержание Вперёд

3. Определения

Преобразование методом магических множеств: Алгоритм магических множеств перезаписывает запрос таким образом, что при вычислении с фиксированной точкой преобразованного запроса не генерируются нерелевантные кортежи. Идея состоит в том, чтобы вычислить набор дополнительных таблиц, которые содержат связывания, используемые для ограничения таблицы. Затем табличные выражения в запросе модифицируются путем соединения дополнительных таблиц, которые действуют как фильтры и препятствуют генерации нерелевантных кортежей. Однако на первом шаге мы производим украшенный (adorned) запрос, в котором таблицы украшаются аннотациями, показывающими, какие аргументы связываются с константами, какие ограничиваются условиями, и какие являются свободными в табличном выражении с данной таблицей. Для каждой таблицы мы имеем украшенную версию, соответствующую всем использованиям этой таблицы с применением паттерна связывания, который описывается данным украшением. Разные украшенные версии, по существу, трактуются как разные таблицы (возможно, по-разному разрешаемые). Например, pbf и pfb трактуются как разные таблицы (имена таблиц). Украшение (adornment) для некоторой n-арной таблицы определяется как строка из символов b, c и f. Позиции аргументов, которые трактуются как свободные (те, на которых нет предикатов), обозначаются как f, а позиции, которые связываются с конечным множеством данных значений (предикатами сравнения на равенство) обозначаются как b. Позиции аргументов, которые ограничены в цели некоторым предикатом, отличным от предиката сравнения на равенство, обозначаются как c.

В преобразованиях методом магических множеств из [BMSU86, BR87] распространяются связывания (предикаты сравнения на равенство) в Datalog с использованием украшений b и f. Условия игнорируются. В [MPR90] преобразования методом магических множеств расширяются для распространение связываний в программах с дубликатами и агрегированием. Расширение для работы с условиями ([MFPR90]) нуждается в адаптации для работы в присутствии дубликатов, и мы представляем эту идею в разд. 4.1. В следующем определении мы игнорируем украшения и условия.

Алгоритм магических множеств можно понимать как двухшаговое преобразование, в котором мы сначала получаем украшенный запрос Pad, а затем применяем следующее преобразование:7)

Мы создаем новый запрос Pmq. Изначально этот запрос пуст.

  1. Для каждой таблицы p из Pad создается новая таблица без дубликатов m_p. Ее арность равна числу связанных аргументов p.
  2. Для каждого табличного выражения в Pad к Pmq добавляется модифицированная версия. Если у табличного выражения r имеется заголовок, скажем, p(t) (t – это сокращение для всех атрибутов p), то модифицированная версия получается путем присоединения к телу таблицы m_p() (m_p обозначает магическую таблицу p, а – связанные аргументы p).
  3. Для каждого табличного выражения r в P с заголовком, скажем, p и для каждой таблицы qi, на которую имеется ссылка в теле выражения, к Pmq добавляется магическое табличное выражение. Его заголовок – m_qi, а тело содержит все таблицы, предшествующие qi в sips (определяется ниже), ассоциированной с r, а также магическую таблицу m_p().
  4. Создается начальная (seed) таблица m_qi(c) из предикатов сравнения по равенству в наиболее внешнем блоке запроса, где c – это набор констант, участвующих в сравнении связанных аргументов q.

Заметим, что с каждой таблицей в Pad ассоциируется магическая таблица. Если генерируется несколько табличных выражений с одним и тем же заголовком, они заменяются одним табличным выражением, в теле которого содержится объединение соответствующих тел.

Интуитивно преобразование методом магических множеств включает добавление в каждом операторе SQL магических таблиц в раздел FROM и предикатов сравнения по равенству в раздел WHERE.

ПРИМЕР 3.1 (Преобразование методом магических множеств): Рассмотрим запрос D из примера 2.1. Нам требуется вычислить среднюю зарплату в отделах в представлении dep_avgsal в том и только в том случае, когда в отделе имеется старший программист, поскольку в противном случае средняя зарплата не релевантна. При применении метода магических множеств эта оптимизация достигается путем определения магической таблицы (M3) и перезаписи D1 и D2 как M1 и M2.

(Ml): SELECT Ename FROM emp, dep_avgsalbf
      WHERE Job = 'Sr Programmer' AND Sal > Asal
            AND emp.Dno = dep_avgsalbf.Dno
			
(M2): dep_avgsalbf(Dno, Asal) AS
      (SELECT DUO, AVG(Sa1)
       FROM m_dep_avgsalbf, emp
       WHERE m_dep_avgsalbf.Dno = emp.Dno
       GROUPBY Dno)
	   
(M3): m_dep_avgsalbf(Dno) AS
      (SELECT DISTINCT Dno FROM emp
       WHERE Job = 'Sr Programmer')

Здесь m_dep_avgsalbf является магической таблицей для представления dep_avgsalbf, выдающей уместные отделы, для которых требуется вычислять представление. Верхний индекс bf показывает, что представление dep_avgsalbf всегда будет вычисляться с использованием первого аргумента, связанного с набром кортежей, а второй аргумент является свободным.

Вспомогательные магические множества: В магическом запросе примера 3.1 предикат Job = 'Sr Programmer' повторяется в операторах M1 и M3. В программе S из примера 2.1 результат выборки сохранялся в s_mag и использовался как общее подвыражение при вычислении Sl и S3. Таблицы, подобные в s_mag, называются дополнительными магическими множествами. Программа D преобразуется в программу S с использованием дополнительных преобразований методом магических множеств ([BR87]). Мы используем дополнительные магические множества в разд. 6, потому что использование общих подвыражений существенно влияет на эффективность. Для простоты объяснений в других разделах мы используем просто магические множества.

SIPS: Sideways Information Passing Strategy определяет решение о том, как передавать информацию сторонним образом в теле табличного выражения при его вычислении. Передаваемая информация поступает из предикатов табличного выражения. SIPS определяется формально в [BR87, MFPR90].

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

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

Графы зависимости: Графы зависимости широко используются для распознавания рекурсии. В табличном выражении таблицы в теле (в разделе FROM) используются для определения таблицы в заголовке. Если в некотором табличном выражении таблица q определяет таблицу r, мы обозначаем это как qr, что называется дугой зависимости. Мы определяем →→ как транзитивное замыкание →. Запрос является рекурсивным в том и только в том случае, когда в графе зависимостей имеются циклы, т.е. если существует таблица q, такая что (q →→ q). Все таблицы в сильно связанном компоненте (strongly connected component, sсс) графа зависимости называются взаимно рекурсивными.

4. Расширенное преобразование методом магических множеств

Преобразования методом магических множеств, определенные в разд. 3, применимы к реляционным системам с дубликатами и агрегацией. В этом определении заимствуются результаты из [MPR90], где определяется семантика дубликатов и агрегации в присутствии рекурсии, и использование агрегации ограничивается классом монотонных (monotonic) и магических стратифицируемых (magical stratified) программ, замкнутых относительно преобразований методом магических множеств.

Долгое время преобразования методом магических множеств считались полезными только для распространения связываний (предикатов сравнения по равенству). В нашей недавней статье [MFPR90] затрагивалось расширение метода для распространения условий (предикатов сравнения не по равенству) в программах Datalog с использованием основного преобразования на основе магических множеств (ground magic-sets transformation, GMT). В разд. 4.1 мы расширяем GMT для работы в присутствии дубликатов.

Далее мы обсуждаем, каким образом метод магических множеств может быть полезен в чисто нерекурсивных системах (разд. 4.2), и представляем однофазный алгоритм для украшения и магического преобразования запроса, которые дают нам возможность проталкивания произвольных условий с использованием только украшений b, c и f (разд. 4.3).

4.1. Проталкивание условий с использованием магии
В основном преобразовании на основе магических множеств, как оно представлено в [MFPR90], не сохраняется семантика дубликатов. Рассмотрим простой пример.

ПРИМЕР 4.1 Рассмотрим следующую программу P, где p1 и p2 – произвольные встроенные предикаты (условия), а u, v, s и w – EDB-отношения. (EDB – extensional database.)

(Pl): r(X,Z) AS
       ((SELECT X, Z
         FROM tcf(X,Y), u(Y,Z) WHERE p1(X))
        UNION ALL
        (SELECT X, Z
         FROM tcf(X,Y), v(Y,Z) WHERE p2(X)))
		 
(P2): tcf(X,Z) AS
         (SELECT X, Z FROM s(X,Y), w(Y,Z))

Пусть s = [(1,2),(1,2)], w = [(2,3)], u = [(3,4)] и v = [(3,4)]. Пусть p1(1) и p2(1) есть true. Тогда в соответствии с семантикой дубликатов программа P определяет r как мультимножество [(1,4),(1,4),(1,4),(1,4)].

GMT преобразует определение P2 в следующее:

(M2): tcf(X,Z) AS
         (SELECT X, Z FROM m(X,Y), w(Y,Z))
		
(M3): m(X,Y) AS
       ((SELECT X, Y FROM s(X,Y) WHERE p1(X))
       UNION DISTINCT
        (SELECT X, Y FROM s(X,Y) WHERE p2(X)))

Для завершения процесса создания магической программы Pl копируется в Ml. В представлении m имеется одна копия кортежа (1,2), и, следовательно, в представлении r будут иметься две копии кортежа (1,4). В результате программы P и M не эквивалентны по отношению к дубликатам. Определение m с использованием UNION ALL нам не помогает, потому что тогда в m будут иметься четыре копии (1,2), и в r будут иметься восемь копий (1,4).

Кстати, если бы либо r, либо t были DISTINCT, GMT сохранял бы семантику запроса.

GMT конструирует специальные магические множества (m), называемые дополнительными магическими множествами, для каждого раздела SELECT путем комбинирования магического множества (p1(X)) с таблицей из раздела FROM. Для сохранения семантики дубликатов требуется удаление накладываемых кортежей (значений X, общих для p1 и p2), в то время как оставшиеся в таблицах дубликаты копируются из раздела(ов) FROM. Такая операция невозможна, если никогда не конструируются магические таблицы, как в случае GMT.

Простое решение состоит в явном конструировании магических таблиц путем следующей перезаписи M2 и M3:

(E2): tcf(X,Z) AS
         (SELECT X, Z
          FROM m(X), s(X,Y), w(Y,Z))
		 
(E3): m(X) AS
       ((SELECT X FROM s(X,Y) WHERE p1(X))
       UNION DISTINCT
        (SELECT X FROM s(X,Y) WHERE p2(X)))

Здесь m – это магическое множество. Операция UNION DISTINCT удаляет дубликаты после объединения. В приведенной конструкции повторяются некоторые соединения, такие как соединение с s. В реализации Starburst у нас имеется решение, позволяющее использовать дополнительное преобразование; из-за недостатка места мы опускаем описание.

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

ПРИМЕР 4.2 (Рекурсия из-за магии): В программе P

(Pl): SELECT A, B FROM r(A,C), q(C,B)
      WHERE A = 10
	  
(P2): r(A,C) AS (SELECT A, C FROM q(A, D), t(D, C))

(P3): q(E,F) AS (SELECT E, F FROM s(E, F))
q используется дважды, в (Pl) и (P2), в обоих местах с украшением bf. Для qbf имеются связывания из rbf (Pl) и из m_rbf (P2). Поэтому магическим множеством является объединение. Магический запрос выглядит следующим образом:
(Ml): SELECT A, B FROM rbf(A,C), qbf(C,B)
      WHERE A = 10
	  
(M2): rbf(A,C) AS (SELECT A, C
                   FROM m_rbf(A), qbf(A,D), t(D,C))
				  
(M3): qbf(E,F) AS
        (SELECT E, F FROM m_qbf(E), s(E,F))
		
(M4): m_rbf (l0)

(M5): m_qbf(A) AS
(5a)       ((SELECT C FROM rbf(A,C) WHERE A = 10)
           UNION DISTINCT
(5b)        (SELECT A FROM m_rbf(A)))

Запрос (M) является рекурсивным, поскольку в его графе зависимостей имеется цикл qbf(M2)rbf(5a)m_qbf(M3)qbf.

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

Рассмотрим пример 4.2. Таблица qbf является рекурсивной, но эта рекурсия введена заново через магическую таблицу m_qbf (как это и должно быть для любой рекурсии, вводимой путем магических преобразований). Кортеж m_qbf (10) вычисляется в (5b) и приводит к кортежам в qbf через (M3). На их основе генерируются кортежи для rbf через (M2). На основе кортежей из rbf генерируются новые кортежи в m_qbf (5a) и, следовательно, в qbf . Но появление новых кортежей в qbf не может возбудить тело (M2) для генерации новых кортежей в rbf. Таким образом, эта рекурсия «сама себя не подкармливает» и заканчивается после первого цикла. Поэтому данную программу можно переписать без рекурсии.

Можно избежать введения рекурсии в магической программе, если не распознавать общих подвыражений. Если относиться к двум использованиям q в программе P как к двум разным таблицам q1 и q2, то преобразование методом магических множеств не приведет к появлению рекурсии, в чем можно убедиться, произведя преобразование методом магических множеств для программы P’, которая получается из P с использованием q1 и q2, определяемых в соответствии с P2.

Уточним интуитивные размышления, на которых основан приведенный пример.

Утверждение 4.1 Пусть M является запросом, полученным путем магического преобразования заданного запроса P в соответствии с набором полных SIPS. Тогда: (A) Если P является запросом с древовидной структурой8), и (B) если P является направленным ациклическим графом (DAG)9), то в M будет иметься ограниченная рекурсия, которую можно избежать, не образуя общих подвыражений.

4.3. Простые bcf-украшения
В преобразованиях методом магических множеств, рассматриваемых в [BMSU86, BR87, MFPR90], предполагается, что на вход поступает уже украшенная программа. Поэтому в преобразовании требуются две фазы. На первой фазе программа украшается, а на второй – магически преобразуется. В этом подразделе мы представляем однофазный алгоритм, совместно выполняющий украшение и магическое преобразование, и показываем, как это может помочь для сокращения сложности украшений.

Мы видим, что украшения обеспечивают три функции:

Функция 1: Украшение α на таблице t является абстракцией для ограничения таблицы t в точке ее использования. Эта абстракция α, а не реальное ограничение, используется для принятия решения о том, как будет вычисляться табличное выражение для tα.

Функция 2: tα вычисляется идентичным образом для всех ограничений, абстрагируемых украшением α (одни и те же SIPS, порядок SIPS, порядок соединений и украшения для таблиц, на которые имеются ссылки в табличном выражении t). Следовательно, если абстракция не является хорошей, то для некоторых ограничений tα будет разрешаться не оптимально. Украшение должно быть правильным ([MFPR90]) в том смысле, что оно должно позволять производить выбор оптимального вычисления всех ограничений (внутри класса ограничений, которые пытает фиксировать паттерн украшения), генерирующих это украшение.

Функция 3: Украшения указывают, когда в двух использованиях t может разделяться одна и та же копия t как общее подвыражение. Основанием для того требования, чтобы в использованиях имелось одно и то же украшение, является то, что тогда магические множества генерируются на основе этих использований с одними и теми же аргументами, что позволяет применять объединения.

В паттерне bcf-украшения, введенном в [MFPR90], c-украшение используется только для независимых условий. Условие на атрибуте X называется независимым, если оно может быть выражено без ссылки на какой-либо свободный (f) атрибут. Таким образом, условие X > 10 является независимым. Условие X > Y независимо, если атрибут Y является связанным, в противном случае это условие зависимо. Алгоритм украшения и следующий за ним GMT из [MFPR90] работают в предположении, что проталкиваются только независимые условия, и что из заданных условий не выводятся какие-либо новые. В [MFPR90] также говорится, что при использовании двухфазного алгоритма невозможно вылавливать и проталкивать зависимые и более общие типы условий на основе паттерна bcf-украшения. Для проталкивания таких условий требуются более сильные паттерны.

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

Определим паттерн простого bcf-украшения аналогично bcf-паттерну из [MFPR90] (обсуждавшегося в разд. 4.1) за исключением того, что украшение c на атрибуте теперь представляет любой тип условия на этом атрибуте, а не только независимое условие.

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

В следующей лемме мы используем определение опорных (grounding) таблиц из [MFPR90]. При заданном условии p на порождаемой таблице t набор таблиц раздела FROM табличного выражения для t, содержащих все атрибуты, на которые имеются ссылки из p, называется опорным набором. Например, в операторе P2 примера 4.1 s является опорной таблицей для ограничения X > 10.

Лемма 4.1 Пусть p1 и p2 – два ограничения на одних и тех же атрибутах порождаемой таблицы t. Тогда, если множество G является опорным для p1, то G является опорным множеством и для p2.

Используя Лемму 4.1, мы покажем, что однофазный алгоритм с простыми bcf-украшениями выполняет все функции, которые должны выполнять украшения.

Функция 1: Если реальные ограничения на таблице доступны во время украшения ее тела, то для функции 1 украшения больше не требуются. В результате абстракция, которую они представляют, не является важной.

Функция 2: Функция 2 обеспечивается паттерном простых bcf-украшений для класса произвольных ограничений; это следует из Леммы 4.1 и основного преобразования методом магических множеств [MFPR90]. Проиллюстрируем это на примере.

ПРИМЕР 4.3 (Простое bcf-украшение):

(P1): SELECT X,Y,Z FROM t(X,Y,Z) 
      WHERE X > 10 AND Y > 10
	  
(P2): SELECT X,Y,Z FROM t(X,Y,Z)
      WHERE X > Y
	  
(P13): t(X,Y,Z) AS (SELECT DISTINCT X,Y,Z 
                    FROM q1(X), q2(Y), u(X,Z))

Для обоих запросов P1 и P2 генерируется украшение tccf. По Лемме 4.1 {q1,q2} является опорным множеством для любого ограничения над двумя первыми аргументами t. Таблицы q1 и q2 должны украшаться по-разному для двух использований tccf, а u должно украшаться как ubf для обоих использований. Если бы мы украшали программу без конструирования магических множеств и без использования информации, за исключением украшения ccf на t, то мы не смогли бы произвести желаемое украшение. Однако с использованием своего однофазного алгоритма мы получаем:

(M1): SELECT X, Y, Z FROM tccf(X,Y,Z) 
      WHERE X > 10 AND Y > 10
	  
(M2): SELECT X, Y, Z FROM tccf(X,Y,Z) 
      WHERE X > Y
	  
(M3): tccf (X,Y,Z) AS 
           SELECT DISTINCT X, Y, Z 
           FROM m_tccf (X,Y), ubf (X,Z))
		   
(M4): m_tccf(X,Y) AS 
        ((SELECT X, Y FROM q1c(X), q2c(Y) 
          WHERE X > 10 AND Y > 10) 
        UNION DISTINCT 
         (SELECT X, Y FROM q1f(X), q2c(Y) 
          WHERE X > Y ))

Отметим разные украшения для q1 в двух операторах SELECT в (M4) и украшение b в (M3), появившиеся по причине наличия магических множеств.

Вообще говоря, для c-украшенной таблицы t GMT переводит опорные таблицы tα в дополнительную таблицу.10) Для любых двух ограничений r1 и r2, генерирующих одно и то же bcf-украшение α на t, опорные таблицы q являются одними и теми же (Лемма 4.1). Таблица q будет копироваться в две таблицы – в (M1) вместе с r1 и в (M2) вместе с r2. Если эти ограничения обладают полностью различной природой, то в (M1) и (M2) для таблиц q могли бы выбираться разные украшения и разные порядки SIPS. Однако в исходном texp для tα в дополнительные магические множества выглядят как генерирующие связывания для всех украшений b или c, независимо от природы ограничений. Поскольку мы не различаем типы связывания при принятии решения о вычислении табличного выражения, вычисление tα будет оптимальным для обоих ограничений.

Функция 3: Паттерн простых bcf-украшений выполняет функцию 3. Если при двух использованиях таблицы в условиях применяются одни и те же аргументы, то и у их опорных магических множеств будут одни и те же аргументы.


7) В разд. 4.3 мы покажим, как можно объединить эти два шага.

8) В запросе с древовидной структурой отсутствуют общие подвыражения.

9) В DAG могут иметься общие подвыражения, но отсутствует рекурсия.

10) Как отмечалось в подразделе 4.1, в некоторых случаях это должно считаться магической таблицей. Это не является проблемой, но для простоты предположим, что у нас всегда имеется дополнительная таблица.

Назад Содержание Вперёд

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

ATLEX Выделенные серверы: в Европе / в России.

Виртуальные серверы: в Европе / в России.

Партнерская программа

Ваш сайт в 8 раз быстрее конкурентов. Хостинг от $2.95

VPS: SSD, KVM, бесплатные бэкапы и администрирование

Все необходимое для вашего сайта и лучшая техподдержка 24/7

хостинг сайтов ГиперХост — хостинг сайтов который Вы искали.

Виртуальный хостинг, Аренда VPS серверов, рация доменных имен, SSL сертификаты

💰 Самые низкие цены на домены

🔒 Отличный хостинг на SSD c бесплатными SSL

💻 Огромнейший выбор dedicated выделенных серверов

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

Новости мира IT:

Архив новостей

Последние комментарии:

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...