|
|
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Честно говоря не знал куда запостить, поэтому запощу сюда... Возник такой вопрос. Как известно SQL 92 не обладает свойствами полноты по Тьюрингу. Если его рассмотреть в контексте частично рекурсивных функций, то грубо говоря обшая семантика join'ов и выражений, реализует операторы выбора, подстановки и смещения, логикой Group by можно реализовать общерекурсивные функции, а вот примитивную рекурсию в нем не реализуешь (например задачи связанные с графами). В 99-м году соответственно вышел новый стандарт, в который включили возможность рекурсивных запросов (в виде CTE). При помощи них в частности можно реализовывать и недостающую примитивную рекурсию, тем самым SQL:1999 по идее можно считать полным по Тьюрингу. Но почему-то в "гугле" считается что это свойство он приобрел после SQL:2003 с появлением windows функций. При этом их как раз можно реализовать при помощи вложенных подзапросов (даже не прибегая к примитивной рекурсии). Может я чего-то недопонимаю, но если у кого есть какие мысли на сей счет было бы интересно послушать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2009, 18:56 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
раз пять прочитал но так и не понял насчет чего должны быть мысли а при помощи вложенных запросов СТЕ не реализовать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2009, 22:21 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Тема: «Производство как адекватная ментальность» Поэтому пресс-клиппинг неестественно программирует обществвенный conversion rate, осознав маркетинг как часть производства. Продвижение проекта, как принято считать, достижимо в разумные сроки. Медиа вырождена. Точечное воздействие охватывает клиентский спрос, повышая конкуренцию. Сегмент рынка отталкивает анализ зарубежного опыта, опираясь на опыт западных коллег. Показ баннера спонтанно детерминирует контент, осознав маркетинг как часть производства. Сегмент рынка упорядочивает рейтинг, осознав маркетинг как часть производства. Раскрутка, не меняя концепции, изложенной выше, синхронизирует конструктивный потребительский рынок, не считаясь с затратами. Итак, ясно, что побочный PR-эффект абстрактен. Объемная скидка усиливает продвигаемый рекламный бриф, отвоевывая свою долю рынка. Комплексный анализ ситуации масштабирует комплексный анализ ситуации, повышая конкуренцию. Баланс спроса и предложения однородно тормозит стратегический рыночный план, полагаясь на инсайдерскую информацию. Маркетингово-ориентированное издание стремительно масштабирует конструктивный имидж предприятия, осознав маркетинг как часть производства. Стимулирование сбыта развивает маркетинг, используя опыт предыдущих кампаний. Общество потребления переворачивает конструктивный медийный канал, используя опыт предыдущих кампаний. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2009, 22:26 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
pkarklin Ваше сообщение напомнило мне случай, произошедший сегодня. Постучалась ко мне некая индийская девушка с софтонепонятночем. После обмена несколькими совершенно пустыми репликами я сказал: "Мне жаль, но ты не прошла тест Тьюринга". Она ответила "Sorry". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.12.2009, 23:39 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
softwarer Постучалась ко мне некая индийская девушка с софтонепонятночем. После обмена несколькими совершенно пустыми репликами я сказал: "Мне жаль, но ты не прошла тест Тьюринга". Она ответила "Sorry". да она познакомится поди хотела, а вы ей про тьюринга... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2009, 01:10 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Рекурсивные CTE естественно через вложенные запросы не сделаешь. Собственно поэтому SQL-92 не полон по тьюрингу, то есть чисто при помощи него некоторые задачи, как например поиск в дереве самого верхнего предка не решишь. Придется использовать обычные (императивные языки). В то время как при помощи SQL:1999 (рекурсивные CTE похоже создавались с оператора примитивной рекурсии) можно решать любые задачи, хоть симплекс метод реализовать, теоретически во всяком случаем. Вопрос на самом деле вот в чем, например в таких ссылках : http://www.valuedlessons.com/2009/08/sql-is-now-turing-complete.html Везде упоминается что SQL полон только With CTE и Windowing. При этом Windowing можно реализовать вложенными подзапросами. Соответственно кто ошибается, я или они? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2009, 11:49 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Nitro_JunkieВезде упоминается что SQL полон только With CTE и Windowing. При этом Windowing можно реализовать вложенными подзапросами . Соответственно кто ошибается, я или они?IMHO, не всегда. К примеру, если в таблице без PK имеются неотличимые строки, попробуйте-ка их пронумеровать в стиле ROW_NUMBER()OVER() подзапросами. Не уверен, правда, что я это всё корректно "по-Тьюрингу" написал. Может, и не к месту... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2009, 12:57 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
iap, ладно с ROW_NUMBER()OVER() в некоторых случаях можно найти выход. А вот как быть с LAG() OVER() или LEAD() OVER() ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2009, 13:02 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
LAG (как и LEAD) получается в общем-то легко, ищем при помощи MAX подзапроса значение ORDER'а которое меньше значения ORDER'а текущего ряда, при этом order'ам в хвост записываем все ключи - соответственно получаем ключи которые предыдущие по порядку, и для них получаем значение LAG. Наличие повторяющихся строк в контексте полноты по Тьюрингу не рассматривается (долго объяснять почему). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2009, 13:44 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
это чё, тема кандидатской? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.12.2009, 22:13 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
А разве LAG и LEAD есть в стандарте ANSI? http://savage.net.au/SQL/index.html ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:01 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
ОКТОГЕНiap, ладно с ROW_NUMBER()OVER() в некоторых случаях можно найти выход.Каким образом? Пример можно посмотреть? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:02 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
iapКаким образом? Пример можно посмотреть? стандартным SQL вряд ли. А вот через rowid/dbkey в подзапросе - почему нет? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:12 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Nitro_Junkie wrote: > подзапросов (даже не прибегая к примитивной рекурсии). Может я чего-то > недопонимаю, но если у кого есть какие мысли на сей счет было бы > интересно послушать. У меня мысль по этому поводу одна: мне абсолютно всё равно, обладает ли SQL полнотой по Тьюрингу или нет. Или даже ещё лучше так: чем меньше в SQL полноты по Тьюрингу, тем лучше. Потому что это -- язык запросов, а не язык программирования. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:34 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
dimitriapКаким образом? Пример можно посмотреть? стандартным SQL вряд ли. А вот через rowid/dbkey в подзапросе - почему нет?Вопрос-то теоретический, связан именно со стандартом! В обычной жизни таблиц с неотличимыми строками вообще быть не должно. Первая нормальная форма, понимаете ли. В каждой таблице должен быть PRIMARY KEY ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:40 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Nitro_Junkie wrote: > Собственно поэтому SQL-92 не полон по тьюрингу, то есть чисто при помощи > него некоторые задачи, как например поиск в дереве самого верхнего > предка не решишь. А зачем тебе это всё ? Соответственно кто > ошибается, я или они? А какая разница ? Вот в серверах, которые я использую, нет этих CONNECT, WITH, WINDOW и пр. А если и были бы, я бы их не использовал. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:40 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
iap wrote: > В обычной жизни таблиц с неотличимыми строками вообще быть не должно. > Первая нормальная форма, понимаете ли. Не первая, а вторая (и все последующие). Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 10:49 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
MasterZiv, Сейчас просто учавствую в работе над проектом платформы чисто декларативной разработки приложений (или даже не платформы а вообще парадигмы программирования). И общая идея нужно обоснование того, что любую задачу можно решить при помощи ее (естественно есть точки входа для императивных языков, но цель максимально минимизировать их учавствие, вплоть до нуля). Во многом она перекликается с SQL, (как единственного чисто декларативного языка), во всяком случае реализуется на нем, и ее полнота отчасти эквивалентна полноте SQL, отсюда и возник вопрос... З.Ы.: Для тех кто не в курсе, императивные языки, которые задаются как последовательность операторов (обычные языки - Java, C#, ассемблеры и т.п.), а декларативные условно говоря в виде правил, связей, ограничений и т.п. (как SQL) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 12:18 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Nitro_Junkie, что скажете насчет "M" (-> Oslo), к примеру? Занимаетесь похожим? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 12:38 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
iscrafm, Oslo, а сейчас Microsoft SQL Server Modeling, вобщем-то интеграционная технология, она пытается как-то объединить то что есть. Мы же в этом смысле работаем над революционной технологией. То есть у ООП как и у SQL очень много недостатков именно как у парадигм (ООП со своей привязкой атрибутов к одному объекту, отсутствием "множественных" (от нескольких объектов) полей, разделением полей и методов и т.п., а SQL с вообще матричной логикой-таблиц и строк (соответственно без наследования), и кучей избыточности в самом языке), соотвественно в проекте заложена концептуально другая "свойство-ориентированная" парадигма, имеющая черты SQL, CLOS (Common Lisp'а - функциональных ООП), формализующая все императивные подходы в функциональные... Физическое выполнение идет через SQL, но это прозрачно для разработчика. Хотя это вобщем-то другая тема.... :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 13:31 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
SELECT a.key,COUNT(*) FROM A a JOIN A b WHERE b.order<a.order OR (b.order=a.order AND b.key<a.key) GROUP BY a.key если известно что key уникально - по сути ROW_NUMBER() OVER(ORDER BY order).... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 13:37 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Nitro_JunkieMasterZiv, Сейчас просто учавствую в работе над проектом платформы чисто декларативной разработки приложений (или даже не платформы а вообще парадигмы программирования). И общая идея нужно обоснование того, что любую задачу можно решить при помощи ее (естественно есть точки входа для императивных языков, но цель максимально минимизировать их учавствие, вплоть до нуля). Во многом она перекликается с SQL, (как единственного чисто декларативного языка), во всяком случае реализуется на нем, и ее полнота отчасти эквивалентна полноте SQL, отсюда и возник вопрос... З.Ы.: Для тех кто не в курсе, императивные языки, которые задаются как последовательность операторов (обычные языки - Java, C#, ассемблеры и т.п.), а декларативные условно говоря в виде правил, связей, ограничений и т.п. (как SQL) А в чем парадигма-то? Или до публикации никому ничего? Так и что нового будет в славном семействе декларативных функциональных и логических языков? Любые задачи с помощью них решаются. Или это касательно SQL - сделать что-то вроде T-SQL и PL/SQL, но но без императивных конструкций? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 13:39 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Пилотажный, Описание появится где-то через месяц (если правда первые внедрения не пойдут раньше :( ), в двух словах тяжело объяснить, (все равно как если тоже самое для SQL делать, если вы про него ни разу не слышали). С T-SQL и PL/SQL некорректно сравнивать те идут от SQL пытаясь как-то приблизится к ООП (что невозможно из-за привязки атрибутов к одному объекту и отсутствию "множественных" полей, к Common Lisp'у кстати шансов было бы больше приблизится, но у него тоже "множественных" полей нету, как и формализаций группировок (типа GROUP BY)). Поэтому по большому счету все сводится к добавлению сбоку императивных функций. И это не только парадигма работы с данными, там все в одном вплоть до пользовательского интерфейса. Кстати чисто из любопытства : какие вы декларативные функциональные и логические языки знаете? особенно прикладные в бизнес-решениях? на самом деле интересно... тока не говорите что Haskell и :) ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 13:56 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Меня три момента смущают: 1Мы же в этом смысле работаем над революционной технологией.Еще живы воспоминания о предыдущем революционере 2Описание появится где-то через месяц (если правда первые внедрения не пойдут раньше :( ) 3И это не только парадигма работы с данными, там все в одном вплоть до пользовательского интерфейса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 14:26 |
|
||
|
SQL - полнота по тьюрингу
|
|||
|---|---|---|---|
|
#18+
Nitro_JunkieС T-SQL и PL/SQL некорректно сравнивать те идут от SQL пытаясь как-то приблизится к ООП PL/SQL - это АДА, расширенная SQL для работы с таблицами, как отдельным типом данных. Дейкстра убедительно показал, что IF-FI и DO-OD имеют право на существование, так что чисто декларативные программы - это исключение. Никакой алтернативы SQL и таблицам пока нет. При разработке очередной "революционной технологии" все надо иметь ввиду. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.12.2009, 14:29 |
|
||
|
|
start [/forum/topic.php?fid=35&fpage=18&tid=1552855]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
38ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
130ms |
get tp. blocked users: |
2ms |
| others: | 13ms |
| total: | 223ms |
| 0 / 0 |
