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 — таблични изрази; конкретните диалекти могат да се различават.

Уроци за четене

  1. 82. Мултимножество и кратност на кортеж
  2. 83. Обединение, сечение и разлика на мултимножества
  3. 84. Проекция и селекция върху мултимножества
  4. 85. Произведение и съединяване на мултимножества
  5. 86. Множества и мултимножества: кога едно правило се променя

Примерната писмена разработка по-горе обобщава темата. Уроците развиват подточките на малки стъпки: понятия, пример, чертеж, точно четене и самостоятелна задача.

Литература

Библиографски сведения и източници · Официален конспект. Конкретните раздели и печатни/PDF страници са посочени във всеки урок; основният източник е СУ 11, второ издание.

Примери и упражнения

Уроци 82–86 съдържат самостоятелни задачи. Всяко условие повтаря необходимите данни, правила и означения. Решавай ги последователно; при преговор можеш да отвориш отделна задача без да търсиш нейни данни другаде.

Проверка на знанията

Към всеки от уроци 82–86 има четири въпроса и авторски отговори в затворени карти. Първо реши задачата, после сравни разсъждението си с отговора. Учебният речник разграничава термините според контекста.

Писмена разработка и устни въпроси

Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:

  1. Въведение: предмет, предназначение и място на темата.
  2. Точни определения, означения и основни понятия.
  3. Последователно изложение на подточките от конспекта и връзките между тях.
  4. Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
  5. Важни свойства, ограничения, сравнения и типични грешки.
  6. Кратко обобщение.

Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.