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.
Точно четене
СУ 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 ∪ S?
- Какви са кратностите в R ∩ S?
- Какво съдържа R − S?
- Какво съдържа S − R и защо разликата не е симетрична?
Реши по условието и изпрати отговорите по номера в разговора. Отвори картите, когато искаш да провериш решението си.
Отговори за преговор
Авторски примерни отговори, затворени по подразбиране. Tab до заглавието; Enter или Space разгъва картата.
Покажи отговор 1
А: 5; Б: 3; В: 1. Общо девет срещания.
Покажи отговор 2
А: 2; Б: 1; В: 0. Следователно ⟦(А), (А), (Б)⟧.
Покажи отговор 3
А: max(0,3−2)=1; Б: max(0,1−2)=0; В: 0. Резултатът е ⟦(А)⟧.
Покажи отговор 4
А: 0; Б: 1; В: 1, тоест ⟦(Б), (В)⟧. Отменяме срещания от различен изходен bag при смяна на посоката.