Реляционная алгебра: значения, которые встречаются только вместе - PullRequest
Новая
       27

Реляционная алгебра: значения, которые встречаются только вместе

0 голосов
/ 21 октября 2018

Рассмотрим таблицу идентификаторов сотрудников в ресторане и смены, на которых они работают.Если у меня есть схема данных, заданная как Shifts (ShiftID, EmployeeID), где Shift и EmployeeID вместе образуют ключ для отношения, как я могу найти все пары сотрудников, которые когда-либо только работают вместе.То есть мне нужны кортежи (A, B) и (B, A), если сотрудник A работает только тогда, когда сотрудник B работает и наоборот.

Возможно ли это с помощью базовых операторов реляционной алгебры (выбор, проект, кросс-произведение, естественное объединение, переименование) и операций над множествами (объединение, пересечение, разность)?

Пример ввода:

Сменный сотрудник

1 A

1 B

2 A

2 B

3C

Ожидаемый результат

Сотрудник1 Сотрудник2

AB

BA

Моя попытка:

Сначала возьмите перекрестный продукт Shift и выберите все кортежи, в которых ShiftID одинаков, но EmployeeID различается (то есть все пары сотрудников работают в одну смену).

Затем я попытался взять кросс-произведение описанного выше отношения с собой и выбрать кортежи, в которых ShiftID одинаков, первый EmployeeID такой же, но второй EmployeeID отличается.Я пытался получить «DifferentPairs», поэтому я выбираю первый EmployeeID в первой копии и второй Employee ID во второй копии.

Но потом я застрял, потому что понял, что Pairs = DifferentPairs для сотрудников с более чем 1 парой, поскольку во втором перекрестном продукте могут быть сотрудники (A, B | A, C) и (A, C | A,B) и поэтому, если я возьму 1-й и 4-й ID, я получу (A, C) и (A, B), и теперь я вернусь с того места, с которого начал (не в приведенном мной примере, а просто в целом).

1 Ответ

0 голосов
/ 26 октября 2018

, если сотрудник А работает только тогда, когда работает сотрудник Б и наоборот.

Итак, мы хотим сравнить набор смен, в котором работает А, с набором, которыйB работает.

Тогда хорошо использовать реляционную алгебру, потому что отношения - это множества.Использовать SQL было бы сложно: таблицы не являются множествами (в общем), а SQL имеет ограниченный потенциал для операторов множеств.

Вы не упоминаете, какое разнообразие RA вы используете.Поэтому я возьму урок D из учебников Дейта и Дарвена.В частности, оператор GROUP для проекции на отношение, содержащий значения одного из его атрибутов в виде набора.Мы поместим это в переменную временного отношения: 

WITH ShiftSet := Shifts GROUP { ShiftID AS ShiftSet }

(Это по сути группирует по EmployeeID, поэтому мы получим один кортеж на сотрудника с изменениями этого сотрудника в качестве набора в атрибуте с именем ShiftSet.)

Затем мы объединяем кортежи Employee с одинаковым значением ShiftSet;с помощью обычного трюка самосоединения (нуждающегося в переименовании) 

ShiftSet JOIN (ShiftSet RENAME {EmployeeID as EmpID2})
WHERE EmployeeID NOT = EmpID2
{ALL BUT ShiftSet}

Условие WHERE состоит в том, чтобы отсеивать кортежи сотрудников, соединенные с собой.Конечный {ALL BUT ...} - это проекция ShiftSet, поэтому в результате мы получаем пары {EmployeeID, EmpID}.

Возможно ли это с базовыми операторами реляционной алгебры?

Да, это возможно с теми, кого вы перечислите.Первый комментарий Филиппа дает вам подсказки.По сути, вы делаете реляционный разрыв: см. Википедию для эквивалентной формулировки с этими операторами.Это приводит к тому, что вам не хватает RA, и это не смущает SQL.

...