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

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

Определение

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

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

${\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}}$

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

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

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

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

Фрагменты

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

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

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

выберите l . student , l . address из attends a1 , gender g1 , attends a2 , gender g2 , lives l, где a1 . student = g1 . student и a2 . student = g2 . student и l . student = g1 . student и a1 . course = a2 . course и g1 . gender = 'мужской' и g2 . gender = 'женский' ;                                   

Журнал данных

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

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

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

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

Расширения

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

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

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

Сложность

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

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

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

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

Конъюнктивные запросы являются одной из самых успешных историй теории баз данных , поскольку многие интересные проблемы, которые являются вычислительно сложными или неразрешимыми для больших классов запросов, осуществимы для конъюнктивных запросов. ^[6] Например, рассмотрим проблему включения запроса. Мы пишем для двух отношений базы данных одной и той же схемы тогда и только тогда, когда каждый кортеж, встречающийся в , также встречается в . При наличии запроса и экземпляра реляционной базы данных мы записываем результирующее отношение оценки запроса для экземпляра просто как . При наличии двух запросов и и схемы базы данных проблема включения запроса — это проблема принятия решения о том, для всех ли возможных экземпляров базы данных по входной схеме базы данных . Основное применение включения запроса — оптимизация запросов: принятие решения о том, эквивалентны ли два запроса, возможно путем простой проверки взаимного включения. ${\displaystyle R\subseteq 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 , но разрешима и NP-полна для конъюнктивных запросов. Фактически, оказывается, что проблема содержания запроса для конъюнктивных запросов — это точно такая же проблема, как и проблема оценки запроса. ^[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. Герд Г. Хиллебранд, Парис К. Канеллакис , Гарри Г. Мэрсон, Моше Й. Варди : Неразрешимые проблемы ограниченности для программ Datalog. J. Log. Program. 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, заархивировано из оригинала 2011-08-23 , извлечено 2011-05-16
4. Ашок К. Чандра и Филип М. Мерлин, 1977. Оптимальная реализация конъюнктивных запросов в реляционных базах данных . STOC '77: Труды девятого ежегодного симпозиума ACM по теории вычислений [2]
5. Баган, Гийом; Дюран, Арно; Гранжан, Этьен (2007). Дюпарк, Жак; Хензингер, Томас А. (ред.). «Об ациклических конъюнктивных запросах и перечислении с постоянной задержкой». Computer Science Logic . Lecture Notes in Computer Science. 4646. Springer Berlin Heidelberg: 208–222. doi :10.1007/978-3-540-74915-8_18. ISBN 9783540749158.
6. Серж Абитбул , Ричард Б. Халл, Виктор Виану : Основы баз данных. Addison-Wesley, 1995.
7. Колайтис, Фокион Г.; Варди, Моше Й. (2000), «Конъюнктивно-запросное сдерживание и удовлетворение ограничений», Журнал компьютерных и системных наук , 61 (2): 302–332, doi : 10.1006/jcss.2000.1713
8. Михалис Яннакакис : Алгоритмы для ациклических схем баз данных. Proc. VLDB 1981: 82-94.
9. Георг Готтлоб , Никола Леоне и Франческо Скарчелло (2001). «Сложность ациклических конъюнктивных запросов». Журнал ACM 48 (3): 431–498. doi :10.1145/382780.382783.
10. Георг Готтлоб , Никола Леоне и Франческо Скарчелло: Разложения гипердеревьев и трактуемые запросы. J. Comput. Syst. Sci. 64(3): 579-627 (2002)
11. Георг Готтлоб , Кристоф Кох, Клаус У. Шульц: Конъюнктивные запросы по деревьям. Дж. ACM 53(2): 238-272 (2006).

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

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