Конъюнктивный запрос

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

Определение

Конъюнктивные запросы представляют собой фрагмент (независимой от предметной области) логики первого порядка, заданной набором формулы, которые можно составить из атомарных формул с помощью конъюнкции ∧ и экзистенциальная квантификация ∃, но без использования дизъюнкции ∨, отрицания ¬, или универсальная квантификация ∀. Каждую такую формулу можно (эффективно) переписать в эквивалентную формулу в пренексной нормальной форме , поэтому эта форма обычно просто предполагается.

Таким образом, конъюнктивные запросы имеют следующую общую форму:

(x_{1},\ldots ,x_{k}).\exists x_{k+1},\ldots x_{m}.A_{1}\wedge \ldots \wedge A_{r}

,

со свободными переменными $x_{1},\ldots ,x_{k}$ называются выделенными переменными, а связанные переменные $x_{k+1},\ldots ,x_{m}$ называются неразличимыми переменными. $A_{1},\ldots ,A_{r}$ представляют собой атомарные формулы .

В качестве примера того, почему важно ограничение на независимую от предметной области логику первого порядка, рассмотрим $x_{1}.\exists x_{2}.R(x_{2})$ , который не является независимым от домена; см. теорему Кодда . Эта формула не может быть реализована во фрагменте реляционной алгебры select-project-join и, следовательно, не должна рассматриваться как конъюнктивный запрос.

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

(student, address) . ∃ (student2, course) .
   attends(student, course) ∧ gender(student, 'male') ∧ 
   attends(student2, course) ∧
   gender(student2, 'female') ∧ lives(student, address)

Обратите внимание: поскольку единственным объектом, представляющим интерес, является студент-мужчина и его адрес, это единственные различающиеся переменные, а переменные course, student2 лишь экзистенциально квантифицированы , то есть неразличимы.

Фрагменты

Конъюнктивные запросы без различающихся переменных называются логическими конъюнктивными запросами . Конъюнктивные запросы, в которых все переменные различаются (и ни одна переменная не связана), называются запросами равного соединения . ^[1] они эквивалентны потому что в реляционном исчислении запросам эквисоединения в реляционной алгебре (при выборе всех столбцов результата).

Связь с другими языками запросов

Конъюнктивные запросы также соответствуют запросам выбора-проекта-объединения в реляционной алгебре (т. е. запросы реляционной алгебры, которые не используют операции объединения или разности), а также запросы выбора откуда в SQL , в которых условие где использует исключительно соединения условий атомарного равенства, т.е. условия, созданные из имен столбцов и констант без использования операторов сравнения. чем "=", в сочетании с помощью "и". Примечательно, что это исключает использование агрегации и подзапросов. Например, приведенный выше запрос можно записать как SQL-запрос фрагмента конъюнктивного запроса как

select l.student, l.address
from   attends a1, gender g1,
       attends a2, gender g2,
       lives l
where  a1.student = g1.student and
       a2.student = g2.student and
       l.student = g1.student and
       a1.course = a2.course and
       g1.gender = 'male' and
       g2.gender = 'female';

Ученый-компьютерщик

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

 result(student, address) :- attends(student, course),  gender(student, male),
                             attends(student2, course), gender(student2, female),
                             lives(student, address).

Хотя в этой записи нет кванторов, переменные, появляющиеся в заголовке правила, по-прежнему неявно оцениваются универсально , в то время как переменные, появляющиеся только в теле правила, по-прежнему неявно оцениваются экзистенциально.

Хотя любой конъюнктивный запрос может быть записан как правило Datalog, не каждая программа Datalog может быть записана как конъюнктивный запрос. Фактически, только отдельные правила для экстенсиональных символов-предикатов могут быть легко переписаны как эквивалентный конъюнктивный запрос. Проблема определения того, существует ли для данной программы Datalog эквивалентная нерекурсивная программа (соответствующая положительному запросу реляционной алгебры или, что то же самое, формуле положительной экзистенциальной логики первого порядка или, как частный случай, конъюнктивному запросу) известна как проблема ограниченности журнала данных и неразрешима. ^[2]

Расширения

Расширения соединительных запросов, обеспечивающие большую выразительную силу, включают:

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

Формальное изучение всех этих расширений оправдано их применением в реляционных базах данных и находится в области теории баз данных .

Сложность

Для исследования вычислительной сложности обработки конъюнктивных запросов следует выделить две проблемы. Первая — это проблема оценки конъюнктивного запроса в реляционной базе данных , где и запрос, и база данных считаются частью входных данных. Сложность этой проблемы обычно называют комбинированной сложностью , тогда как сложность задачи оценки запроса в реляционной базе данных, где запрос предполагается фиксированным, равна называется сложностью данных . ^[3]

Конъюнктивные запросы являются NP-полными относительно комбинированной сложности . ^[4] в то время как сложность данных конъюнктивных запросов очень низка, в параллельном классе сложности AC0 , который содержится в LOGSPACE и, следовательно, в полиномиальном времени . NP -трудность конъюнктивных запросов может показаться удивительной, поскольку реляционная алгебра и SQL строго включают в себя конъюнктивные запросы и, таким образом, по крайней мере, столь же сложны (фактически, реляционная алгебра является PSPACE -полной в отношении комбинированной сложности и, следовательно, даже сложнее в широко придерживались предположений теории сложности). Однако в обычном сценарии приложения базы данных велики, а запросы очень малы, и модель сложности данных может подойти для изучения и описания их сложности.

Проблема перечисления всех ответов на небулев конъюнктивный запрос изучалась в контексте алгоритмов перечисления с характеристикой (при некоторых предположениях вычислительной сложности ) запросов, для которых перечисление может быть выполнено с линейной предварительной обработкой по времени и постоянной задержкой между каждое решение. В частности, это ациклические конъюнктивные запросы, которые также удовлетворяют условию свободного соединения . ^[5]

Формальные свойства

Конъюнктивные запросы — одна из историй величайшего успеха теории баз данных , поскольку многие интересные задачи, которые являются вычислительно трудными или неразрешимыми для более крупных классов запросов, решаемы для конъюнктивных запросов. ^[6] Например, рассмотрим проблему сдерживания запроса . Мы пишем $R\subseteq S$ для двух отношений с базой данных $R,S$ одной и той же схемы тогда и только тогда, когда каждый кортеж, встречающийся в $R$ также встречается в $S$ . Учитывая запрос $Q$ и реляционной базы данных экземпляр $I$ , мы записываем отношение результата оценки запроса к экземпляру просто как $Q(I)$ . Учитывая два запроса $Q_{1}$ и $Q_{2}$ и схемы базы данных , проблема содержания запроса — это проблема принятия решения о том, будут ли для всех возможных экземпляров базы данных $I$ над входной схемой базы данных, $Q_{1}(I)\subseteq Q_{2}(I)$ . Основное применение сдерживания запросов заключается в оптимизации запросов: решить, эквивалентны ли два запроса, можно, просто проверив взаимное сдерживание.

Проблема содержания запроса неразрешима для реляционной алгебры и SQL , но разрешима и NP-полна для конъюнктивных запросов. Фактически оказывается, что проблема содержания запроса для конъюнктивных запросов — это точно такая же проблема, как и проблема оценки запроса. ^[6] Поскольку запросы, как правило, небольшие, NP-полнота здесь обычно считается приемлемой. Проблема содержания запроса для конъюнктивных запросов также эквивалентна проблеме удовлетворения ограничений . ^[7]

Важным классом конъюнктивных запросов с полиномиальной комбинированной сложностью являются ациклические конъюнктивные запросы. ^[8] Оценка запроса и, следовательно, его удержание являются LOGCFL -полными и, следовательно, выполняются за полиномиальное время . ^[9] Ацикличность конъюнктивных запросов — это структурное свойство запросов, которое определяется относительно гиперграфа запроса : ^[6] конъюнктивный запрос является ациклическим тогда и только тогда, когда его ширина гипердерева равна 1. Для особого случая конъюнктивных запросов, в которых все используемые отношения являются двоичными, это понятие соответствует древовидной ширине графа зависимостей переменных в запросе (т. е. граф, имеющий переменные запроса в виде узлов и ненаправленного ребра $\{x,y\}$ между двумя переменными тогда и только тогда, когда существует атомарная формула $R(x,y)$ или $R(y,x)$ в запросе), а конъюнктивный запрос является ациклическим тогда и только тогда, когда его граф зависимостей является ациклическим .

Важным обобщением ацикличности является понятие ограниченной ширины гипердерева , которая является мерой того, насколько близок к ациклическому гиперграф, аналогично ограниченной ширине дерева в графах . Конъюнктивные запросы ограниченной ширины дерева имеют LOGCFL . комбинированную сложность ^[10]

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

Ссылки

^ Дэн Олтяну, Якуб Заводный, Границы размера факторизованных представлений результатов запроса , 2015, DOI 10.1145/2656335, [1]
^ Герд Г. Хиллебранд , Пэрис К. Канеллакис , Гарри Г. Майрсон , Моше Ю. Варди : Неразрешимые проблемы ограниченности для программ регистрации данных. Дж. Лог. Программа. 25(2): 163–190 (1995)
^ Варди, Моше Ю. (1982), «Сложность реляционных языков запросов (расширенное резюме)», Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 , стр. 137–146, CiteSeerX 10.1.1.331.6045 , doi : 10.1145/800070.802186 , ISBN 978-0897910705 , S2CID 7869248 , заархивировано из оригинала 23 августа 2011 г. , получено 16 мая 2011 г.
^ Ашок К. Чандра и Филип М. Мерлин , 1977. Оптимальная реализация конъюнктивных запросов в реляционных базах данных . STOC '77: Материалы девятого ежегодного симпозиума ACM по теории вычислений [2]
^ Баган, Гийом; Дюран, Арно; Гранжан, Этьен (2007). Дюпарк, Жак; Хензингер, Томас А. (ред.). «Об ациклических конъюнктивных запросах и перечислении с постоянной задержкой». Информатика Логика . Конспекты лекций по информатике. 4646 . Шпрингер Берлин Гейдельберг: 208–222. дои : 10.1007/978-3-540-74915-8_18 . ISBN 9783540749158 .
^ Перейти обратно: ^а ^б ^с Серж Абитебул , Ричард Б. Халл , Виктор Виану : Основы баз данных. Аддисон-Уэсли, 1995.
^ Колайтис, Фокион Г.; Варди, Моше Ю. (2000), «Сдерживание конъюнктивного запроса и удовлетворение ограничений», Журнал компьютерных и системных наук , 61 (2): 302–332, doi : 10.1006/jcss.2000.1713
^ Михалис Яннакакис : Алгоритмы для ациклических схем баз данных. Учеб. ВЛДБ 1981: 82-94.
^ Георг Готтлоб , Никола Леоне и Франческо Скарчелло (2001). «Сложность ациклических конъюнктивных запросов». Журнал ACM 48 (3): 431–498. дои : 10.1145/382780.382783 .
^ Георг Готтлоб , Никола Леоне и Франческо Скарчелло : Разложение гипердерева и управляемые запросы. Дж. Компьютер. Сист. наук. 64(3): 579-627 (2002).
^ Георг Готтлоб , Кристоф Кох , Клаус У. Шульц : Конъюнктивные запросы по деревьям. Дж. ACM 53(2): 238-272 (2006).

Внешние ссылки

[1] Дэн Олтяну, Якуб Заводный, Границы размера факторизованных представлений результатов запроса , 2015, DOI 10.1145/2656335, [1]

[2] Герд Г. Хиллебранд , Пэрис К. Канеллакис , Гарри Г. Майрсон , Моше Ю. Варди : Неразрешимые проблемы ограниченности для программ регистрации данных. Дж. Лог. Программа. 25(2): 163–190 (1995)

[3] Варди, Моше Ю. (1982), «Сложность реляционных языков запросов (расширенное резюме)», Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 , стр. 137–146, CiteSeerX 10.1.1.331.6045 , doi : 10.1145/800070.802186 , ISBN 978-0897910705 , S2CID 7869248 , заархивировано из оригинала 23 августа 2011 г. , получено 16 мая 2011 г.

[4] Ашок К. Чандра и Филип М. Мерлин , 1977. Оптимальная реализация конъюнктивных запросов в реляционных базах данных . STOC '77: Материалы девятого ежегодного симпозиума ACM по теории вычислений [2]

[5] Баган, Гийом; Дюран, Арно; Гранжан, Этьен (2007). Дюпарк, Жак; Хензингер, Томас А. (ред.). «Об ациклических конъюнктивных запросах и перечислении с постоянной задержкой». Информатика Логика . Конспекты лекций по информатике. 4646 . Шпрингер Берлин Гейдельберг: 208–222. дои : 10.1007/978-3-540-74915-8_18 . ISBN 9783540749158 .

[AHV-6] Перейти обратно: ^а ^б ^с Серж Абитебул , Ричард Б. Халл , Виктор Виану : Основы баз данных. Аддисон-Уэсли, 1995.

[7] Колайтис, Фокион Г.; Варди, Моше Ю. (2000), «Сдерживание конъюнктивного запроса и удовлетворение ограничений», Журнал компьютерных и системных наук , 61 (2): 302–332, doi : 10.1006/jcss.2000.1713

[8] Михалис Яннакакис : Алгоритмы для ациклических схем баз данных. Учеб. ВЛДБ 1981: 82-94.

[9] Георг Готтлоб , Никола Леоне и Франческо Скарчелло (2001). «Сложность ациклических конъюнктивных запросов». Журнал ACM 48 (3): 431–498. дои : 10.1145/382780.382783 .

[10] Георг Готтлоб , Никола Леоне и Франческо Скарчелло : Разложение гипердерева и управляемые запросы. Дж. Компьютер. Сист. наук. 64(3): 579-627 (2002).

[11] Георг Готтлоб , Кристоф Кох , Клаус У. Шульц : Конъюнктивные запросы по деревьям. Дж. ACM 53(2): 238-272 (2006).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]