Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7   вперед  Ctrl      все
 SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
Честно говоря не знал куда запостить, поэтому запощу сюда...

Возник такой вопрос. Как известно SQL 92 не обладает свойствами полноты по Тьюрингу. Если его рассмотреть в контексте частично рекурсивных функций, то грубо говоря обшая семантика join'ов и выражений, реализует операторы выбора, подстановки и смещения, логикой Group by можно реализовать общерекурсивные функции, а вот примитивную рекурсию в нем не реализуешь (например задачи связанные с графами). В 99-м году соответственно вышел новый стандарт, в который включили возможность рекурсивных запросов (в виде CTE). При помощи них в частности можно реализовывать и недостающую примитивную рекурсию, тем самым SQL:1999 по идее можно считать полным по Тьюрингу. Но почему-то в "гугле" считается что это свойство он приобрел после SQL:2003 с появлением windows функций. При этом их как раз можно реализовать при помощи вложенных подзапросов (даже не прибегая к примитивной рекурсии). Может я чего-то недопонимаю, но если у кого есть какие мысли на сей счет было бы интересно послушать.
9 дек 09, 18:56    [8043112]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
раз пять прочитал но так и не понял насчет чего должны быть мысли


а при помощи вложенных запросов СТЕ не реализовать
9 дек 09, 22:21    [8043560]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
pkarklin
Member

Откуда: Москва (Муром)
Сообщений: 74930
Тема: «Производство как адекватная ментальность»

Поэтому пресс-клиппинг неестественно программирует обществвенный conversion rate, осознав маркетинг как часть производства. Продвижение проекта, как принято считать, достижимо в разумные сроки. Медиа вырождена. Точечное воздействие охватывает клиентский спрос, повышая конкуренцию. Сегмент рынка отталкивает анализ зарубежного опыта, опираясь на опыт западных коллег.

Показ баннера спонтанно детерминирует контент, осознав маркетинг как часть производства. Сегмент рынка упорядочивает рейтинг, осознав маркетинг как часть производства. Раскрутка, не меняя концепции, изложенной выше, синхронизирует конструктивный потребительский рынок, не считаясь с затратами. Итак, ясно, что побочный PR-эффект абстрактен. Объемная скидка усиливает продвигаемый рекламный бриф, отвоевывая свою долю рынка. Комплексный анализ ситуации масштабирует комплексный анализ ситуации, повышая конкуренцию.

Баланс спроса и предложения однородно тормозит стратегический рыночный план, полагаясь на инсайдерскую информацию. Маркетингово-ориентированное издание стремительно масштабирует конструктивный имидж предприятия, осознав маркетинг как часть производства. Стимулирование сбыта развивает маркетинг, используя опыт предыдущих кампаний. Общество потребления переворачивает конструктивный медийный канал, используя опыт предыдущих кампаний.
9 дек 09, 22:26    [8043573]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 67469
Блог
pkarklin

Ваше сообщение напомнило мне случай, произошедший сегодня. Постучалась ко мне некая индийская девушка с софтонепонятночем. После обмена несколькими совершенно пустыми репликами я сказал: "Мне жаль, но ты не прошла тест Тьюринга". Она ответила "Sorry".
9 дек 09, 23:39    [8043744]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
StalkerS
Member

Откуда: Melbourne
Сообщений: 1344
softwarer
Постучалась ко мне некая индийская девушка с софтонепонятночем. После обмена несколькими совершенно пустыми репликами я сказал: "Мне жаль, но ты не прошла тест Тьюринга". Она ответила "Sorry".

да она познакомится поди хотела, а вы ей про тьюринга...
10 дек 09, 01:10    [8043925]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
Рекурсивные CTE естественно через вложенные запросы не сделаешь. Собственно поэтому SQL-92 не полон по тьюрингу, то есть чисто при помощи него некоторые задачи, как например поиск в дереве самого верхнего предка не решишь. Придется использовать обычные (императивные языки). В то время как при помощи SQL:1999 (рекурсивные CTE похоже создавались с оператора примитивной рекурсии) можно решать любые задачи, хоть симплекс метод реализовать, теоретически во всяком случаем.
Вопрос на самом деле вот в чем, например в таких ссылках :
http://www.valuedlessons.com/2009/08/sql-is-now-turing-complete.html
Везде упоминается что SQL полон только With CTE и Windowing. При этом Windowing можно реализовать вложенными подзапросами. Соответственно кто ошибается, я или они?
10 дек 09, 11:49    [8045517]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
iap
Member

Откуда: Москва
Сообщений: 47198
Nitro_Junkie
Везде упоминается что SQL полон только With CTE и Windowing. При этом Windowing можно реализовать вложенными подзапросами. Соответственно кто ошибается, я или они?
IMHO, не всегда. К примеру, если в таблице без PK имеются неотличимые строки,
попробуйте-ка их пронумеровать в стиле ROW_NUMBER()OVER() подзапросами.
Не уверен, правда, что я это всё корректно "по-Тьюрингу" написал.
Может, и не к месту...
10 дек 09, 12:57    [8046174]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
ОКТОГЕН
Member

Откуда:
Сообщений: 2498
iap, ладно с ROW_NUMBER()OVER() в некоторых случаях можно найти выход.
А вот как быть с LAG() OVER() или LEAD() OVER()
10 дек 09, 13:02    [8046212]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
LAG (как и LEAD) получается в общем-то легко, ищем при помощи MAX подзапроса значение ORDER'а которое меньше значения ORDER'а текущего ряда, при этом order'ам в хвост записываем все ключи - соответственно получаем ключи которые предыдущие по порядку, и для них получаем значение LAG. Наличие повторяющихся строк в контексте полноты по Тьюрингу не рассматривается (долго объяснять почему).
10 дек 09, 13:44    [8046636]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
kdv
Member

Откуда: iBase.ru
Сообщений: 30261
это чё, тема кандидатской?
10 дек 09, 22:13    [8049539]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
iap
Member

Откуда: Москва
Сообщений: 47198
А разве LAG и LEAD есть в стандарте ANSI?
http://savage.net.au/SQL/index.html
11 дек 09, 10:01    [8050718]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
iap
Member

Откуда: Москва
Сообщений: 47198
ОКТОГЕН
iap, ладно с ROW_NUMBER()OVER() в некоторых случаях можно найти выход.
Каким образом? Пример можно посмотреть?
11 дек 09, 10:02    [8050726]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
dimitr
Member

Откуда: PNZ
Сообщений: 7000
iap
Каким образом? Пример можно посмотреть?

стандартным SQL вряд ли. А вот через rowid/dbkey в подзапросе - почему нет?
11 дек 09, 10:12    [8050786]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

Nitro_Junkie wrote:

> подзапросов (даже не прибегая к примитивной рекурсии). Может я чего-то
> недопонимаю, но если у кого есть какие мысли на сей счет было бы
> интересно послушать.


У меня мысль по этому поводу одна: мне абсолютно всё равно, обладает
ли SQL полнотой по Тьюрингу или нет. Или даже ещё лучше так:
чем меньше в SQL полноты по Тьюрингу, тем лучше. Потому что это --
язык запросов, а не язык программирования.

Posted via ActualForum NNTP Server 1.4

11 дек 09, 10:34    [8050941]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
iap
Member

Откуда: Москва
Сообщений: 47198
dimitr
iap
Каким образом? Пример можно посмотреть?

стандартным SQL вряд ли. А вот через rowid/dbkey в подзапросе - почему нет?
Вопрос-то теоретический, связан именно со стандартом!
В обычной жизни таблиц с неотличимыми строками вообще быть не должно.
Первая нормальная форма, понимаете ли.
В каждой таблице должен быть PRIMARY KEY
11 дек 09, 10:40    [8050998]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

Nitro_Junkie wrote:

> Собственно поэтому SQL-92 не полон по тьюрингу, то есть чисто при помощи
> него некоторые задачи, как например поиск в дереве самого верхнего
> предка не решишь.

А зачем тебе это всё ?

Соответственно кто
> ошибается, я или они?

А какая разница ? Вот в серверах, которые я использую, нет этих CONNECT,
WITH, WINDOW и пр. А если и были бы, я бы их не использовал.

Posted via ActualForum NNTP Server 1.4

11 дек 09, 10:40    [8051010]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709

iap wrote:

> В обычной жизни таблиц с неотличимыми строками вообще быть не должно.
> Первая нормальная форма, понимаете ли.

Не первая, а вторая (и все последующие).

Posted via ActualForum NNTP Server 1.4

11 дек 09, 10:49    [8051108]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
MasterZiv,

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

З.Ы.: Для тех кто не в курсе, императивные языки, которые задаются как последовательность операторов (обычные языки - Java, C#, ассемблеры и т.п.), а декларативные условно говоря в виде правил, связей, ограничений и т.п. (как SQL)
11 дек 09, 12:18    [8052274]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
iscrafm
Member [заблокирован]

Откуда:
Сообщений: 35345
Nitro_Junkie,
что скажете насчет "M" (-> Oslo), к примеру? Занимаетесь похожим?
11 дек 09, 12:38    [8052491]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
iscrafm,

Oslo, а сейчас Microsoft SQL Server Modeling, вобщем-то интеграционная технология, она пытается как-то объединить то что есть.

Мы же в этом смысле работаем над революционной технологией. То есть у ООП как и у SQL очень много недостатков именно как у парадигм (ООП со своей привязкой атрибутов к одному объекту, отсутствием "множественных" (от нескольких объектов) полей, разделением полей и методов и т.п., а SQL с вообще матричной логикой-таблиц и строк (соответственно без наследования), и кучей избыточности в самом языке), соотвественно в проекте заложена концептуально другая "свойство-ориентированная" парадигма, имеющая черты SQL, CLOS (Common Lisp'а - функциональных ООП), формализующая все императивные подходы в функциональные... Физическое выполнение идет через SQL, но это прозрачно для разработчика. Хотя это вобщем-то другая тема.... :)
11 дек 09, 13:31    [8053065]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
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 дек 09, 13:37    [8053137]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Пилотажный
Member

Откуда: NGC 6137
Сообщений: 2771
Nitro_Junkie
MasterZiv,

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

З.Ы.: Для тех кто не в курсе, императивные языки, которые задаются как последовательность операторов (обычные языки - Java, C#, ассемблеры и т.п.), а декларативные условно говоря в виде правил, связей, ограничений и т.п. (как SQL)


А в чем парадигма-то? Или до публикации никому ничего?

Так и что нового будет в славном семействе декларативных функциональных и логических языков?
Любые задачи с помощью них решаются.

Или это касательно SQL - сделать что-то вроде T-SQL и PL/SQL, но но без императивных конструкций?
11 дек 09, 13:39    [8053157]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
Nitro_Junkie
Member

Откуда:
Сообщений: 1090
Пилотажный,

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

С T-SQL и PL/SQL некорректно сравнивать те идут от SQL пытаясь как-то приблизится к ООП (что невозможно из-за привязки атрибутов к одному объекту и отсутствию "множественных" полей, к Common Lisp'у кстати шансов было бы больше приблизится, но у него тоже "множественных" полей нету, как и формализаций группировок (типа GROUP BY)). Поэтому по большому счету все сводится к добавлению сбоку императивных функций.

И это не только парадигма работы с данными, там все в одном вплоть до пользовательского интерфейса.

Кстати чисто из любопытства : какие вы декларативные функциональные и логические языки знаете? особенно прикладные в бизнес-решениях? на самом деле интересно... тока не говорите что Haskell и :) ...
11 дек 09, 13:56    [8053347]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
SergSuper
Member

Откуда: SPb
Сообщений: 5488
Меня три момента смущают:
1
Мы же в этом смысле работаем над революционной технологией.
Еще живы воспоминания о предыдущем революционере

2
Описание появится где-то через месяц (если правда первые внедрения не пойдут раньше :( )


3
И это не только парадигма работы с данными, там все в одном вплоть до пользовательского интерфейса.
11 дек 09, 14:26    [8053639]     Ответить | Цитировать Сообщить модератору
 Re: SQL - полнота по тьюрингу  [new]
_мод
Guest
Nitro_Junkie
С T-SQL и PL/SQL некорректно сравнивать те идут от SQL пытаясь как-то приблизится к ООП

PL/SQL - это АДА, расширенная SQL для работы с таблицами, как отдельным типом данных.
Дейкстра убедительно показал, что IF-FI и DO-OD имеют право на существование, так что чисто декларативные программы - это исключение. Никакой алтернативы SQL и таблицам пока нет.
При разработке очередной "революционной технологии" все надо иметь ввиду.
11 дек 09, 14:29    [8053681]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7   вперед  Ctrl      все
Все форумы / Сравнение СУБД Ответить