Кажется, известно, что для того, чтобы найти ответ на запрос по реляционной базе данных , нужно время , и невозможно избавиться от показателя степени,
Поскольку может быть очень большим, мы задаемся вопросом, почему базы данных вообще работают на практике.
Является ли это просто вопросом обычных запросов, которые вообще не велики в реальных приложениях? (Тогда интересно знать, каков обычный размер запросов, предъявляемых к системам реляционных баз данных, и каков «максимальный» размер запросов, которые, как ожидается, будут эффективно отвечать системой БД на практике .)
Заметки об экспонентене "съемный"
Чтобы показать, что показатель степенине является съемным, можно использовать запрос, спрашивающий, существует ли клика размера в графе, заданном базой данных. Проверить, имеет ли граф клик, является NP-полной задачей. Более того, он не является трактуемым с фиксированным параметром, с параметром . Подробности можно найти, например, в
Libkin, L .: Элементы теории конечных моделей. Springer (2004)
или
Papadimitriou, CH, Yannakakis, M .: О сложности запросов к базе данных. J. Comput. Сист. Sci. 58 (3), 407–427 (1999)
источник
SELECT * FROM users WHERE username="abc" AND passwrod="xyz"
) - это простой поиск, для выполнения которого требуется O (| D |). Если в соответствующих полях базы данных есть индекс, он займет O (log | D |). Я не разбираюсь в базах данных, но не думаю, что более сложные запросы будут занимать экспоненциальное время.Ответы:
Существуют большие классы запросов, которые «просты» даже в худшем случае. В частности, если класс запросов содержит только конъюнктивные запросы и каждый запрос имеет ограниченную ширину (например, treewidth, treewidth его графа инцидентности, дробной ширины гипердерева или субмодульной ширины), тогда на запрос можно ответить, используя что-то вроде дерева соединений вместе с перебором перебора для локальных частей запроса, которые отклоняются от дерева. Это требует полиномиального времени, причем степень полинома определяется параметром width.
Кажется, что многие запросы, встречающиеся на практике, являются и соединительными, и имеют небольшую ширину. Таким образом, полиномиальное время выполнения в этом случае имеет низкую степень.
Даниэль Маркс недавно представил на STOC 2010 доклад о субмодулярной ширине, полная версия которого включает в себя хорошее резюме различных понятий ширины и того, как формулировка CSP связана с формализмом базы данных (в версии конференции этого нет).
Это не полный ответ, так как он не имеет отношения к «типичной» сложности запросов к базе данных, но даже при анализе наихудшего случая есть простые запросы.
источник
Можно использовать запросы Q_n, чтобы проверить, содержит ли граф, представленный в виде базы данных, клику с n элементами. Проверить, имеет ли граф клику, является NP-полной задачей. Кроме того, это не трактуется с фиксированным параметром, с параметром n (что означает D ^ n).
источник
Другой способ ответить на этот вопрос: «Они этого не делают!»
Если вы дадите типичной реализации СУБД запрос, содержащий очень большое количество объединений, он даже не пройдет этап планирования / оптимизации (не говоря уже об оценке), даже если запрос является ациклическим или имеет очень простую структуру, такую как Андраш ссылается на выше.
Но для «типичных» рабочих нагрузок СУБД такие запросы, похоже, не возникают.
источник
Вот более реалистичная версия ответа tigreen с точки зрения человека, который на самом деле интенсивно использует (реляционные) базы данных: вся суть и сложность их применения состоит в том, чтобы структурировать их так, чтобы они требовали как можно меньшего количества объединяет для каждого когда-либо необходимого запроса насколько это возможно, и именно поэтому они действительно работают . Другими словами, не ожидайте, что базы данных сами решат сложные проблемы - они не будут, но при разумном использовании они действительно удобный и применимый инструмент.
источник
Соединения являются только квадратичными по многим ко многим отношениям. Они относительно редки: на практике большинство связей и объединений имеют отношение «один ко многим», поэтому для определения индексов / ключей им потребуется линейное время. Запросы с несколькими объединениями «многие ко многим» являются серьезной проблемой.
источник