Реляционная Алгебра эквивалент SQL " не в"

Существует ли реляционная алгебра, эквивалентная выражению SQL NOT IN?

Например, если у меня есть отношение: 

A1  |  A2
----------
x   |  y
a   |  b
y   |  x

Я хочу удалить все Кортежи в отношении, для которого A1 находится в A2. В SQL я мог бы запросить: 

SELECT
    *
FROM
    R
WHERE
    R.A1 NOT IN
        (
        SELECT
            A2
        FROM
            R
        )
/

Что действительно ставит меня в тупик, так это как сделать подзапрос внутри оператора выбора реляционной алгебры, возможно ли это?:

Σ некоторый подзапрос здесь R

2 5
sql relational-algebra

2 ответа:

В реляционной алгебре это можно сделать с помощью картезианского произведения. Что-то вроде:

R-ρa1, a2 (πa11, a21 (σ A11 = A22 (ρ a11, a21(R) x ρa12, a22(R)))

  • переименуйте столбцы R, т. е. из a1 в a11 (левая рука) и a12 (правая рука)
  • возьмем поперечное произведение R с переименованными столбцами
  • выберите строки, где a11 равно a22
  • спроецируйте a12 и a22 и сохраните a11 и a21
  • переименовать к a1 и a2

Это дает вам строки, которые были сопоставлены. Вычтите это из R, чтобы найти строки, которые не совпадают.

6

Первый вопрос посылает нас вниз по неправильному мышлению. Это должно быть:

Существует ли реляционная алгебра, эквивалентная выражению SQL R WHERE ... [NOT] IN S?

(то есть ответ-это некоторая операция между двумя отношениями, не какой-то фильтр.)

Ответ-Да, это (естественно) JOIN ака оператор бабочки ⋈.

Чтобы понять, почему, давайте сначала приведем в порядок данное решение SQL. Как показано, он ищет атрибут A1 NOT IN отношение с одним атрибут A2. Это действительно неправильное совпадение в именах атрибутов. SQL также допускает NOT внутри условия where. Этот SQL делает логическую структуру более ясной: 

SELECT * FROM R
WHERE NOT (A1 IN (SELECT A2 AS A1 FROM R) )
Теперь мы можем видеть проекцию и переименование. (Окружающее NOT мы можем реализовать как множество минус, согласно первому ответу.) Таким образом, эквивалентное РА:

R - (R ⋈ ρA1⁄A2(πА2(R)))

Для интереса, учебник D: 

R MINUS (R JOIN (R {A2} RENAME A2 AS A1))

В том, как поставлен вопрос, есть похмелье от SQL-мышления. SQL WHERE заставляет вас перейти в "режим" на уровне строк. Это правило 7 contra Codd, требующее операторов set-at-time.

В общем случае SQL WHERE и RA σ с их фильтрами уровня строк могут быть более лаконично реализованы как (естественные) JOIN с логикой set-at-time. (Например, это то, что Date & Darwen делают в своих а алгебра.)

2