II.9. Релационни операции върху мултимножества — Разширена писмена разработка
Разширена писмена разработка. II.9. Релационни операции върху мултимножества
Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.
Кратка разработка и уроци по темата · План за изпита · Покритие · Източници
Обхват от конспекта
Релационни операции върху мултимножества. Защо са необходими мултимножествата? Обединение, сечение и разлика при мултимножествата. Проекция върху мултимножества. Декартово произведение върху мултимножества. Съединенията при мултимножествата.
Покритие на конспекта
Всяка подточка води към съответния раздел на разработката.
- Релационни операции върху мултимножества — 1. Кратността е част от информацията
- Защо са необходими мултимножествата? Обединение, сечение и разлика при мултимножествата — 2. Защо се използват и как работят множествените операции
- Проекция върху мултимножества — 3. Проекция върху мултимножества
- Декартово произведение върху мултимножества — 4. Произведение и умножаване на кратностите
- Съединенията при мултимножествата — 5. Съединения при мултимножества
Кратък план за изпита
- Мултимножество и кратност на кортеж.
- Причини за запазване на повторенията.
- Обединение, сечение и разлика чрез кратности.
- Проекция, произведение и съединения.
- Разлики спрямо множествените закони и SQL.
1. Кратността е част от информацията
Мултимножеството (bag) е колекция, в която еднакъв елемент може да участва повече от веднъж. Формално на всеки възможен кортеж t съпоставяме неотрицателна цяла кратност mR(t). Кратност 0 означава отсъствие. За обикновено множество кратностите са само 0 и 1. Редът на елементите остава незначим: мултимножество не е сортиран списък.
Например {SQL, SQL, ER} има общо три срещания и две различни стойности. Двете SQL срещания могат да произхождат от два различни курса или две различни записвания. След проектиране само на името разграничителните идентификатори вече не се виждат, но броят срещания може да остане значим. Дубликат в резултат не доказва сам по себе си грешка в първичните данни.
2. Защо се използват и как работят множествените операции
Премахването на дубликати изисква работа, например сортиране или хеширане. Ако заявката не изисква уникални стойности, запазването на повторенията може да избегне тази работа. Освен това COUNT, SUM и AVG често трябва да отчитат всяка отделна покупка, оценка или регистрация, дори видимите стойности да съвпадат. SQL по подразбиране често запазва повторенията, а DISTINCT ги премахва изрично.
За мултимножествените варианти на трите операции кратностите са:
m(R ⊎ S)(t) = mR(t) + mS(t) m(R ∩bag S)(t) = min(mR(t), mS(t)) m(R −bag S)(t) = max(mR(t) − mS(t), 0)
Символите тук са изписани с уточнение bag, за да не се смесват с класическите операции. СУ 11 използва обичайните знаци в изрично заявен мултимножествен контекст. При обединение събираме срещанията, при сечение вземаме толкова, колкото има и от двете страни, а при разлика премахваме по едно срещане за всяко съответстващо срещане от втория операнд.
R(Име) = {SQL, SQL, ER}
S(Име) = {SQL, ER, ER, XML}
R ⊎ S = {SQL, SQL, SQL, ER, ER, ER, XML}
R ∩bag S = {SQL, ER}
R −bag S = {SQL}
S −bag R = {ER, XML}Операндите отново трябва да са съвместими по схема и домейни. Мултимножественото обединение е аналог на SQL UNION ALL. SQL UNION премахва дубликатите. INTERSECT ALL и EXCEPT ALL изразяват съответните мултимножествени варианти там, където конкретната СУБД ги поддържа; не бива да се приема еднаква поддръжка във всички продукти.
Някои множествени тъждества се променят. R ⊎ R удвоява кратностите и обикновено не е R. Разликата R −bag R е празна. Сечението с R отново е R, защото min(m,m)=m. Затова коректността на алгебрично преобразуване се проверява чрез кратности, а не чрез привичка от теорията на множествата.
3. Проекция върху мултимножества
Мултимножествената проекция запазва всяко срещане на входен ред. Ако различни входни кортежи дадат еднакъв проектиран кортеж, кратностите им се събират. За резултатен кортеж u: mπA(R)(u) = Σ mR(t) върху всички t, чиято A част е u.
КУРС(Код, Име) =
{(К01, SQL), (К02, SQL), (К03, ER)}
πИме(КУРС) = {SQL, SQL, ER} [bag]
δ(πИме(КУРС)) = {SQL, ER} [с премахване на дубликати]Тук оригиналните три реда са различни, но проекцията създава повторение. Операторът δ отделя операцията „направи стойностите уникални“ от избора на колони. Ако търсим броя курсове, резултатът е 3; ако търсим броя различни имена — 2. Всяка от двете задачи е разумна, но задава различен въпрос.
Селекцията, макар да не е отделна подточка тук, има проста мултимножествена семантика: кратността на ред, който удовлетворява условието, се запазва; иначе става 0. Тя не премахва повторенията сред преминалите редове. Това позволява селекция и проекция да се комбинират без скрита дедупликация.
4. Произведение и умножаване на кратностите
При произведението всяко срещане от първия операнд се съчетава с всяко срещане от втория. За кортежите r и s кратността на съставния кортеж е mR(r) · mS(s). Ако R(A) = {a,a} и S(B) = {b,b,b}, R × S съдържа шест срещания на (a,b). Общият размер е произведението от общите размери, като се броят повторенията.
Това правило обяснява защо съединение с дублиращи се ключови стойности може силно да увеличи броя редове. Ако програмата очаква точно един съвпадащ ред, тази уникалност трябва да е доказана с ограничение или с предходна операция; тя не е свойство на самия JOIN.
5. Съединения при мултимножества
θ-съединението запазва от произведението само комбинациите, които удовлетворяват условието. Естественото съединение сравнява общите атрибути и оставя едно тяхно копие, но не извършва автоматична дедупликация. За всяка съвпадаща двойка кратностите се умножават; ако последваща проекция събере различни резултатни кортежи в една стойност, те се сумират.
R(Код, Име) = {(К01, SQL), (К01, SQL)}
S(Код, Номер) = {(К01, У01), (К01, У01), (К01, У02)}
R ⋈ S:
(К01, SQL, У01) — кратност 4
(К01, SQL, У02) — кратност 2Това са допустими входни мултимножества за примера, без наложен уникален ключ. Ако после проектираме само Име, SQL има кратност 6. Ако задачата е да изброим различните имена, прилагаме δ и получаваме едно SQL. Ако броим реални участници, трябва да определим кои колони идентифицират участника и защо има повторения, вместо механично да добавяме DISTINCT.
Важна граница: при еднаква схема естественото съединение на две мултимножества не е непременно мултимножественото сечение. За общ кортеж кратностите при join се умножават, а при сечение се взема минимумът. При кратности 2 и 3 получаваме съответно 6 и 2. Точното следене на тези числа е основата за вярно разсъждение за реалните SQL резултати.
Литературна опора и граници на сверяването
Официална библиография на СУ — номерата по-долу са от нея.
- СУ 11 — Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Database Systems: The Complete Book, 2. изд., Prentice Hall, 2008. Пълен текст, наличен в проекта и използван за сверка.
- Точно четене: §5.1.1–5.1.6; печатни 205–212 / PDF 242–249. PDF страниците са поредни от началото на локалния файл; в това копие печатната страница + 37 дава PDF страницата.
- Страница на авторите за второто издание. Примерите тук са авторски. Означенията са обяснени в текста; SQL уточненията са разграничени от класическия модел.
Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.