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