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

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

Определение

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

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

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

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

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

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

(студент, адрес). ∃ (студент2, курс). посещает (студент, курс) ∧ пол (студент, 'мужчина') ∧ посещает (студент2, курс) ∧ пол (студент2, 'женщина') ∧ живет (студент, адрес)

Обратите внимание: поскольку единственное, что представляет интерес, - это студент-мужчина и его адрес, это единственные выделенные переменные, а переменные курс, студент2 только экзистенциально количественно, т.е. незаметно.

Фрагменты

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

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

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

Выбрать л.ученик, л.адресиз   посещает а1, Пол g1,       посещает а2, Пол g2,       жизни лкуда  а1.ученик = g1.ученик и       а2.ученик = g2.ученик и       л.ученик = g1.ученик и       а1.курс = а2.курс и       g1.Пол = 'мужчина' и       g2.Пол = 'женский';

Лог данных

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

 результат(ученик, адрес) :- посещает(ученик, курс),  Пол(ученик, мужской),                             посещает(студент2, курс), Пол(студент2, женский),                             жизни(ученик, адрес).

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

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

Расширения

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

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

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

Сложность

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

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

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

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

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

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

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

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

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

Рекомендации

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

внешняя ссылка

• Ульман, Дж. Д. Интеграция информации с использованием логических представлений Теоретическая информатика, 2000, 239, 189-210^{[мертвая ссылка ]}
• Георг Готтлоб, Презентация методов структурной декомпозиции для эффективного вычисления конъюнктивных запросов (PDF)