Преобразование агрегатных операторов из SQL в реляционную алгебру

Question

У меня написано несколько SQL-запросов, которые я хочу преобразовать в реляционную алгебру. Однако в некоторых запросах используются агрегирующие операторы, и я не знаю, как их преобразовать. В частности, они используют операторы COUNT и GROUP BY .. HAVING.

Вот схема:

Моряки ( sid , имя, рейтинг) Резервы ( sid , ставка , цена) Лодки ( ставка , имя)

Вот пример того, что я делаю: найдите ставки и имена всех лодок, зарезервированных ровно 2 моряками.

SELECT B.bid, B.bname
FROM Boats B, Reserves R
WHERE B.bid = R.bid
GROUP BY R.bid
HAVING 2 = (SELECT COUNT(*)
FROM Reserves R2
WHERE R2.bid = B.bid);

Допустимые операции реляционной алгебры: выбор, проекция, объединение, условное объединение, переименование, объединение, пересечение, перекрестное произведение, деление

Answer 1

«Я читал книгу с главой по реляционной алгебре, и в ней вообще не упоминались агрегатные функции для них».

Литература по реляционной алгебре обычно ограничивается той частью алгебры, котораяделает его закрытым по отношениям .Алгебра замкнута на множестве типов (я, вероятно, немного небрежно выражаюсь, но основная идея верна), если ни один из операторов алгебры не возвращает значение типа, который не является членом этого множестватипов, над которыми замкнута алгебра.

Если все, что у вас есть (или вы хотите рассмотреть в книге), это набор всех типов отношений, и вы хотите написать трактовку алгебры, то вы не можете определитьоператор, который возвращает целое число (COUNT) или число с плавающей запятой (HARMONICMEAN) или дату (MIN ()), или что-то подобное, не нарушая свойство 'closed' алгебры.

Это не означает, что такие операции агрегирования бесполезны (конечно, нет).Как правило, они просто не совсем актуальны в контексте, где основной целью является объяснение JOIN, PROJECT, RESTRICT и т. Д.

EDIT

дополнительная часть ответа относительно GROUP BY ... HAVING,Вы правильно заметили, что эта конструкция SQL является нетривиальной вещью, когда речь идет об эквивалентах алгебры.Суть этого в том, что в наборе операторов алгебры, о котором вы упоминаете, отсутствует оператор, необходимый для достижения таких целей, и этот оператор - GROUP.GROUP принимает входное отношение и создает выходное отношение, в котором один из атрибутов имеет отношение .

Например, GROUP (RESERVES, SAILORS_AND_THEIR_BID (SID, PRICE)) произведетотношение степени 2 с атрибутами BID и SAILORS_AND_THEIR_BID.Последний атрибут имеет отношение к значению, поэтому выражение COUNT (SAILORS_AND_THEIR_BID) становится действительным в контексте условия RESTRICT, применяемого к этому отношению, так что вы можете написать (GROUP (RESERVES, SAILORS_AND_THEIR_BID (SID, PRICE))) WHERE COUNT(SAILORS_AND_THEIR_BID) = 2.

Answer 2

Это только половина ответа ...

Соотношение "лодки, зарезервированные двумя или более моряками" можно найти с помощью условного соединения и проекции, которые входят в ваш набор разрешенных операций:

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid;

Соотношение «лодки, зарезервированные тремя или более моряками» можно найти с помощью условного соединения (дважды) и проекции, которые входят в ваш набор разрешенных операций:

SELECT DISTINCT R1.bid
  FROM Reserves AS R1
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
       JOIN Reserves AS R3
          ON R1.bid = R3.bid
          AND R2.sid < R3.sid;

Если , у нас был оператор минус, например EXCEPT в стандартном SQL:

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
EXCEPT
SELECT DISTINCT R1.bid
  FROM Reserves AS R1
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
       JOIN Reserves AS R3
          ON R1.bid = R3.bid
          AND R2.sid < R3.sid;

Если , у нас было ограничение (WHERE в SQL) и полуразница (aka оператор antijoin ) (например, NOT IN в SQL):

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
 WHERE R1.bid NOT IN (
                      SELECT DISTINCT R1.bid
                        FROM Reserves AS R1
                             JOIN Reserves AS R2
                                ON R1.bid = R2.bid
                                   AND R1.sid < R2.sid
                             JOIN Reserves AS R3
                                ON R1.bid = R3.bid
                                AND R2.sid < R3.sid
                     );

... но ваш набор разрешенных операций не включает ограничение, полуразличие или минус: (

Answer 3

Опираясь на один ответ, когда:

Да, отсутствие оператора разности множеств наносит вред.Это должно быть полностью разрешено.Однако мы можем выразить разницу между множеством с помощью дополнения и пересечения множества:

B - A = B ∩ A'

, т. Е. Различие B и A фактически является пересечением B с дополнением A.У нас есть пересечение в качестве допустимого оператора, и хотя собственное дополнение отношения является уродливым, дополнение R1 1 R относительно R (т. Е. Вещи в R, которых нет в R1), можно легко найти с помощью объединения:

SELECT DISTINCT R0.x
FROM R as R1
JOIN R as R0 ON R1.x<>R0.x
WHERE R1.x=val

- это дополнение к R, равное

SELECT DISTINCT R.x FROM R WHERE R.x=val

---

Итак, вот решение загадки, я думаю: все лодки зарезервированы легкодвумя или более парнями: выберите все лодки, которые находятся в таблице резервов, возьмите с собой декартово произведение результата, затем выберите каждый ряд, в котором есть разные матросы1 и матросы2.В громоздкой нотации реляционной алгебры они научили меня:

π( R.bid ) (
   σ( R.bid=R2.bid and R.sid<R2.sid )( R x ρ(R, R2) ) 
)

(где π - оператор проекции, σ - оператор выбора, а ρ - оператор переименования)

Это объединяет idиз всех лодок, зарезервированных двумя или более людьми.Теперь я собираюсь получить все лодки, которые были зарезервированы двумя или менее парнями.Для этого я выберу все лодки, зарезервированные тремя или более парнями, и возьму дополнение набора, выбрав все строки из исходной таблицы, которых нет в этом наборе.Это не будет красиво, но здесь это так:

 π(R.bid)(σ(R.bid<>R1.bid)(
    π(R.bid)(R)
      x
    π(R1.bid) (
        σ( R1.bid=R2.bid and R2.bid=R3.bid and R1.sid<R2.sid and R2.sid<R3.sid )( ρ(R, R1) x ρ(R, R2) x ρ(R, R3) )
     )
  ))

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

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

π( R.bid ) (
   σ( R.bid=R2.bid and R.sid<R2.sid )( R x ρ(R, R2) ) 
) ∩ π( R.bid ) (
    σ(R.bid<>R1.bid)(
       π(R.bid)(R)
         x
       π(R1.bid) (
           σ( R1.bid=R2.bid and R2.bid=R3.bid and R1.sid<R2.sid and R2.sid<R3.sid )( ρ(R, R1) x ρ(R, R2) x ρ(R, R3) )
        )
     )
 )

Тьфу.Это так ужасно, это больно.Хотелось бы, чтобы я знал более приятные обозначения.

Вкратце, это может выглядеть так, я думаю:

(SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
    JOIN Reserves AS R2 ON R1.bid = R2.bid AND R1.sid < R2.sid
) INTERSECT (
SELECT DISTINCT R.bid
  FROM Reserves AS R1
    JOIN Reserves AS R2 ON R1.bid = R2.bid AND R1.sid < R2.sid
    JOIN Reserves AS R3 ON R1.bid = R3.bid AND R2.sid < R3.sid
    JOIN Reserves AS R ON R.bid<>R1.bid
)

Обратите внимание, что это точно одно решение, если только я выразил разницу в наборе какпересечение с дополнением.