83. Обединение, сечение и разлика на мултимножества

Специализирана тема С9 · Програма № 19, СУ / ФМИ, 2026/2027 г. Авторски урок, примери и задача; не са официални отговори на СУ.

Цел: да пресмяташ кратностите чрез събиране, минимум и изваждане с долна граница нула.

Около 10–20 минути с примера и задачата; четенето от учебника може да се отдели в следваща стъпка.

Основни понятия

Ако кортеж t има кратност n в R и m в S, то в bag обединението R ∪ S кратността му е n+m. Повторенията се събират; това е различно от множественото обединение.

В bag сечението R ∩ S кратността е min(n,m). В bag разликата R − S е max(0,n−m): всяко срещане в S отменя едно в R, но няма отрицателен брой редове.

Както при множествата, входните схеми и домейни трябва да са съвместими. В таблица на кратностите колоната „кратност“ е помощно описание на bag, а не добавен атрибут в самата разглеждана релация.

Практичен пример

Нека R(Код) = ⟦(А), (А), (Б)⟧ и S(Код) = ⟦(А), (Б), (Б), (В)⟧. За А имаме n=2,m=1: в обединението са 3, в сечението 1, в R−S е 1. За Б стойностите са съответно 3,1,0; за В — 1,0,0.

За кортеж А: n = 2 в R, m = 1 в S. Обединение: 2 + 1; сечение: min(2,1). Разлика R − S: max(0,2−1) = 1
Схема на примера. Не е ER диаграма. Отвори в пълен размер.

Точно четене

СУ 11: Garcia-Molina, Ullman и Widom, Database Systems: The Complete Book, второ издание, §5.1.2, печатни 207–209 / PDF 244–246. Чети само посочените раздели в този диапазон; примерите и задачата тук са авторски.

Учебникът и официалната библиография · Учебен речник на понятията.

Самостоятелна кратка задача

Условие

Дадени са R(Код) = ⟦(А), (А), (А), (Б)⟧ и S(Код) = ⟦(А), (А), (Б), (Б), (В)⟧. Това са всички срещания, със същия текстов домейн, без NULL. Всички операции са върху мултимножества. За кратности n в R и m в S използвай n+m за ∪, min(n,m) за ∩ и max(0,n−m) за −. Можеш да отговаряш с кратност за всеки различен кортеж.

R: А×3, Б×1. S: А×2, Б×2, В×1. Сметни кратността на всеки кортеж отделно
Дадените факти и означения; резултатът остава за решаване. Не е ER диаграма. Отвори в пълен размер.
  1. Какви са кратностите в R ∪ S?
  2. Какви са кратностите в R ∩ S?
  3. Какво съдържа R − S?
  4. Какво съдържа S − R и защо разликата не е симетрична?

Реши по условието и изпрати отговорите по номера в разговора. Отвори картите, когато искаш да провериш решението си.

Отговори за преговор

Авторски примерни отговори, затворени по подразбиране. Tab до заглавието; Enter или Space разгъва картата.

Покажи отговор 1

А: 5; Б: 3; В: 1. Общо девет срещания.

А: 3 + 2 = 5. Б: 1 + 2 = 3; В: 0 + 1 = 1. R ∪ S има 5 + 3 + 1 = 9 срещания
Схема към отговор 1. Не е ER диаграма. Отвори в пълен размер.
Покажи отговор 2

А: 2; Б: 1; В: 0. Следователно ⟦(А), (А), (Б)⟧.

Покажи отговор 3

А: max(0,3−2)=1; Б: max(0,1−2)=0; В: 0. Резултатът е ⟦(А)⟧.

Покажи отговор 4

А: 0; Б: 1; В: 1, тоест ⟦(Б), (В)⟧. Отменяме срещания от различен изходен bag при смяна на посоката.