86. Множества и мултимножества: кога едно правило се променя

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

Цел: да проверяваш алгебрични равенства с кратности и да намираш контрапример.

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

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

Алгебрично равенство твърди еднакъв резултат за всички допустими входове. Един съвпадащ пример не го доказва, но един контрапример е достатъчен да го опровергае.

Някои правила се запазват при bag: R ∪ S = S ∪ R, защото n+m=m+n; R ∩ S = R − (R − S), защото n−max(0,n−m)=min(n,m). Други се променят: R ∪ R не е R при непразен bag, тъй като всяка кратност се удвоява.

Множественото равенство (R ∪ S) − T = (R − T) ∪ (S − T) не е общовалидно за bag. Вляво срещанията първо се събират, после T ги отменя веднъж; вдясно T отменя срещания отделно във всеки вход. Това е и причината да не пренасяме механично оптимизации между двете семантики.

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

Нека R(A) = S(A) = T(A) = ⟦(а)⟧. При bag лявата страна (R ∪ S) − T има 2−1=1 срещане на (а). Дясната има (1−1)+(1−1)=0. При множества и двете страни са празни, защото обединението оставя (а) само веднъж.

R = S = T = ⟦а⟧. Ляво: (1+1)−1 = 1. Дясно: (1−1)+(1−1) = 0
Схема на примера. Не е ER диаграма. Отвори в пълен размер.

Точно четене

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

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

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

Условие

Дадени са едноколонни мултимножества R(Код) = ⟦(К1), (К1)⟧, S(Код) = ⟦(К1)⟧ и T(Код) = ⟦(К1)⟧, със същия текстов домейн и без NULL. Това са всички срещания. За bag ∪ събира кратности; − дава max(0,n−m). Във въпрос 3 вместо тях разгледай съответните множества R′ = S′ = T′ = {(К1)}, със стандартни множествени ∪ и −. Контрапример означава входове, при които двете страни на предполагаемо общо равенство са различни.

Кратности на К1: R=2, S=1, T=1. Ляво: (R ∪ S) − T. Дясно: (R − T) ∪ (S − T)
Дадените факти и означения; резултатът остава за решаване. Не е ER диаграма. Отвори в пълен размер.
  1. Колко срещания на (К1) има в bag израза (R ∪ S) − T?
  2. Колко срещания има в bag израза (R − T) ∪ (S − T)?
  3. Какви са резултатите на същите два израза за R′, S′ и T′ като множества?
  4. Какъв извод правим за равенството при мултимножества: никога не е вярно или не е вярно за всички входове?

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

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

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

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

max(0,2+1−1)=2 срещания: ⟦(К1), (К1)⟧.

Първо bag обединение: 2 + 1 = 3. После отстраняваме 1 срещане. Лявата страна има 2 срещания на К1
Схема към отговор 1. Не е ER диаграма. Отвори в пълен размер.
Покажи отговор 2

max(0,2−1)+max(0,1−1)=1+0=1 срещане: ⟦(К1)⟧.

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

И двата са празни. R′∪S′ съдържа К1 веднъж и T′ го отстранява; всяка от отделните разлики също е празна.

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

Не е вярно за всички входове. Дадените bag са контрапример; това не изключва равенство при други данни, например когато T е празно.