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

19

Кажется, известно, что для того, чтобы найти ответ на запрос по реляционной базе данных , нужно время , и невозможно избавиться от показателя степени,QD|D||Q||Q|

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

Является ли это просто вопросом обычных запросов, которые вообще не велики в реальных приложениях? (Тогда интересно знать, каков обычный размер запросов, предъявляемых к системам реляционных баз данных, и каков «максимальный» размер запросов, которые, как ожидается, будут эффективно отвечать системой БД на практике .)

Заметки об экспонентене "съемный"|Q|

Чтобы показать, что показатель степенине является съемным, можно использовать запрос, спрашивающий, существует ли клика размера в графе, заданном базой данных. Проверить, имеет ли граф клик, является NP-полной задачей. Более того, он не является трактуемым с фиксированным параметром, с параметром . Подробности можно найти, например, в Libkin, L .: Элементы теории конечных моделей. Springer (2004) или Papadimitriou, CH, Yannakakis, M .: О сложности запросов к базе данных. J. Comput. Сист. Sci. 58 (3), 407–427 (1999)|Q|nnn


imz - Иван Захарящев
источник
7
Обычные запросы (вроде SELECT * FROM users WHERE username="abc" AND passwrod="xyz") - это простой поиск, для выполнения которого требуется O (| D |). Если в соответствующих полях базы данных есть индекс, он займет O (log | D |). Я не разбираюсь в базах данных, но не думаю, что более сложные запросы будут занимать экспоненциальное время.
MS Dousti
7
@imz: В вашем примере сложность , которая все еще полиномиальна. Похоже, что если в запросе k соединений, сложность O ( | D | k + 1 ) . Это полином для фиксированного k, но я думаю, что для больших k выполнение запроса будет очень медленным на практике. Следовательно, нужно избегать слишком большого количества соединений любой ценой. O(|D|2)O(|D|k+1)
MS Dousti
7
В худшем случае сложность времени экспоненциальна по длине запроса . Это не противоречит тому, что некоторые длинные запросы выполняются быстро. Специалисты по базам данных знают, какие запросы выполняются быстро в типичных механизмах баз данных, и они в любом случае не полагаются на наихудший предел в отношении длины запроса.
Цуёси Ито
2
@Kaveh: «В последней главе книги« О сложностях описания »Иммермана было небольшое обсуждение»: очень хорошее предложение. Nitpicking: это обсуждается в предпоследней главе. @imz: Вы можете также найти полезную статью « Выразительная сила SQL» .
MS Dousti
5
@imz: «Есть ли у этого графа n-клика» на практике не так часто встречается запрос. Большинство запросов больше похоже на те, что предлагает @Sadeq, и имеют сильно древовидную структуру. Более того, для действительно больших баз данных даже полностью линейный запрос обходится слишком дорого, и приходится работать с эскизом базы данных.
Андрас Саламон

Ответы:

16

Существуют большие классы запросов, которые «просты» даже в худшем случае. В частности, если класс запросов содержит только конъюнктивные запросы и каждый запрос имеет ограниченную ширину (например, treewidth, treewidth его графа инцидентности, дробной ширины гипердерева или субмодульной ширины), тогда на запрос можно ответить, используя что-то вроде дерева соединений вместе с перебором перебора для локальных частей запроса, которые отклоняются от дерева. Это требует полиномиального времени, причем степень полинома определяется параметром width.

Кажется, что многие запросы, встречающиеся на практике, являются и соединительными, и имеют небольшую ширину. Таким образом, полиномиальное время выполнения в этом случае имеет низкую степень.

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

  • Даниэль Маркс, Свойства тракторного гиперграфа для удовлетворения ограничений и конъюнктивных запросов , 2010. arxiv : 0911.0801

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

Андраш Саламон
источник
6

Можно использовать запросы Q_n, чтобы проверить, содержит ли граф, представленный в виде базы данных, клику с n элементами. Проверить, имеет ли граф клику, является NP-полной задачей. Кроме того, это не трактуется с фиксированным параметром, с параметром n (что означает D ^ n).

mishaz
источник
Пожалуйста, опубликуйте дополнительные пояснения относительно фона вопроса в виде «комментария» (не «ответа») - с помощью кнопки «Добавить комментарий» под вопросом или в качестве предложения по редактированию - со ссылкой «изменить» ниже вопрос. «Ответы» не для каких-либо обсуждений и дополнений к вопросу. (Участие здесь должно быть более удобным, если вы зарегистрируетесь как неанонимный пользователь; тогда будет легче отследить, кто что сказал в обсуждениях.)
imz - Иван Захарящев
@imz: Он назвал это ответом, потому что не имеет права комментировать. Нужно иметь как минимум 50 повторений. чтобы иметь возможность комментировать везде.
Томек Тарчинский
@Tomek, @imz, ну, сейчас обсуждается мета, если мы позволим комментировать, используя ответы или нет.
Каве
5

Другой способ ответить на этот вопрос: «Они этого не делают!»

Если вы дадите типичной реализации СУБД запрос, содержащий очень большое количество объединений, он даже не пройдет этап планирования / оптимизации (не говоря уже об оценке), даже если запрос является ациклическим или имеет очень простую структуру, такую ​​как Андраш ссылается на выше.

Но для «типичных» рабочих нагрузок СУБД такие запросы, похоже, не возникают.

tjgreen
источник
1
Для сложных запросов результатом этапа оптимизации является случайно выбранный план. Это не так плохо, как кажется, потому что путь выполнения все еще может быть «достаточно хорошим», и есть много других причин, почему оптимизация трудна за пределами комбинаторики количества соединений.
Тегири Ненаши
4

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

кто бы ни
источник
0

Соединения являются только квадратичными по многим ко многим отношениям. Они относительно редки: на практике большинство связей и объединений имеют отношение «один ко многим», поэтому для определения индексов / ключей им потребуется линейное время. Запросы с несколькими объединениями «многие ко многим» являются серьезной проблемой.

reinierpost
источник