Конъюнктивный запрос - 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 х_ {к + 1}, \ ldots, х_ {м}}$ ${\ Displaystyle A_ {1}, \ ldots, A_ {r}}$

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

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

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

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

Фрагменты

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

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

Конъюнктивные запросы также соответствуют запросам select-project-join в реляционной алгебре (то есть запросам реляционной алгебры, которые не используют объединение или разность операций) и запросам select-from-where в SQL, в которых условие where использует исключительно конъюнкции атомарные условия равенства, т. е. условия, построенные из имен столбцов и констант без использования операторов сравнения, кроме «=», в сочетании с использованием «и». Примечательно, что это исключает использование агрегирования и подзапросов. Например, приведенный выше запрос может быть записан как 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 и является неразрешимой.

Расширения

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

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

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

Сложность

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

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

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

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

Конъюнктивные запросы - одна из величайших историй успеха теории баз данных, поскольку для конъюнктивных запросов возможно решение многих интересных проблем, которые являются вычислительно трудными или неразрешимыми для больших классов запросов. Например, рассмотрим проблему включения запроса. Мы пишем для двух отношений базы данных одной и той же схемы тогда и только тогда, когда каждый кортеж, встречающийся в, также встречается в . Для данного запроса и экземпляра реляционной базы данных мы записываем результирующее отношение оценки запроса в экземпляре просто как . Учитывая два запроса и схему базы данных , проблема сдерживания запроса заключается в том, чтобы решить, будут ли для всех возможных экземпляров базы данных по входной схеме базы данных . Основное применение сдерживания запросов - оптимизация запросов: определение эквивалентности двух запросов возможно путем простой проверки взаимного включения. ${\ Displaystyle R \ substeq 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) \ substeq Q_ {2} (I)}$

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

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

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

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

Languages

In other projects