Языки запросов к базе данных для эффективных запросов

9

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

Существуют ли языки запросов, которые могут реализовывать только эффективные запросы?

Если таких языков нет, есть ли теоретическая причина для этого?

Некоторые причины, по которым я могу ожидать, что подобные вещи существуют или хотя бы имеют смысл:

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

Этот вопрос вдохновлен пересечением двух предыдущих вопросов:

Языки программирования для эффективных вычислений

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

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Артем Казнатчеев
источник
1
Разве это не тема «Описательная сложность»? у них есть языковые характеристики запросов для различных классов сложности.
Каве
Описательная сложность, безусловно, огромная часть и руководство для языков программирования для эффективных вычислений. Но я не думаю, что это так просто, как сказать «описательная сложность использует логику» и «запросы к базам данных используют логику». В частности, для DC кажется, что размер запроса является фиксированным, а 'n' определяется размерами конечных структур, которые эти запросы принимают. В базах данных это действительно размер запроса, который является переменным, и база данных также является переменной или, возможно, фиксированным параметром.
Артем Казнатчеев
3
Есть также результаты для переменных запросов, но они не так впечатляющи, как соответствие между проверкой моделей и хорошо известными классами сложности. Также более широкое поле теории конечных моделей, частью которого является описательная сложность, имеет ряд результатов выразимости, непосредственно связанных с базами данных. Базы данных - это почти точно конечные теоретико-модельные структуры.
Марк Хаманн
1
Я не думал об этой переписке. Я добавил конечный тег теории моделей. Если вы или @Kaveh хотите уточнить ваши комментарии и знать, как принять конкретные результаты из описательной сложности конечной теории моделей в целом для создания таких языков запросов, то я действительно хотел бы увидеть этот ответ!
Артем Казнатчеев

Ответы:

7

Один из способов взглянуть на языки запросов к базам данных - через призму дедуктивных баз данных , где запросы представлены в виде логических программ. В этом параметре наиболее релевантной работой, связанной с вашим вопросом, является анализ сложности статического анализа McAllester, который показал , что вы можете рассуждать о времени выполнения запроса, рассуждая о количестве «срабатываний префиксов» в правилах вашего программа. Что такое «префиксная стрельба», не очень сложно, но я отсылаю вас к статье для этого.

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

Некоторые более поздние работы над реализацией идей Макаллестера включают « От правил регистрации данных до эффективных программ с гарантиями времени и пространства» (Лю и Столлер) и « Дедалус: журнал данных во времени и пространстве» (Альваро, Марчак, Конвей, Хеллерштейн, Майер и Сирс). Однако я признаю, что еще не читал последнюю из этих двух статей.

Роб Симмонс
источник