II.9. Релационни операции върху мултимножества
II. Специализирана част · Тема 9 · Подготовка по конспекта на СУ / ФМИ № 19, 2026/2027
Обхват от конспекта
Релационни операции върху мултимножества. Защо са необходими мултимножествата? Обединение, сечение и разлика при мултимножествата. Проекция върху мултимножества. Декартово произведение върху мултимножества. Съединенията при мултимножествата.
Цел на подготовката
Да можеш самостоятелно да обясниш понятията и връзките между тях, да дадеш собствен пример и да приложиш изброените подходи в задача.
Примерна писмена разработка
Авторски образец за подготовка по тази тема. Не е официален отговор, утвърден от СУ, и не задава задължителен обем или схема за оценяване. Чети го за разбиране; упражнявай възпроизвеждане със собствени примери и сверявай с пълния обхват на конспекта.
Мултимножества и необходимост
Мултимножеството, или bag, е неподредена колекция, в която един елемент може да се среща повече от веднъж. За кортеж t означаваме с m_R(t) неговата неотрицателна целочислена кратност в R. Множеството е частен случай с кратности 0 или 1. Подредената последователност е различно понятие: bag запазва повторенията, но не и реда.
SQL заявките обичайно работят с мултимножества. Дубликатите могат да са смислени — например две покупки с еднакъв продукт и цена — или да възникнат при проекция и съединение. Автоматичното им премахване би променило броя и сумите и може да изисква допълнителна обработка. За идентификация на конкретни събития е нужен подходящ ключ; еднаквите показвани стойности не доказват, че става дума за един и същ факт.
Операции чрез кратности
При обединение на мултимножества кратностите се събират: m_(R∪bag S)(t)=m_R(t)+m_S(t). При сечение се взема минимумът, а при разлика — max(0,m_R(t)−m_S(t)). Ако t се среща два пъти в R и три пъти в S, обединението има пет срещания, сечението — две, а разликата R−S — нула. Разликата S−R има едно срещане. Това са определения за bag операциите, не за обичайните SQL UNION и EXCEPT без ALL, които премахват дубликати.
Селекцията запазва кратността на всеки удовлетворяващ кортеж. При проекция кратността на резултатен кортеж е сумата от кратностите на всички входни кортежи, които се проектират в него. Например покупки (Иван,книга) и (Иван,тетрадка), всяка по веднъж, дават две срещания на Иван след проекция само на името.
При декартово произведение кратността на комбинация от два кортежа е произведение на входните кратности. Два еднакви леви и три еднакви десни кортежа дават шест еднакви комбинации. Θ-съединението филтрира това произведение, а естественото съединение съчетава съвпаденията по общите атрибути. Когато повече входни комбинации дават еднакъв резултат, техните приноси се сумират.
Алгебрични закони и извод
Закони от множествената алгебра не се пренасят автоматично. Например R∪bag R удвоява кратностите и не е равно на R. Премахването на дубликати е отделна операция. Проекцията и разликата не могат произволно да се разменят: различни входни кортежи може да станат еднакви след проекция и да се унищожат взаимно при изваждането. SQL операторите с ALL трябва да се разграничават от техните множествени варианти и да се отчита поддръжката им от конкретната СУБД. Главният практически извод е, че преди броене или сумиране трябва да знаем как съединенията и проекциите променят кратностите.
Литературна опора
Основен източник за сверяване: Garcia-Molina, Ullman, Widom, Database Systems: The Complete Book, второ издание, раздели 5.1. Учебник, официални материали и библиография. Примерите и изложението тук са авторски, а не превод на учебника.
За SQL съпоставките: официална документация на PostgreSQL — таблични изрази; конкретните диалекти могат да се различават.
Уроци за четене
- 82. Мултимножество и кратност на кортеж
- 83. Обединение, сечение и разлика на мултимножества
- 84. Проекция и селекция върху мултимножества
- 85. Произведение и съединяване на мултимножества
- 86. Множества и мултимножества: кога едно правило се променя
Примерната писмена разработка по-горе обобщава темата. Уроците развиват подточките на малки стъпки: понятия, пример, чертеж, точно четене и самостоятелна задача.
Литература
Библиографски сведения и източници · Официален конспект. Конкретните раздели и печатни/PDF страници са посочени във всеки урок; основният източник е СУ 11, второ издание.
Примери и упражнения
Уроци 82–86 съдържат самостоятелни задачи. Всяко условие повтаря необходимите данни, правила и означения. Решавай ги последователно; при преговор можеш да отвориш отделна задача без да търсиш нейни данни другаде.
Проверка на знанията
Към всеки от уроци 82–86 има четири въпроса и авторски отговори в затворени карти. Първо реши задачата, после сравни разсъждението си с отговора. Учебният речник разграничава термините според контекста.
Писмена разработка и устни въпроси
Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:
- Въведение: предмет, предназначение и място на темата.
- Точни определения, означения и основни понятия.
- Последователно изложение на подточките от конспекта и връзките между тях.
- Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
- Важни свойства, ограничения, сравнения и типични грешки.
- Кратко обобщение.
Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.