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

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

Вот схема:

Матросы ( sid , sname, rating) Резервы ( sid , bid , price) Лодки ( bid , bname)

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

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); 

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

Это всего лишь половина ответа …

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

 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 ); 

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

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

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

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

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

РЕДАКТИРОВАТЬ

дополнительная часть ответа относительно 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.

Опираясь на ответ onedaywhen:

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

 B - A = B ∩ A' 

т.е. разность B и A на самом деле является пересечением B с дополнением A. У нас есть пересечение как разрешенный оператор, и в то время как собственное дополнение отношения является уродливым, дополнение R1 ⊆ 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 of

 SELECT DISTINCT Rx FROM R WHERE Rx=val 

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

 π( 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) ) ) )) 

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

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

 π( 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 ) 

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