II.8. Алгебра на релационните операции — Разширена писмена разработка
Разширена писмена разработка. II.8. Алгебра на релационните операции
Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.
Кратка разработка и уроци по темата · План за изпита · Покритие · Източници
Обхват от конспекта
Алгебра на релационните операции. Основи на релационната алгебра. Множествени операции върху релациите. Проекция. Селекция. Декартово произведение. Естествено съединение. Θ-съединения. Комбиниране на операции за формиране на заявки. Преименуване. Зависими и независими операции. Линейна нотация на алгебричните изрази.
Покритие на конспекта
Всяка подточка води към съответния раздел на разработката.
- Алгебра на релационните операции — 1. Алгебрата като език за заявки
- Основи на релационната алгебра — 1. Алгебрата като език за заявки
- Множествени операции върху релациите — 2. Множествени операции
- Проекция — 3. Проекция и селекция
- Селекция — 3. Проекция и селекция
- Декартово произведение — 4. Декартово произведение и преименуване
- Естествено съединение — 5. Естествено и θ-съединение
- Θ-съединения — 5. Естествено и θ-съединение
- Комбиниране на операции за формиране на заявки — 6. Сложна заявка и линеен запис
- Преименуване — 4. Декартово произведение и преименуване
- Зависими и независими операции — 7. Зависими и независими операции
- Линейна нотация на алгебричните изрази — 6. Сложна заявка и линеен запис
Кратък план за изпита
- Релационна алгебра и затвореност.
- Обединение, сечение и разлика; съвместимост.
- Селекция, проекция, преименуване и произведение.
- Естествено и θ-съединение.
- Композиция, независим базис и линеен запис.
1. Алгебрата като език за заявки
Релационната алгебра описва заявки чрез операции, които приемат релации и връщат релации. Затвореността позволява резултатът от една операция да е вход за друга и така да се изграждат сложни изрази. В класическия вариант релациите са множества: дублиран кортеж не се пази втори път и редът на резултата не е определен.
Алгебрата описва логическо преобразуване. Тя не определя непременно физическия алгоритъм за достъп до диска, използвания индекс или реда на реалните цикли. Две еквивалентни заявки могат да имат различни планове за изпълнение. При разсъждение трябва да се знаят входните схеми, типовете на атрибутите и семантиката на всяка операция.
2. Множествени операции
Обединението R ∪ S съдържа кортежите от поне единия операнд; сечението R ∩ S — общите; разликата R − S — тези от R, които липсват в S. Необходима е съвместимост: еднакви атрибути с подходящи домейни, евентуално след преименуване. Само еднаквият брой колони не е достатъчен, ако колоните представят несъпоставими величини.
R(Код) = {К01, К02}; S(Код) = {К02, К03}
R ∪ S = {К01, К02, К03}
R ∩ S = {К02}
R − S = {К01}; S − R = {К03}Обединението и сечението са комутативни, разликата не е. При множествената семантика R ∪ R = R. Тези свойства не трябва автоматично да се пренасят към операциите с натрупване на повторения при мултимножества.
3. Проекция и селекция
Селекцията σC(R) запазва редовете, за които условието C е вярно, и не променя схемата. Условието може да комбинира сравнения с AND, OR и NOT. В класическия вариант без NULL оценяването е двузначно. Проекцията πA₁,…,Aₖ(R) избира атрибути и премахва възникналите дубликати. Тя променя схемата и може да намали броя кортежи.
КУРС(Код, Име, Часове) =
{(К01, SQL, 30), (К02, ER, 12), (К03, SQL, 18)}
σЧасове≥18(КУРС) = {(К01, SQL, 30), (К03, SQL, 18)}
πИме(КУРС) = {SQL, ER}Селекция избира редове, проекция — атрибути. Името SELECT в SQL не е буквален синоним само на алгебричната селекция: списъкът след SELECT има роля на проекция, а WHERE — на селекция. При класическа проекция не остават две еднакви стойности SQL; при SQL без DISTINCT може да останат.
4. Декартово произведение и преименуване
R × S съдържа всяка възможна комбинация от ред на R и ред на S. При |R| = m и |S| = n резултатът има m·n реда и сбора от броя атрибути. Съвпадащите имена трябва да се разграничат чрез квалифициране или преименуване. Произведението не проверява само по себе си дали комбинацията има бизнес смисъл.
Операторът ρ преименува релацията или нейните атрибути, без да променя стойностите. Например ρA(НомерA,ИмеA)(ЧИТАТЕЛ) и ρB(НомерB,ИмеB)(ЧИТАТЕЛ) създават две различимо именувани копия за самосъединение. Така можем да намерим двама различни читатели с еднакво име чрез условие НомерA ≠ НомерB и ИмеA = ИмеB. Преименуването е особено важно при повтарящи се роли на едно множество.
5. Естествено и θ-съединение
θ-съединението R ⋈C S е селекция върху произведението: σC(R × S). Условието може да съдържа равенство, неравенство или комбинация от сравнения. При equijoin се сравнява за равенство, но двете сравнявани колони могат да останат отделни атрибути на резултата.
Естественото съединение R ⋈ S сравнява за равенство всички едноименни атрибути и оставя по едно копие от тях. Ако няма общи имена, то е декартово произведение. Ако всички имена са общи и схемите са съвместими, при множествена семантика резултатът е сечението. Еднакво име на колони с различен смисъл може да наложи нежелано условие; затова естественото съединение изисква внимателни схеми.
КУРС(Код, Име) = {(К01, SQL), (К02, ER)}
ЗАПИСВАНЕ(Номер, Код) = {(У01, К01), (У02, К01)}
ЗАПИСВАНЕ ⋈ КУРС =
{(У01, К01, SQL), (У02, К01, SQL)}К02 не се появява, защото няма съвпадащо записване. Това е вътрешно съединение; запазването на несъвпаднали редове изисква външно съединение от разширената алгебра. Броят резултатни редове не е непременно равен на броя на който и да е операнд.
6. Сложна заявка и линеен запис
Нека към последния пример има КУРСИСТ(Номер, ИмеКурсист) с редове (У01, Ана) и (У02, Борис). Търсим имената на записаните в курс SQL. Получаваме вложения израз πИмеКурсист(КУРСИСТ ⋈ ЗАПИСВАНЕ ⋈ σИме='SQL'(КУРС)). Селекцията първо ограничава курсовете, съединенията намират свързаните курсисти, а проекцията запазва имената. Ако двама курсисти имат едно и също име, класическият резултат съдържа името веднъж; за разграничаване трябва да се запази и номерът.
Линейната нотация дава имена на междинните резултати:
T1 ← σИме='SQL'(КУРС) T2 ← ЗАПИСВАНЕ ⋈ T1 T3 ← КУРСИСТ ⋈ T2 Резултат ← πИмеКурсист(T3)
Тук стрелката означава „нека този резултат се нарича“, а не ФЗ или ER ограничение. Междинните имена са за описание на заявката; не изискват физически запис на временни таблици. Линейният запис улеснява проверката на схемата след всяка стъпка и е удобен за писмено решение.
7. Зависими и независими операции
В този контекст „зависима операция“ означава операция, изразима чрез други операции, а не функционална зависимост между атрибути. Един обичаен базис включва селекция, проекция, декартово произведение, обединение, разлика и преименуване. Сечението се извежда като R − (R − S); θ-съединението — като селекция върху произведение; естественото съединение — чрез подходящо преименуване, произведение, селекция за равенство и проекция.
Производните операции се запазват в езика, защото изразяват намерението по-ясно. „Независими“ се разглежда спрямо избрания език и базис, а не като абсолютна практическа важност. При преобразуване на заявка трябва да се запазят схемата и семантиката: например ранна проекция не бива да премахва атрибут, който още е нужен за условие на съединение. Алгебрата дава едновременно език за точно формулиране и основа за еквивалентни преобразувания.
Литературна опора и граници на сверяването
Официална библиография на СУ — номерата по-долу са от нея.
- СУ 11 — Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Database Systems: The Complete Book, 2. изд., Prentice Hall, 2008. Пълен текст, наличен в проекта и използван за сверка.
- Точно четене: §2.4.1–2.4.13; печатни 38–52 / PDF 75–89. PDF страниците са поредни от началото на локалния файл; в това копие печатната страница + 37 дава PDF страницата.
- Страница на авторите за второто издание. Примерите тук са авторски. Означенията са обяснени в текста; SQL уточненията са разграничени от класическия модел.
Текстът и примерите са авторска учебна разработка, а не официален отговор или указание на изпитна комисия на СУ. Номерацията на разделите в плана е авторска. Препратките показват опората за понятията, а не че примерите са преписани от учебник.