По словам Иммермана , класс сложности, связанный с запросами SQL, - это в точности класс безопасных запросов в (запросы первого порядка плюс оператор подсчета): SQL захватывает безопасные запросы. (Другими словами, все запросы SQL имеют сложность в , и все проблемы в могут быть выражены как запрос SQL.)
Исходя из этого результата, с теоретической точки зрения, существует много интересных проблем, которые могут быть эффективно решены, но не выражены в SQL. Поэтому расширение SQL, которое все еще эффективно, кажется интересным. Вот мой вопрос:
Существует ли расширение SQL (внедренное и используемое в отрасли ), которое захватывает (т. Е. Может выражать все вычисляемые запросы за полиномиальное время и никаких других)?
Мне нужен язык запросов к базе данных, который удовлетворяет всем трем условиям. Легко определить расширение, которое расширило бы SQL и захватило бы . Но мои вопросы, если такой язык имеет смысл с практической точки зрения, поэтому я хочу язык, который используется на практике. Если это не так и такого языка нет, то я хотел бы знать, есть ли причина, которая делает такой язык неинтересным с практической точки зрения? Например, являются ли часто возникающие на практике запросы достаточно простыми, чтобы в таком языке не было необходимости?
Ответы:
Что касается вашего основного вопроса, я рекомендую этот короткий опрос Мартина Гроэ.
Я бы сказал, что это сохраняется в большинстве случаев, учитывая достаточное количество расширений, добавленных к распространенным языкам запросов (транзитивное замыкание, арифметические операторы, подсчет и т. Д.). Это происходит с точки зрения кого-то, кто проделал некоторую работу в качестве внештатного разработчика относительно простых веб-сайтов и других приложений, поэтому я не уверен насчет реального использования SQL в больших отраслях промышленности / больших базах данных.
В редких случаях может потребоваться более мощный язык, я предполагаю, что разработчики программного обеспечения справляются с ними, используя язык, на котором они пишут приложение, а не запросы (например, C ++ или java).
источник
Во-первых, выразительная сила SQL менее очевидна, чем кажется. Агрегирующие, групповые и арифметические особенности SQL оказываются весьма неуловимыми. Априори кажется возможным, что при некотором кодировании алгебраических операторов, использующих эти функции, можно фактически выразить достижимость в SQL. Оказывается, это не совсем так для SQL-92 , который является «локальным».
Это означает, что для SQL-92 требуется расширение для захвата PTIME, и такое, которое позволяет результирующему языку быть «нелокальным».
Однако разрешение упорядоченных структур и реалистично ограниченной арифметики доказывает, что SQL-92 не может выразить достижимость, будет означать, что равномерное и, следовательно, вероятно, будет довольно трудным. (Можно утверждать, что в типах данных в SQL-92 всегда существует естественное линейное упорядочение, и поэтому можно предположить, что базовые структуры упорядочены.)TC0⊊NLOGSPACE
Затем ландшафт снова изменился, поскольку SQL: 1999 (SQL3) включал рекурсию. Таким образом, SQL: 1999 кажется, по крайней мере, столь же выразительным, как и логика с фиксированной запятой при подсчете (хотя я думаю, что детали могут снова быть довольно сложными, включая проблему порядка). Сделали ли новые конструкции логику более выразительной, чем требуется для захвата PTIME, я не знаю, и для установления этого потребуются некоторые исследования. Тем временем дальнейшие изменения были внесены в 2003 , 2006 , 2008 и 2011 годах.(будучи документами ISO, только проекты доступны бесплатно). Эти изменения добавили множество новых функций, в том числе XQuery как «часть» SQL-запросов. Я предполагаю, что «SQL» теперь более выразителен, чем требуется для захвата PTIME, но для этого требуется кодирование, которое может потребовать больших и довольно неестественных запросов, которые могут не поддерживаться в реальных системах.
Так что я думаю, что есть доказательства того, что нет промышленного расширения SQL, которое бы точно захватывало PTIME , отвечая на ваш вопрос нечетко. Короче говоря, промышленные расширения довольно мощные и могут уже иметь перегруженный PTIME. Если это правда, что SQL: 1999 уже достаточно мощный, чтобы захватить хотя бы PTIME, то также неясно, что на самом деле означает «SQL» в вашем вопросе, поскольку нужно было бы определить «SQL» для обозначения версии, предшествующей SQL: 1999.
Наконец, опрос Гроэ о поиске логики захвата PTIME (также упоминаемой Яномой) показывает, что захват PTIME не только сложен, если у нас нет линейного порядка в качестве части языка, но и доказательство того, что такой логики не может быть, также подразумевать .P≠NP
источник
Хотя он, вероятно, не существует для реальных целей, он, безусловно, существует, и его можно реализовать и реализовать. Вы можете определить этот язык с помощью чего-то, способного моделировать машину Тьюринга с заданным одинарным числом шагов. IE, способный решить P-полную задачу. Однако, если вы создаете такую вещь, она почти завершена по Тьюрингу, за исключением ограничения «задано одинарное число шагов», которое на языке, подобном SQL, было бы очень странным способом ограничить его только безопасными запросами. Вы могли бы сделать это, если шаги являются записями некоторой таблицы, но это не выглядит ничего ценного для практических целей.
источник