Перевести на RA: би-импликация / эквивалентность

Question

(Нет, это не один из тех вопросов, которые переводят SQL в RA ;-) У меня есть формула в логике первого порядка, которую я хочу выразить в RA.Это должно быть легко: подход Кодда 1972 года в в документе «Реляционная полнота» состоит в том, чтобы показать, что каждый оператор FOL может быть эквивалентно выражен в RA.

При заданном соотношении SP:

• Заголовок {S# CHAR, P# CHAR, QTY INT}
• Ключ {S#, P#}
• Характеристический предикат SP ( s, p, q ) = 'Поставщик s поставляет Деталь p в количестве q . '

Экспресс: «Поставщик« S1 »и Поставщик« S2 »поставляют одинаковый набор деталей (без учетаколичества). '

Формула:

∀p. (∃q1. SP('S1', p, q1) ) ⇔ (∃q2. SP('S2', p, q2) )

Обратите внимание: если S1 вообще не поставляет детали, эта формула верна на тот случай, если S2 также не поставляет детали.

Это вопрос «да / нет» (в формуле нет свободных переменных);поэтому я бы ожидал выражение RA должно приводить к отношению без атрибутов, возвращая пустое отношение, если два Поставщика не предоставляют одинаковый набор Частей (формула оценивается как Ложь);в противном случае непустое отношение без атрибутов (формула оценивается как True).

Чтобы пояснить немного подробнее: обычно запросы возвращают список чего-либо - например, список частей, предоставленный S1, игнорируяколичество: SP WHERE (S# = 'S1') {P#} (или по-гречески π<sub>{P#}</sub>(σ<sub>S# = 'S1'</sub>(SP))).Для вопроса «да / нет» нас интересует только то, возвращает ли запрос что-то или ничего, например, Поставщик S1 поставляет деталь P456 ?: SP WHERE (S# = 'S1' AND P# ='P456') {} (π<sub>{}</sub>(σ<sub>S# = 'S1'</sub>(σ<sub>P# = 'P456'</sub>(SP)))).

ВыЗаметьте, что я использую вариант RA: Tutorial D от Date & Darwen .Это легче читать и набирать, чем оригинальный RA Кодда (я также включил греческие символы и форму подписки).Я ограничусь операторами Tutorial D , которые соответствуют RA Кодда.

Я могу сделать обратный запрос, который хочу: «Есть ли какие-то детали, поставляемые S1, но нена S2 или наоборот? '

Во-первых, пара сокращений для общих подвыражений

WITH S1P := SP WHERE (S# = 'S1'){P#},
     S2P := SP WHERE (S# = 'S2'){P#} :

( S1P MINUS S2P )
UNION
( S2P MINUS S1P );

Для тех, кто предпочитает греческий:

S1P := π<sub>{P#}</sub>(σ<sub>S# = 'S1'</sub>(SP))<br> S2P := π<sub>{P#}</sub>(σ<sub>S# = 'S2'</sub>(SP))<br> (S1P \ S2P) ∪ (S2P \ S1P)

Это вернет пустой результат на тот случай, если два Поставщика предоставят одинаковый набор Частей.Таким образом, все, что остается сделать, - это проект, в результате которого не будет атрибутов, и перевернуть пустой результат в непустой, и наоборот.Но в RA Кодда нет способа выразить этот переворот, AFAICT.

При применении метода Codd 1972 года к формуле самая внешняя операция - это полный квантификатор, поэтому преобразуйте это в отрицание экзистенциального:

¬∃p. ¬( (∃q1. SP('S1', p, q1) ) ⇔ (∃q2. SP('S2', p, q2) ) )

Но теперь самой внешней операцией является отрицание.Метод Кодда только позволяет отрицанию выглядеть вложенным внутри соединения.

Я застрял.Есть идеи?

Answer 1

Не существует выражения RA, которое отвечает на вопрос, если мы ограничимся операторами и семантикой RA в соответствии со спецификацией Codd 1972 года.

Даже если мы добавим операторы, обычно включаемые в RA в наши дни, мы не сможем ответитьвопрос как поставленный.Например, операторы, описанные в википедии , такие как «Переименовать» или «1005 *», «Расширить» (для вычисляемых столбцов), «Группировка / агрегация», «Внешние объединения».результат (отношение ноль градусов) не поддерживается Codd.Я говорю «возможно», потому что Кодд никогда строго не определяет «отношение».Есть сноска Кодда 1970 года 1 "R - это подмножество декартового произведения S<sub>1</sub> x S<sub>2</sub> x ... x S<sub>n</sub>.";но не указана нижняя граница для n.Ясно, что предполагается включить вырожденный «продукт» для n, равный 1, тогда почему бы не разрешить ноль?

Например, SQL не поддерживает таблицы с нулем степени.SQL поддерживает псевдорасширение потенциальной таблицы с нулевым градусом с помощью фиктивного столбца:

SELECT 'Yes' AS Dummy FROM SP WHERE...

Даже учитывая это, я утверждаю, что на поставленный вопрос нельзя ответить в SQL.(Рассмотрим случай, когда SP пусто: тогда два Поставщика предоставляют один и тот же набор Продуктов, а именно пустой набор; но FROM SP ... может возвращать только пустое отношение.)

Различные небыли предложены стандартные операторы или примитивы (см. Комментарии к q и к другим ответам).AFAICT нет авторитетного упоминания, которое «благословляет» какой-либо конкретный подход.Например, Книга Алисы , кажется, не учитывает отношения нулевой степени.

Чтобы кратко рассмотреть возможные операторы / примитивы.(Любой из них явно эквивалентен любому другому, в том смысле, что если у нас есть один, мы можем определить другие в терминах этого - кроме последнего.)

Те, кто возвращает true /false :

• Реляционное сравнение: подмножество ⊆, которое можно использовать для определения равенства отношений ==.(Для этого необходимо, чтобы операнды были 'Union Compatible'.)
• IS_EMPTY( ) (что появляется в Tutorial D ).

Сложность с возвращением true/ false в том, что в RA таких примитивов нет.(Операторы RA обычно описываются как «закрытые над отношениями».) В качестве альтернативы эти операторы могут возвращать отношение ноль градусов;но тогда почему бы не перейти к этому прямому?

Те, которые возвращают отношение ноль градусов :

• Операция дополнения, действительная только применительно к нулю градусовсвязь.(Это операция «перевернуть», обсуждаемая в q.)

• Сделать Dee примитивом, то есть непустое отношение степень-ноль.Тогда Dum =<sub>df</sub> Dee MINUS Dee;и в общем дополнении к r (который должен быть нулевым градусом) = _df Dee MINUS r

• Обеспечить примитив (ы)для выражения отношения литеральное / константное значение, так же как большинство языков программирования поддерживают выражение числовых или строковых литералов или более сложных структур данных.Тогда Dum/Dee - это всего лишь две из множества констант отношений.