Аннотация

Эта статья является ответом на некоторые критические замечания, которые были сделаны в адрес (a) Третьего Манифеста – см. [4] – и (b) языка Tutorial D, который используется в [4] для иллюстрации идей Третьего Манифеста. Эти критические замечания появились в [6] и могут быть кратко изложены следующим образом: В Третьем Манифесте вообще и в Tutorial D, в частности, допускается построение выражений, которые являются парадоксальными и потому неразрешимыми.

• Парадокс Эпименида
• Обсуждение
• Замечания по поводу Tutorial D
• Замечание по поводу Третьего Манифеста
• Литература

Парадокс Эпименида

Рассмотрим следующий пример:

• Пусть P – это предикат «Отсутствует истинная инстанциация предиката P». Предположим, что P является допустимым предикатом (я проанализирую это предположение в следующем разделе); тогда в действительности это не только предикат, но и высказывание, поскольку в нем отсутствуют параметры.
• Пусть r – это отношение, соответствующее P (т.е. отношение, в теле которого содержаться те и только те кортежи, которые представляют истинные инстанциации P). Поскольку у P отсутствуют параметры, у r отсутствуют атрибуты (т.е. это отношение степени ноль), и, следовательно, оно должно быть либо TABLE_DEE, либо TABLE_DUM. Напомню, что TABLE_DEE – это единственное отношение без атрибутов и с ровно одним кортежем (0-кортежем), а TABLE_DUM – это единственное отношение без атрибутов и без кортежей [5].
• Предположим, что r – это TABLE_DEE. Тогда интерпретация (наличие в r единственного кортежа) состоит в том, что P является истинным – что, по определению, означает отсутствие истинных инстанциаций P, и, следовательно, r не должно содержать никаких кортежей (т.е. должно быть TABLE_DUM).
• Наоборот, предположим, что r – это TABLE_ DUM. Тогда интерпретация (того факта, что в r нет ни одного кортежа) состоит в том, что P является ложным – что, по определению, означает наличие хотя бы одной (на самом деле, ровно одной) истинной инстанциации P, и, следовательно, r должно содержать хотя бы один (на самом деле, ровно один) кортеж (т.е. должно быть TABLE_ DEE).

Вероятно, вы уже поняли, что этот пример воспроизводит в реляционной форме известный парадокс Эпименида. И конечно, корнем проблемы является ссылка на самого себя: предикат P ссылается сам на себя.

---

На тот случай, если вам неудобно полагаться на аргументы, основанные на специальных отношениях TABLE_DEE и TABLE_DUM, позвольте привести другой пример, иллюстрирующий тот же случай. Этот пример представляет собой существенно упрощенный вариант примера, приведенного Дэвидом Макговерном (David McGoveran) и опубликованного мной в колонке журнала DBP&D [2]. Пусть r – это отношение с единственным атрибутом N типа INTEGER, и пусть предикатом для r является «Мощность r есть N»^♦. Если r пусто, то мощность r равна нулю, и, следовательно, в r должен входить кортеж t = TUPLE {N 0}, и поэтому r не должно быть пусто. Но если кортеж t = TUPLE {N 0} действительно входит в r, то r не является пустым, и, следовательно, кортеж t не должен входить в r. То есть снова имеется некоторая разновидность того же парадокса.

Обсуждение

В оставшейся части статьи я возвращаюсь к примеру с участием TABLE_DEE и TABLE_DUM. В связи с этим примером я говорил, что P является предикатом, а на самом деле еще и высказыванием – но так ли это в действительности? По определению, высказывание – это утверждение, которое однозначно является либо истинным, либо ложным. (Более точно, это утверждение, в котором делается предположение, однозначно являющееся истинным или ложным.) Но очевидно, что P не является ни истинным, ни ложным – потому что, если оно истинно, то оно ложно, и наоборот, – так что, возможно, я был не прав, назвав его в предыдущем разделе высказыванием.

Однако более важно то, что, как мне кажется, нам не следует спорить о том, является ли P предикатом, или, более конкретно, высказыванием; нам нужно решить, трактуется ли он в таком качестве в нашей формальной системе – системе, о которой идет речь. Если такая трактовка допускается, мы имеем проблему. Однако заметим следующее:

• Эта проблема не является проблемой конкретно языка Tutorial D; на самом деле, я не вижу, каким образом она могла бы быть проблемой этого языка, поскольку в своем примере я вообще не обращался к Tutorial D.
• Эта проблема не является и проблемой конкретно Третьего Манифеста, поскольку в своем примере я вообще не обращался и к Третьему Манифесту; я пользовался всего лишь тем общеизвестным фактом, что для каждого предиката имеется соответствующее отношение – а именно, то отношение, тело которого содержит те и только те кортежи, которые представляют истинную инстанциацию данного предиката.
• Эта проблема не является и проблемой конкретно реляционной модели, по существу, по той же причине.
• Эта проблема не происходит и из того факта, что в Третьем Манифесте требуется (неявно) вычислительная полнота Tutorial D. Я упоминаю этот аспект потому, что именно это является основным источником критики: то, что требование вычислительной полноты «приводит к созданию языка, логические выражения которого … являются, возможно, неразрешимыми» [6]. Замечу, что я не говорю, что это критическое замечание является некорректным; я всего лишь указываю, что отсутствие разрешимости в обсуждаемом примере (разрешимости того, входит ли кортеж в отношение или нет), по моему мнению, не имеет никакого отношения к вычислительной полноте Tutorial D.

Скорее, проблема (если здесь вообще имеется проблема) связана с логикой. Другими словами, либо в логике допускается P в качестве предиката, либо не допускается. Если допускается, то имеется проблема, связанная с логикой. Если не допускается, то нет проблемы в связи с логикой, а проблемы (если они имеются) связаны с реляционной моделью. С большим основанием Третий Манифест и Tutorial D здесь вообще не при чем.

Замечание: Насколько я понимаю, Рассел в своей теории типов был вынужден принять недопустимость P и других подобных утверждений в качестве предикатов. Однако, даже если согласиться с этим, мое утверждение остается неизменным: если в этой области и существует проблема, она является внутренней проблемой – она не связана с какой-либо ошибкой в Третьем Манифесте или Tutorial D.

Замечания по поводу Tutorial D

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

VAR R { } KEY { } ;

CONSTRAINT EPIMENIDES COUNT ( R ) = 0 ;

Более конкретно, можно было бы подумать, что ограничение EPIMENIDES является формальным выражением предиката P («Отсутствуют истинные инстанциации предиката P», или, эквивалентно, «Число истинных инстанциаций предиката P равняется нулю»). Но это не так. И причина состоит не в том, что к ограничениям не применима гипотеза о замкнутом мире. В гипотезе о замкнутости мира (говоря вольно) утверждается, что relvar R в данный момент времени должна содержать те и только те кортежи, которые в этот момент удовлетворяют предикату переменной R. Но в Tutorial D не поддерживается и не может поддерживаться знание предикатов relvar; в этом языке могут быть известны только ограничения relvar. И нет – и не может быть – такого требования, что relvar R в данный момент времени содержит те и только те кортежи, которые удовлетворяют в этот момент ограничениям, применимым к R. Так что тот факт (в примере), что relvar R всегда является пустой, сам по себе не приводит ни к какому парадоксу.

Попробуем подойти по-другому. Вот еще одна попытка сформулировать парадокс Эпименида в терминах Tutorial D:

VAR R { } KEY { } ;

CONSTRAINT EPIMENIDES

IF COUNT ( R ) = 1 THEN COUNT ( R ) = 0 AND

IF COUNT ( R ) = 0 THEN COUNT ( R ) = 1 ;

Здесь ограничение EPIMENIDES логически эквивалентно следующему:

Если в relvar R существует кортеж, то relvar R должна быть пустой, а если relvar R является пустой, то в ней должен существовать кортеж.

Другими словами, это ограничение является противоречием. (Заметьте, пожалуйста, что я использую здесь термин противоречие в его формальном логическом смысле, имея в виду предикат, любой вызов которого гарантированно приводит к результату FALSE вне зависимости от того, какие аргументы поставлены в соответствие его параметрам.) Но если ограничение является противоречием, то, прежде всего, отсутствует – или, по крайней мере, должна отсутствовать – какая-либо возможность добавления его к системе! Более точно, если какой-либо пользователь пытается определить некоторое новое ограничение для некоторой базы данных, то система, прежде всего, должна проверить, что база данных в настоящее время удовлетворяет этому ограничению. Если эта проверка не удается, то ограничение, очевидно, должно быть отброшено; и если это ограничение является противоречием, то база данных ни коем образом не может удовлетворять ему в настоящее время.

Конечно, здесь я в целях обсуждения предполагаю, что система действительно может обнаружить тот факт, что база данных не удовлетворяет некоторому предлагаемому ограничению. В сопутствующей статье [1] обсуждается, что происходит при недействительности этого предположения. Однако для полноты я привожу здесь краткий набросок того, что должно происходить в правильно организованной системе, когда некоторый пользователь пытается определить некоторое новое ограничение базы данных DC:

1. Система вычисляет логическое выражение ограничения DC над текущим состоянием базы данных.
2. Если результатом вычисления является TRUE, то система принимает DC, как допустимое ограничение, и с этого момента обеспечивает его соблюдение (до тех пор, пока в некоторый момент времени оно не будет отменено).
3. Если результатом вычисления является FALSE, то система отвергает DC как ограничение, не допустимое в данное время.
4. Если вычисление не заканчивается в течение некоторого преопределенного периода времени, возникает тайм-аут, и система отвергает DC – не потому, что это ограничение является недопустимым, а из-за того, что оно является слишком сложным, чтобы система могла им управлять.

Замечание по поводу Третьего Манифеста

Хотя парадокс Эпименида по своей сути слишком прост для иллюстрации этого факта, в общем случае идея «предикатов, ссылающихся на предикаты» в реляционной терминологии соответствует отношениям, значениями атрибутов которых являются отношения (relation-valued attributes, RVA). В частности, непосредственно самоссылащийся предикат – т.е. предикат, включающий прямую ссылку на самого себя – соответствует отношению некоторого типа T, содержащему атрибут того же типа T. Такой тип отношения T называется рекурсивно определенным типом. В [4] по этому поводу говорится следующее:^♦♦

<цитата>

Открытым остается вопрос о том, можно ли определять тип отношения рекурсивно, напрямую или косвенно, в терминах его же самого. Более точно, пусть RELATION{H} является типом отношения, и пусть S(1), S(2), ... – это последовательность множеств, определяемая следующим образом:

S(1) = {t : t является типом некоторого атрибута в {H}}

S(i) = {t : t является типом некоторого компонента в некотором возможном представлении некоторого скалярного типа или типом некоторого атрибута некоторого типа отношения в S(i-1) }

(i > 1)

Если существует некоторое n (n > 0) такое, что RELATION{H} – элемент S(n), то этот тип RELATION{H} является рекурсивно определенным. (Это определение нуждается в небольшом расширении, если поддерживается наследование типов, но эта деталь нас здесь не задевает.) Таким образом, открытый вопрос состоит в том, следует ли допускать рекурсивно определяемые типы. Наша модель не настолько зависит от ответа на этот вопрос, чтобы мы чувствовали себя обязанными уделить ему отдельное внимание; однако в данной книге мы следуем Принципу осторожного проектирования [3] и полагаем (там, где это существенно), что такие типы не допускаются.

</цитата>

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

• Примите к сведению, что я не призываю полностью запретить RVA. Я говорю об этом потому, что многие люди критиковали Третий Манифест за поддержку RVA на том основании, что допущение таких отношений выводит нас в сферу логики второго (или более высокого) порядка. Последнее утверждение, по-видимому, является верным, но никто еще не смог продемонстрировать какую-либо конкретную проблему, порождаемую этим фактом (т.е. только этим фактом) – по крайней мере, никто не продемонстрировал такую проблему нам, авторам [4].
• В приведенной выше цитате из [4] говорится, что в этой книге мы полагаем, что рекурсивно определяемые типы не допускаются. Однако в описанном в этой же книге языке Tutorial D определение таких типов допускается (возможно, косвенным образом). Вот простой пример:
  
  VAR RX BASE RELATION { A1 INTEGER, A2 SAME_TYPE_AS ( RX ) };
  
  Более сложный пример:
  
  VAR RX BASE RELATION { A1 INTEGER, A2 SAME_TYPE_AS ( RY ) };
  VAR RY BASE RELATION { A3 INTEGER, A4 SAME_TYPE_AS ( RX ) };
  
  Поэтому, возможно, языку Tutorial D в том виде, в котором он описывается в [4], свойственно отсутствие разрешимости. Однако я полагаю, что можно было бы создать реализацию, в которой бы отвергалась любая попытка использования этой «возможности» путем предотвращения (желательно, во время компиляции) любой попытки определения (напрямую или косвенным образом) типа T с использованием его же самого – примерно так же, как система должна предотвращать любую попытку определения ограничения, при вычислении которого во время определения не может быть получено значение TRUE.

Литература

1. C. J. Date: "And Now for Something Completely Computational," www.thethirdmanifesto.com (July 2006). Имеется перевод на русский язык С.Д. Кузнецова: К. Дж. Дейт. А теперь про нечто полностью вычислительное.
2. C. J. Date: "How We Missed the Relational Boat" and "Answers to Puzzle Corner Problems (Installments 13-17)," in C. J. Date, Relational Database Writings 1991-1994. Reading, Mass.: Addison-Wesley (1995).
3. C. J. Date: "The Principle of Cautious Design," in C. J. Date (with Hugh Darwen): Relational Database Writings 1989-1991. Reading, Mass.: Addison-Wesley (1992).
4. C. J. Date and Hugh Darwen: Databases, Types, and the Relational Model: The Third Manifesto (3rd edition). Reading, Mass.: Addison-Wesley (2006). (Второе издание книги опубликовано в переводе на русский язык: К. Дж. Дейт, Хью Дарвен. Основы будущих систем баз данных: третий манифест. Перевод под ред. С.Д.Кузнецова Янус-К, 2004.)
5. Hugh Darwen: "The Nullologist in Relationland; or, Nothing Really Matters," in C. J. Date (with Hugh Darwen): Relational Database Writings 1989-1991. Reading, Mass.: Addison-Wesley (1992).
6. Anon.: Private correspondence with Hugh Darwen (December 2005 - January 2006).