«Избежал ли ловушки» Кодд?
К настоящему моменту мы видим, что в [1] , видимо, корректно утверждается, что Tutorial D, будучи вычислительно полным, является неразрешимым. Более того, в этом источнике также утверждается (по крайней мере, неявно), что реляционная алгебра и реляционное исчисление Кодда являются разрешимыми; в действительности, они должны быть таковыми, поскольку исчисление Кодда, по существу, является прикладной формой пропозиционального исчисления, которое разрешимо, а алгебра Кодда логически эквивалентна его исчислению.
Два отступления от темы: Во-первых, реляционное исчисление обычно считают прикладной формой исчисления предикатов, а не исчисления высказываний; однако тот факт, что мы имеем дело с конечными системами, означает, что на самом деле оно является исчислением высказываний, по крайней мере, с логической точки зрения. Во-вторых, исходное исчисление Кодда в действительности было менее выразительным, чем его алгебра (т.е. имелись некоторые алгебраические выражения, для которых отсутствовали эквиваленты в исчислении), но этот недостаток впоследствии был устранен. Большие подробности в этой статье нам не требуются.
Как мы видим, в [1] также утверждается, что Кодд «избегает ловушки» требования вычислительной полноты и за счет этого не сталкивается с проблемой неразрешимости. В [1] ничего не говорится явно о том, как можно избежать этой ловушки, но приводятся намеки на то, что для этого нужно провести четкую границу между частями языка, которые имеют отношение к работе с базой данных и вычислениями:
Мое пожелание состоит в том, чтобы явно разделить в Tutorial D теоретико-множественную семантику и семантику вычислительного языка … Следует переформулировать ОО-предписание 3, чтобы сказать, что подъязык приложений языка D должен быть вычислительно полным и полностью процедурным, а подъязык баз данных языка D должен быть не вычислительно полным, должен быть полностью непроцедурным и должен быть разрешимым (хотя мне не очень понятно, как эти подъязыки могут взаимодействовать) … [Еще одна попытка, позже:] Разделите D на RD (реляционную, непроцедурную часть) и CD (вычислительную, процедурную часть).
Тогда ОО-предписание 3 следует переформулировать так, чтобы сказать, что RD должен быть не вычислительно полным, и в нем не должна обеспечиваться возможность вызова какой-либо операции, которую невозможно реализовать средствами RD … Реляционный язык баз данных RD должен быть разрешимым. Следовательно, он не должен быть вычислительно полным, и в нем не должна поддерживаться возможность вызова какой-либо процедуры, которую в принципе невозможно реализовать средствами RD.
Но следуют ли этим ограничениями предложения языка самого Кодда? Нет! Рассмотрим следующие выдержки из собственных статей Кодда: Из самой первой (1969 г.) статьи про реляционную модель [2]: Пусть подъязык выборки называется R и основной язык – H … R обеспечивает возможность спецификации выборки любого поднабора данных из банка данных … Класс ограничительных выражений, которое могут использоваться в спецификации набора, находится в точно определенном … соответствии с классом правильно построенных формул исчисления предикатов … Любая требуемая арифметическая функция может определяться с использованием языка H и вызываться из конструкций языка R [курсив добавлен].
Из пересмотренного варианта статьи, опубликованного в 1970 г. в Communications of the ACM [3]: Пусть подъязык выборки называется R и основной язык – H … R обеспечивает возможность спецификации выборки любого поднабора данных из банка данных … Класс ограничительных выражений, которое могут использоваться в спецификации набора, должен обладать описательной мощностью класса правильно построенных формул прикладного исчисления предикатов … В условных или других частях операторов выборки могут потребоваться арифметические функции. Такие функции могут определяться на языке H и вызываться из конструкций языка R [курсив добавлен].
И в статье, посвященной подъязыку данных ALPHA [4], говорится следующее: Все вычислительные функции определяются с помощью операторов основного языка; все операции выборки и сохранения – с помощью операторов подъязыка данных.
Однако в операторе подъязыка данных может содержаться вызов функции, определенной с помощью операторов основного языка … Расширяемая библиотека функций, которые могут вызываться из запросов, обеспечивает средства расширения возможностей выборки DSL [Data SubLanguage] ALPHA.
В этой статье далее приводится несколько примеров использования таких функций как в разделе «целевого списка», так и в разделе «условия» запросов. Так что я бы сказал, что во всех трех статьях [2-4] Кодд не только «не избегал ловушки» – очевидно, что он даже и задумывался о наличии ловушки, которую нужно стараться избегать.
Замечание: Комментируя ранний вариант настоящей статьи, автор [1] утверждал, что разделение Коддом языков R и H было достаточным для того, чтобы «избежать ловушки». В частности, он утверждал, что (a) одним из эффектов такого разделения являлось то, что к вызову из языка R функции, определенной средствами языка H, можно было относиться с точки зрения языка R как к константе, и (b) что ловушки удалось избежать, потому что в функциях, определенных на языке H, отсутствовал доступ к переменным, определенным на языке R. После размышлений я пришел к выводу, что не понимаю эти утверждения. В частности, в функциях, используемых Коддом в примерах в [4], очень часто производится доступ к переменным, «определенным на языке R», – в число этих функций входят аналоги всем знакомых агрегатных операций COUNT, SUM, AVG, MAX и MIN, которые, конечно, явно определяются для работы с отношениями. (Если речь идет о том, что эти функции могут только читать свои операнды и не могут изменять их, то это верно и для Tutorial D, так что, по-видимому, имеется в виду не это.)
Отклоняясь от темы, я хотел бы добавить, что по причинам, которые мне не хотелось бы здесь объяснять, я никогда не относился к числу поклонников идеи подъязыка данных (частично по этой причине появилось ОО-предписание 3 Манифеста). Как я писал в [7], Я никогда не был убежден в том, что выделение доступа к данным в отдельный «подъязык» является хорошей идеей, [хотя] она присутствует в нашей практике в течение довольно долгого времени в форме встраиваемого SQL.Кстати, в связи с этим интересно заметить, что после добавления в стандарт SQL в 1996 г. механизма PSM («Persistent Stored Modules») сам SQL стал теперь вычислительно полным языком – что означает отсутствие дальнейшей потребности в основном языке (при использовании SQL).
