Как понять `u = r ÷ s`, оператор деления, в реляционной алгебре?

Question

пусть будет база данных со следующими реляционными схемами: R(A,B,D) и S(A,B) с атрибутами одного и того же имени в том же домене и с экземплярами r и n.

Экземпляр r

Экземпляр s

Что такое схема и каковы кортежи u=r÷s? Как их определить на английском языке с помощью r и s?

Моя попытка

Я знаю, что

u=r÷s =

Что заставляет меня думать, что это будет только массив из одного столбца А, но я не уверен, что достаточно знать какой будет результат в массиве.

Можете ли вы помочь мне понять u = r ÷ s?

Answer 1

Интуитивное свойство оператора деления реляционной алгебры просто состоит в том, что оно является обратным к декартовому произведению. Например, если у вас есть R и S два отношений, то, если U есть отношение определяется как декартово произведение из них:

U = R x S 

деления является оператор таким образом, что:

U ÷ R = S 

и :

U ÷ S = R 

Таким образом, вы можете думать о результате U ÷ R как: «проекция U что, умноженное на R, производит U ", а также операции ÷, в качестве операции, которая находит все« детали »U, которые объединены с все кортежи R.

Однако, чтобы быть полезным, мы хотим, чтобы эта операция применима к любой паре отношений, то есть мы хотим разделить отношение, которое является , а не результатом декартова продукта. Для этого формальное определение более сложное.

Итак, предположим, что мы имеем два отношения R и S с атрибутами соответственно А и В, их разделение может быть определена как:

R ÷ S = π _AB (R) - П _AB ((π _АВ (R) х S) - R)

, которые могут быть считаны таким образом:

1. П _AB (R) x S: проект R по атрибутам R, которые не входят в S, и умножают (декартово произведение) это отношение с S. Это создает связь с атрибутами A из R и со строками всех возможных комбинаций строк S и проекции R;

2. Из предыдущего результата вычесть все кортежи первоначально в R, то есть выполнить (π _AB (R) х S) - R. Таким образом, мы получаем «лишние» кортежи, то есть кортежи в декартовом продукте, который не присутствовал в исходном соотношении.

3. Наконец, вычтите из исходного соотношения эти дополнительные кортежи (но, опять же, выполните эту операцию только по атрибутам R, которых нет в S). Таким образом, окончательная операция: π _A-B (R) - π _A-B (результат этапа 2).

Итак, подходит к вашему примеру, проекция r на D равно:

(D) 
d1 
d2 
d3 
d4 

и декартово произведение с s является:

(A, B, D) 
a1 b1 d1 
a1 b1 d2 
a1 b1 d3 
a1 b1 d4 

Теперь мы можем удалить из этого набора кортежи, которые также находились в исходном соотношении r, т.е.первые два кортежа и последние один, так что мы получаем следующий результат:

(A, B, D) 
a1 b1 d3 

И, наконец, мы можем удалить предыдущие кортежи (проектируется на D), от исходного соотношения (вновь проектируемого на D), то есть, мы убираем:

(D) 
d3 

от:

(D) 
d1 
d2 
d3 
d4 

и мы получаем следующий результат, который является конечным результатом разделения:

(D) 
d1 
d2 
d4 

Наконец, мы могли бы перепроверить результат путем умножения его с оригинальным соотношением s (который состоит только из кортежа (a1, b1)):

(A B D) 
a1 b1 d1 
a1 b1 d2 
a1 b1 d4 

И глядя на ряды исходного соотношения r , вы можете увидеть этот факт, что должно дать вам важную информацию о значении оператора деления:

только значение из колонки D в r, которые присутствуют вместе с (a1, b1) (единственный кортеж s), являются , d2 и d4.

Вы также можете увидеть другой пример в Wikipedia, и для детального объяснения разделения, вместе с его преобразование SQL, вы можете взглянуть на эти slides.