Прикладна інформатика.
Функції СУБД.
Можна вважати, що якщо прикладна інформаційна система спирається на певну систему управління даними, що володіє цими властивостями, то ця система керування даними є системою управління базами даних (СУБД).
Основні функції СУБД:
Безпосереднє управління даними у зовнішній пам'яті. Ця функція включає забезпечення необхідних структур зовнішньої пам'яті як для зберігання даних, які безпосередньо входять до БД, так і для службових цілей, наприклад, для прискоренням доступу до даних у деяких випадках (зазвичай для цього використовуються індекси).
Управління буферами оперативної пам'яті. СУБД зазвичай працюють з БД значного розміру; принаймні цей розмір зазвичай істотно більше доступного обсягу оперативної пам'яті. Зрозуміло, що якщо при зверненні до будь-якого елементу даних буде здійснюватися обмін із зовнішньою пам'яттю, то вся система буде працювати зі швидкістю пристрої зовнішньої пам'яті. Практично єдиним способом реального збільшення цієї швидкості є буферизація даних в оперативній пам'яті. Тому в розвинених СУБД підтримується власний набір буферів оперативної пам'яті з власною дисципліною заміни буферів.
Управління транзакціями. Транзакція - це послідовність операцій над БД, що розглядаються СУБД як єдине ціле. Або транзакція успішно виконується, і СУБД фіксує (COMMIT) зміни БД, вироблені цією транзакцією, в зовнішній пам'яті, або ні одне з цих змін ніяк не відбивається на стані БД. Поняття транзакції необхідне для підтримки логічної цілісності БД.
журналізацію. Одним з основних вимог до СУБД є надійність зберігання даних у зовнішній пам'яті. Під надійністю зберігання розуміється те, що СУБД повинна бути в змозі відновити останній узгоджений стан БД після будь-якого апаратного або програмного збою. Звичайно розглядаються два можливі види апаратних збоїв: так звані м'які збої, які можна трактувати як раптову зупинку роботи комп'ютера (наприклад, аварійне вимкнення живлення), і жорсткі збої, що характеризуються втратою інформації на носіях зовнішньої пам'яті. Підтримання надійності зберігання даних в БД вимагає надмірності зберігання даних, причому та частина даних, яка використовується для відновлення, повинна зберігатися особливо надійно. Найбільш поширеним методом підтримання такої надмірної інформації є ведення журналу змін БД. Журнал - це особлива частина БД, недоступна користувачам СУБД і підтримувана з особливою ретельністю (іноді підтримуються дві копії журналу, що розташовуються на різних фізичних дисках), до якої надходять записи про всі зміни основної частини БД. В усіх випадках дотримуються стратегії "попереджуючої" записи до журналу (так званого протоколу Write Ahead Log - WAL). Найпростіша ситуація відновлення - індивідуальний відкат транзакції.
Підтримка мов БД. Для роботи з базами даних використовуються спеціальні мови, в цілому звані мовами баз даних. В сучасних СУБД зазвичай підтримується єдиний інтегрований мова, що містить всі необхідні засоби для роботи з БД, починаючи від її створення, і що забезпечує базовий призначений для користувача інтерфейс з базами даних. Стандартним мовою найбільш поширених в даний час реляційних СУБД є мова SQL (Structured Query Language).
Типова організація сучасної СУБД:
Логічно в сучасній реляційної СУБД можна виділити найбільш внутрішню частину - ядро СУБД (часто його називають Data Base Engine), компілятор мови БД (зазвичай SQL), підсистему підтримки виконавчі, набір утиліт. У деяких системах ці частини виділяються явно, в інших - ні, але логічно такий поділ можна провести у всіх СУБД.
Ядро СУБД - відповідає за управління даними у зовнішній пам'яті, управління буферами оперативної пам'яті, управління транзакціями і журналізацію. Відповідно, можна виділити такі компоненти ядра (принаймні, логічно, хоча в деяких системах ці компоненти виділяються явно), як менеджер даних, менеджер буферів, менеджер транзакцій і менеджер журналу. Ядро СУБД володіє власним інтерфейсом, не доступним користувачам безпосередньо і використовуються в програмах, що виробляються компілятором SQL (або в підсистемі підтримки виконання таких програм) і утилітах БД. Ядро СУБД є основною резидентної частиною СУБД. При використанні архітектури "клієнт-сервер" ядро є основною складовою серверної частини системи.
Основною функцією компілятора мови БД є компіляція операторів мови БД в деяку виконувану програму.
В окремі утиліти БД звичайно виділяють такі процедури, які занадто накладно виконувати з використанням мови БД, наприклад, завантаження і вивантаження БД, збір статистики, глобальна перевірка цілісності БД і т.д. Утиліти програмуються з використанням інтерфейсу ядра СУБД, а іноді навіть з проникненням всередину ядра.
3. Розподілені бази даних.
Основне завдання систем управління розподіленими базами даних полягає в забезпеченні засоби інтеграції локальних баз даних, що розташовуються в деяких вузлах обчислювальної мережі, з тим, щоб користувач, що працює в будь-якому вузлі мережі, мав доступ до всіх цих баз даних як до єдиної бази даних .
При цьому повинні забезпечуватися:
простота використання системи;
можливості автономного функціонування при порушеннях зв'язності мережі або при адміністративних потребах;
високий ступінь ефективності.
Можливі однорідні і неоднорідні розподілені бази даних. В однорідному випадку кожна локальна база даних управляється однією і тією ж СУБД. У неоднорідної системі локальні бази даних можуть ставитися навіть до різних моделей даних. Мережева інтеграція неоднорідних баз даних - це актуальна, але дуже складна проблема. Багато рішень відомі на теоретичному рівні, але поки не вдається впоратися з головною проблемою - недостатньою ефективністю інтегрованих систем.
Розподілена система управління базами даних.
Легкість використання системи досягається за рахунок того, що користувачі БД (розробники прикладних програм і кінцеві користувачі) працюють в середовищі певної мови БД (наприклад, SQL). Система автоматично виявляє поточне місце розташування згадуються у запиті користувача об'єктів даних; одна й та ж прикладна програма, що включає пропозиції SQL, може бути виконана в різних вузлах мережі. При цьому в кожному вузлі мережі на етапі компіляції запиту вибирається найбільш оптимальний план виконання запиту у відповідності з розташуванням даних в розподіленій системі.
Забезпечення автономності вузлів мережі досягається за рахунок того, що кожна локальна база даних адмініструється незалежно від інших. Можливі автономне підключення нових користувачів, зміна версії автономної частини системи і т.д. Система спроектована таким чином, що в ній не потрібні централізовані служби іменування об'єктів або виявлення глухих кутів. В індивідуальних вузлах не потрібна наявність глобального знання про операції, що виконуються в інших вузлах мережі; робота з доступними базами даних може тривати при виході з ладу окремих вузлів мережі або ліній зв'язку.
Високий ступінь ефективності системи досягається за рахунок:
Виконанню запиту передує його компіляція.
Можливість переміщення видалених відносин в локальну базу даних.
4.ER - модель.
На використанні різновидів ER-моделі засновано більшість сучасних підходів до проектування баз даних (головним чином, реляційних). Модель була запропонована Ченом (Chen) в 1976 р. Моделювання предметної області базується на використанні графічних діаграм, що включають невелику кількість різнорідних компонентів. У зв'язку з наочністю подання концептуальних схем баз даних ER-моделі одержали широке поширення в системах CASE, що підтримують автоматизоване проектування реляційних баз даних. Основними поняттями ER-моделі є сутність, зв'язок і атрибут.
Сутність - це реальний або представляється об'єкт, інформація про який повинна зберігатися і бути доступна. У діаграмах ER-моделі сутність представляється у вигляді прямокутника, що містить ім'я сутності. При цьому ім'я сутності - це ім'я типу, а не деякого конкретного примірника цього типу. Для більшої виразності і кращого розуміння ім'я суті може супроводжуватися прикладами конкретних об'єктів цього типу. Кожен екземпляр суті повинен бути відрізнити від будь-якого іншого примірника тієї ж сутності.
Зв'язок - це графічно зображається асоціація, що встановлюється між двома сутностями. Ця асоціація завжди є бінарної і може існувати між двома різними сутностями або між сутністю і їй самій (рекурсивна зв'язок). У будь-якого зв'язку виділяються два кінці (відповідно до існуючої парою пов'язують сутностей), на кожному з яких вказується ім'я кінця зв'язку, ступінь кінця зв'язку (скільки екземплярів даної сутності зв'язується), обов'язковість зв'язку (тобто будь-який чи примірник даної суті повинен брати участь в зв'язку з цим). Зв'язок представляється у вигляді лінії, що зв'язує дві сутності або веде від суті до неї ж самої. При це в місці "стикування" зв'язку з сутністю використовуються трьох точковий вхід в прямокутник суті, якщо для цієї сутності в зв'язку можуть використовуватися багато (many) примірників суті, і однокрапкового вхід, якщо у зв'язку може брати участь тільки один екземпляр сутності. Обов'язковий кінець зв'язку зображається суцільною лінією, а необов'язковий - переривчастою лінією.
Атрибутом суті є будь-яка деталь, яка служить для уточнення, ідентифікації, класифікації, числової характеристики або вирази стану сутності. Імена атрибутів заносяться в прямокутник, що зображує сутність, під ім'ям сутності і зображуються малими літерами, можливо, з прикладами.
Нормальні форми ER-схем.
У першій нормальній формі ER-схеми усуваються повторювані атрибути або групи атрибутів, тобто проводиться виявлення неявних сутностей, "замаскованих" під атрибути.
У другій нормальній формі усуваються атрибути, які залежать тільки від частини унікального ідентифікатора. Ця частина унікального ідентифікатора визначає окрему сутність.
У третій нормальній формі усуваються атрибути, які залежать від атрибутів, що не входять в унікальний ідентифікатор. Ці атрибути є основою окремої сутності.
Більш складні елементи ER-моделі.
Підтипи і супертіпи сутностей. Як у мовах програмування з розвиненими типовими системами запроваджується можливість успадкування типу суті, виходячи з одного або декількох супертіпов.
Зв'язки "many-to-many". Іноді буває необхідно зв'язувати суті таким чином, що з обох кінців зв'язку можуть бути присутні кілька екземплярів сутності.
Уточнюємо ступеня зв'язку. Іноді буває корисно визначити можливу кількість примірників суті, беруть участь у даній зв'язку (наприклад, службовцю дозволяється брати участь не більше, ніж в трьох проектах одночасно). Для вираження цього семантичного обмеження дозволяється вказувати на кінці зв'язку її максимальну або обов'язкову ступінь.
Каскадні видалення екземплярів сутностей. Деякі зв'язку бувають настільки сильними (звичайно, у разі зв'язку "один-ко-многим"), що при видаленні опорного екземпляра сутності (відповідного кінця зв'язку "один") потрібно видалити і всі екземпляри суті, відповідні кінця зв'язку "багато".
Домени. Як і у випадку реляційної моделі даних буває, корисна можливість визначення потенційно допустимого безлічі значень атрибута сутності (домену).
21.Переход від ER - моделі до реляційної.
Кожна проста сутність перетворюється в таблицю. Проста сутність - сутність, яка не є підтипом і яка не має підтипів. Назва суті стає ім'ям таблиці.
Кожен атрибут стає можливим стовпцем з тим же ім'ям, може вибиратися більш точний формат. Стовпці, відповідні необов'язковим атрибутах, можуть містити невизначені значення; стовпці, що відповідають обов'язковим атрибутами, - не можуть.
Компоненти унікального ідентифікатора суті перетворюються на первинний ключ таблиці. Якщо є кілька можливих унікальних ідентифікаторів, вибирається найбільш використовуваний. Якщо до складу унікального ідентифікатора входять зв'язку, до числа стовпців первинного ключа додається копія унікального ідентифікатора сутності, яка знаходиться на далекому кінці зв'язку (цей процес може тривати рекурсивно). Для іменування цих стовпців використовуються імена решт зв'язків та/або імена сутностей.
Зв'язки багато-до-одного (і один-до-одного) стають зовнішніми ключами. Тобто робиться копія унікального ідентифікатора з кінця зв'язку "один", і відповідні стовпці складають зовнішній ключ. Необов'язкові зв'язку відповідають стовпцях, що допускають невизначені значення; обов'язкові зв'язку - стовпцях, що не допускає невизначені значення.
Індекси створюються для первинного ключа (унікальний індекс), зовнішніх ключів і тих атрибутів, на яких передбачається в основному базувати запити.
Якщо в концептуальній схемі були присутні підтипи, то можливі два способи: всі підтипи в одній таблиці (а) або для кожного підтипу - окрема таблиця (б). При застосуванні способу (а) таблиця створюється для найбільш зовнішнього супертіпа, а для підтипів можуть створюватися подання. До таблиці додається, принаймні, один стовпець, що містить код ТИПУ, він стає частиною первинного ключа. При використанні методу (б) для кожного підтипу першого рівня (для більш нижніх - подання) супертіп відтворюється за допомогою представлення UNION (з усіх таблиць підтипів вибираються загальні стовпці - стовпці супертіпа).
Є два способи роботи за наявності виключають зв'язків: загальний домен (а) і явні зовнішні ключі (б). Якщо залишаються зовнішні ключі все в одному домені, тобто мають загальний формат (спосіб (а)), то створюються два стовпця: ідентифікатор зв'язку та ідентифікатор сутності. Стовпець ідентифікатора зв'язку використовується для розрізнення зв'язків, що покриваються дугою виключення. Стовпець ідентифікатора суті використовується для зберігання значень унікального ідентифікатора суті на далекому кінці відповідної зв'язку. Якщо результуючі зовнішні ключі не відносяться до одного домену, то для кожного зв'язку, покривається дугою виключення, створюються явні стовпці зовнішніх ключів; всі ці стовпці можуть містити невизначені значення.
7,8. Ієрархічні системи.
Типовим представником (найбільш відомим і поширеним) є Information Management System (IMS) фірми IBM. Перша версія з'явилася в 1968 р. До цих пір підтримується багато баз даних, що створює суттєві проблеми з переходом, як на нову технологію БД, так і на нову техніку.
Ієрархічна БД складається з упорядкованого набору дерев; більш точно, з упорядкованого набору декількох екземплярів одного типу дерева. Тип дерева складається з одного "кореневого" типу запису і впорядкованого набору з нуля або більше типів піддерев (кожне з яких є певним типом дерева). Тип дерева в цілому являє собою ієрархічно організований набір типів запису. У IMS використовувалася оригінальна і нестандартна термінологія: "сегмент" замість "запис", а під "записом БД" розумілося все дерево сегментів.
Всі екземпляри даного типу нащадка із загальним екземпляром типу предка називаються близнюками. Для БД визначений повний порядок обходу - зверху вниз, зліва направо.
Маніпулювання даними.
Знайти вказане дерево БД (наприклад, відділ 310);
Перейти з одного дерева до іншого;
Перейти від одного запису до іншого всередині дерева (наприклад, від відділу - до першого співробітникові);
Перейти від одного запису до іншої в порядку обходу ієрархії;
Вставити новий запис у вказану позицію;
Видалити поточний запис.
Обмеження цілісності.
Автоматично підтримується цілісність посилань між предками і нащадками. Основне правило: ніякої нащадок не може існувати без свого батька. Зауважимо, що аналогічне підтримку цілісності за посиланнями між записами, що не входять в одну ієрархію, не підтримується
В ієрархічних системах підтримувалася деяка форма уявлень БД на основі обмеження ієрархії.
9,10. Мережеві системи.
Типовим представником є Integrated Database Management System (IDMS) компанії Cullinet Software, Inc., призначена для використання на машинах основного класу фірми IBM по?? управлінням більшості операційних систем. Архітектура системи заснована на пропозиціях Data Base Task Group (DBTG) Комітету з мов програмування Conference on Data Systems Languages (CODASYL), організації, відповідальної за визначення мови програмування Кобол. Звіт DBTG був опублікований в 1971 р., а в 70-х роках з'явилося кілька систем, серед яких IDMS.
Мережевий підхід до організації даних є розширенням ієрархічного. В ієрархічних структурах запис-нащадок повинна мати в точності одного предка; в мережевій структурі даних нащадок може мати будь-яке число предків. Мережева БД складається з набору записів та набору зв'язків між цими записами, а якщо говорити більш точно, з набору екземплярів кожного типу із заданого в схемі БД набору типів запису і набору екземплярів кожного типу із заданого набору типів зв'язку. Тип зв'язку визначається для двох типів запису: предка і нащадка. Примірник типу зв'язку складається з одного примірника типу запису предка і впорядкованого набору екземплярів типу запису нащадка. Для даного типу зв'язку L з типом запису предка P і типом запису нащадка C повинні виконуватися наступні дві умови:
Кожен екземпляр типу P є предком тільки в одному екземплярі L;
Кожен екземпляр C є нащадком не більше, ніж в одному примірнику L.
На формування типів зв'язку не накладаються особливі обмеження, але можливі, наприклад, такі ситуації:
Тип запису нащадка в одному типі зв'язку L1 може бути типом запису предка в іншому типі зв'язку L2 (як в ієрархії).
Даний тип запису P може бути типом запису предка в будь-якій кількості типів зв'язку.
Даний тип запису P може бути типом запису нащадка в будь-якій кількості типів зв'язку.
Може існувати будь-яке число типів зв'язку з одним і тим же типом запису предка і одним і тим же типом запису нащадка, і якщо L1 і L2 - два типи зв'язку з одним і тим же типом запису предка P і одним і тим же типом запису нащадка C, то правила, за якими утворюється споріднення, у різних зв'язках можуть відрізнятися.
Типи запису X та Y можуть бути предком і нащадком в одній зв'язку і нащадком і предком - в іншій.
Предок і нащадок можуть бути одного типу запису.
Маніпулювання даними.
Знайти певний запис в наборі однотипних записів (інженера Сидорова);
Перейти від предка до першого нащадку за деякою зв'язку (до першого співробітнику відділу 310);
Перейти до наступного нащадку у деякому зв'язку (від Сидорова до Іванова);
Перейти від нащадка до предка за деякою зв'язку (знайти відділ Сидорова);
Створити нову запис;
Знищити запис;
Змінити запис;
Включити в зв'язок;
Виключити з зв'язку;
переставити в інший зв'язок і т.д.
Обмеження цілісності.
В принципі їх підтримку не потрібно, але іноді вимагають цілісності за посиланнями (як в ієрархічній моделі).
11,12. Загальні поняття реляційного підходу до організації БД.
Основними поняттями реляційних баз даних є тип даних, домен, атрибут, кортеж, первинний ключ і ставлення.
Тип даних.
Поняття тип даних в реляційної моделі даних цілком адекватно поняттю типу даних в мовах програмування. Зазвичай в сучасних реляційних БД допускається зберігання символьних, числових даних, бітових рядків, спеціалізованих числових даних (таких як "гроші"), а також спеціальних "темпоральних" даних (дата, час, часовий інтервал). Досить активно розвивається підхід до розширення можливостей реляційних систем абстрактними типами даних.
Домен.
Поняття домену більш специфічно для баз даних, хоча і має деякі аналогії з підтипами в деяких мовах програмування. У самому загальному вигляді домен визначається завданням деякого базового типу даних, до якого відносяться елементи домену, і довільного логічного виразу, який застосовується до елемента типу даних. Якщо обчислення цього логічного виразу дає результат "істина", то елемент даних є елементом домену. Найбільш правильною інтуїтивною трактуванням поняття домену є розуміння домену як допустимого потенційного безлічі значень даного типу.
Схема відносини, схема бази даних.
Схема відносини - це іменоване безліч пар (ім'я атрибуту, ім'я домену (або типу, якщо поняття домену не підтримується)). Ступінь або "арность" схеми відносини - потужність цієї множини. Схема БД (в структурному сенсі) - це набір іменованих схем відносин.
Кортеж, ставлення.
Кортеж, що відповідає даній схемі відносини, - це безліч пар (ім'я атрибуту, значення), яке містить одне входження кожного імені атрибута, що належить схемі відносини. "Значення" є припустимим значенням домену даного атрибуту (або типу даних, якщо поняття домену не підтримується). Тим самим, ступінь або "арность" кортежу, тобто число елементів у ньому, співпадає з "арность" відповідної схеми відносини. Просто кажучи, кортеж - це набір іменованих значень заданого типу. Ставлення - це безліч кортежів, які відповідають одній схемі відносини. Іноді, щоб не плутатися, говорять "ставлення-схема" і "ставлення-екземпляр", іноді, схему, відносини називають заголовком відносини, а відношення як набір кортежів - тілом відносини.
Загальна характеристика.
Найбільш поширена трактування реляційної моделі даних, очевидно, належить Дейта, який відтворює її (з різними уточненнями) практично у всіх своїх книгах. Згідно Дейта реляційна модель складається з трьох частин, що описують різні аспекти реляційного підходу: структурної частини, маніпуляційної частини і цілісної частини.
У структурної частини моделі фіксується, що єдиною структурою даних, що використовується в реляційних БД, є нормалізоване n-арное ставлення. По суті справи, в попередніх двох розділах цієї лекції ми розглядали саме поняття і властивості структурної складової реляційної моделі.
У маніпуляційної частині моделі затверджуються два фундаментальних механізму маніпулювання реляційними БД - реляційна алгебра і реляційне числення. Перший механізм базується в основному на класичній теорії множин (з деякими уточненнями), а другий - на класичному логічному апараті обчислення предикатів першого порядку. Ми розглянемо ці механізми детальніше на наступній лекції, а поки що лише зауважимо, що основною функцією маніпуляційної частини реляційної моделі є забезпечення заходів реляційної будь-якого конкретного мови реляційних БД: мова називається реляційних, якщо він має не меншою виразністю і потужністю, ніж реляційна алгебра або реляційне числення.
Цілісність суті і посилань.
У цілісної частини реляційної моделі даних фіксуються два базові вимоги цілісності, які повинні підтримуватися в будь-який реляційної СУБД. Перша вимога називається вимогою цілісності сутностей. Об'єкту або сутності реального світу в реляційних БД відповідають кортежі відносин. Конкретно вимога полягає в тому, що будь-який кортеж будь-якого відношення відрізнити від будь-якого іншого кортежу цього відношення, тобто іншими словами, будь-яке відношення має володіти первинним ключем.
Друга вимога називається вимогою цілісності за посиланнями. При дотриманні нормалізованності відносин складні сутності реального світу представляються в реляційної БД у вигляді декількох кортежів декількох відносин. Атрибут називається зовнішнім ключем, його значення однозначно характеризують суті, представлені кортежами деякого іншого відносини (тобто описують їх первинного ключа). Кажуть, що ставлення, в якому визначено зовнішній ключ, посилається на відповідне відношення, в якому такий же атрибут є первинним ключем. Вимога цілісності по посиланнях, або вимога зовнішнього ключа полягає в тому, що для кожного значення зовнішнього ключа, що з'являється в посилається відношенні, у відношенні, на яку веде посилання, повинен знайтися кортеж з таким же значенням первинного ключа, або значення зовнішнього ключа повинно бути невизначеним (тобто ні на що не вказувати).
Обмеження цілісності суті і за посиланнями повинні підтримуватися СУБД. Для дотримання цілісності суті досить гарантувати відсутність в будь-якому відношенні кортежів з одним і тим же значенням первинного ключа.
Існують три підходи, кожен з яких підтримує цілісність за посиланнями. Перший підхід полягає в тому, що забороняється проводити видалення кортежу, на який існують посилання (тобто спочатку потрібно або видалити що мають посилання кортежі, або відповідним чином змінити значення їх зовнішнього ключа). При другому підході при видаленні кортежу, на який є посилання, у всіх що посилаються кортежу значення зовнішнього ключа автоматично стає невизначеним. Нарешті, третій підхід (каскадне видалення) полягає в тому, що при видаленні кортежу з відносини, на яку веде посилання, з посилається відносини автоматично видаляються всі мають посилання кортежі.
14.B - дерево.
Мабуть, найбільш популярним підходом до організації індексів у базах даних є використання техніки B-дерев. З точки зору зовнішнього логічного представлення B-дерево - це збалансоване сильно зелене дерево, у зовнішній пам'яті. Збалансованість означає, що довжина шляху від кореня дерева до будь-якого його листу одна й та ж. Гіллястість дерева - це властивість кожного вузла дерева посилатися, але велика кількість вузлів-нащадків. З точки зору фізичної організації B-дерево представляється як мультіспісочная структура сторінок зовнішньої пам'яті, тобто кожному вузлу дерева відповідає блок зовнішньої пам'яті (сторінка). Внутрішні і листові сторінки часто мають різну структуру.
При цьому витримуються наступні властивості:
ключ (1) <= ключ (2) <= ... <= ключ (n);
в сторінці дерева Nm знаходяться ключі k зі значеннями ключ (m) <= k <= ключ (m +1).
Листова сторінка володіє наступними властивостями:
ключ (1) <ключ (2) <... <ключ (t);
сп (r) - упорядкований список ідентифікаторів кортежів (tid), що включають значення ключ (r);
листові сторінки пов'язані одно-або двонаправленим списком.
Пошук в B-дереві - це проходження від кореня до листа у відповідності до заданих значень ключа. Зауважимо, що оскільки дерева сильно гіллясті і збалансовані, то для виконання пошуку по будь-якому значенню ключа буде потрібно одне й те саме (і звичайно невелике) число обмінів із зовнішньою пам'яттю. Більш точно, в збалансованому дереві, де довжини всіх шляхів від кореня до листа одні й ті ж, якщо у внутрішній сторінці поміщається n ключів, то при зберіганні m записів потрібно дерево глибиною logn (m), де logn обчислює логарифм за основою n. Якщо n досить велике (звичайний випадок), то глибина дерева невелика, і формується швидкий пошук. Основною "родзинкою" B-дерев є автоматична підтримка властивості збалансованості. Розглянемо, як це робиться при виконанні операцій занесення та видалення записів. При занесення нового запису виконується:
Пошук листовий сторінки. Фактично, проводиться звичайний пошук по ключу. Якщо в B-дереві не міститься ключ до заданих значень, то буде отриманий номер сторінки, в якій йому належить утримуватися, і відповідні координати всередині сторінки.
Приміщення запису на місце. Природно, що вся робота проводиться в буферах оперативної пам'яті. Листова сторінка, у яку потрібно занести запис, зчитується в буфер, і в ньому виконується операція вставки. Розмір буфера повинен перевищувати розмір сторінки зовнішньої пам'яті.
Якщо після виконання вставки нового запису розмір використовуваної частини буфера не перевищує розміру сторінки, то на цьому виконання операції занесення запису закінчується. Буфер може бути негайно виштовхнутий в зовнішню пам'ять, або тимчасово збережений в оперативній пам'яті в залежності від політики управління буферами.
Якщо ж виникло переповнення буферу (тобто розмір його використовуваної частини перевершує розмір сторінки), то виконується розщеплення сторінки. Для цього запитується нова сторінка зовнішньої пам'яті, що використовується частина буфера розбивається, грубо кажучи, навпіл (так, щоб друга половина також починалася з ключа), і друга половина записується у знову виділену сторінку, а в старій сторінці модифікується значення розміру вільної пам'яті. Природно, модифікуються посилання за списком листових сторінок.
Щоб забезпечити доступ від кореня дерева до заново заведеної сторінки, необхідно відповідним чином модифіковані внутрішню сторінку, яка є предком раніше існуючої листовий сторінки, тобто вставити в неї відповідне значення ключа і посилання на нову сторінку. При виконанні цієї дії може знову статися переповнення тепер уже внутрішньої сторінки, і вона буде розщеплена на два. У результаті буде потрібно вставити значення ключа і посилання на нову сторінку у внутрішню сторінку-предка вище по ієрархії і т.д.
Граничним випадком є переповнення кореневої сторінки B-дерева. У цьому випадку вона теж розщеплюється на два, і заводиться нова коренева сторінка дерева, тобто його глибина, збільшується на одиницю.
При видаленні запису виконуються наступні дії:
Пошук запису по ключу. Якщо запис не знайдено, то значить видаляти нічого не потрібно.
Реальне видалення записи в буфері, в який прочитана відповідна листова сторінка.
Якщо після виконання цієї подопераціі розмір зайнятої в буфері області виявляється таким, що його сума з розміром зайнятої області у листових сторінках, що є лівим чи правим братом цієї сторінки, більше, ніж розмір сторінки, операція завершується.
Інакше виробляється злиття з правим або лівим братом, тобто в буфері проводиться новий образ сторінки, що містить загальну інформацію з даної сторінки та її лівого або правого брата. Стала вже непотрібною листова сторінка заноситься в список вільних сторінок. Відповідним чином коригується список листових сторінок.
Щоб усунути можливість доступу від кореня до звільненої сторінці, потрібно видалити відповідне значення ключа і посилання на звільнену сторінку з внутрішньої сторінки - її предка. При цьому може виникнути потреба в злитті цієї сторінки з її лівим або правими братами і т.д.
Граничним випадком є повне спустошення кореневої сторінки дерева, яке можливе після злиття двох останніх нащадків кореня. У цьому випадку коренева сторінка звільняється, а глибина дерева зменшується на одиницю.
Проблемою є те, що при виконанні операцій модифікації дуже часто можуть виникати розщеплення і злиття. Для ефективного використання зовнішньої пам'яті з мінімізацією числа розщепленні і злиття, застосовуються більш складні прийоми, в тому числі:
попереджувальні розщеплення, тобто розщеплення сторінки не при її переповнення, а трохи раніше, коли ступінь заповнювання сторінки досягає певного рівня;
переливання, тобто підтримка рівноважного заповнення сусідніх сторінок;
злиття 3-в-2, тобто породження двох листових сторінок на основі вмісту трьох сусідніх.
15.Хешірованіе.
Альтернативним і все більш популярним підходом до організації індексів є використання техніки хешування. Це дуже велика тема, яка заслуговує окремого розгляду. Ми обмежимося лише декількома зауваженнями. Загальною ідеєю методів хешування є застосування до значення ключа деякої функції згортки (хеш-функції), що виробляє значення меншого розміру. Згортка значення ключа потім використовується для доступу до запису.
У самому простому, класичний випадок, згортка ключа використовується як адреса в таблиці, що містить ключі і запису. Основною вимогою до хеш-функції є рівномірний розподіл значення пакунки. У разі виникнення колізій (одна й та ж згортка для декількох значень ключа) утворюються ланцюжки переповнення. Головним обмеженням цього методу є фіксований розмір таблиці. Якщо таблиця заповнена занадто сильно або переповнена, але виникне занадто багато ланцюжків переповнення, і головна перевага хешування - доступ до запису майже завжди за одне звернення до таблиці - буде втрачено. Розширення таблиці вимагає її
повної переробки на основі нової хеш-функції (зі значенням згортки більшого розміру). У випадку баз даних такі дії є абсолютно неприйнятними. Тому зазвичай вводять проміжні таблиці-довідники, що містять значення ключів і адреси записів, а самі записи зберігаються окремо. Тоді при переповнення довідника потрібно тільки його переробка, що викликає менше накладних витрат.
Щоб уникнути потреби в повної переробки довідників, при їх організації часто використовують техніку B-дерев з розщеплення і злиттями. Хеш-функція при цьому змінюється динамічно, залежно від глибини B-дерева. Шляхом додаткових технічних хитрощів вдається домогтися збереження порядку записів у відповідності до значень ключа. У цілому методи B-дерев і хешування все більше зближуються.
16, 17.Реляціонная алгебра.
Основна ідея реляційної алгебри полягає в тому, що коли незабаром відносини є множинами, то кошти маніпулювання відносинами можуть базуватися на традиційних теоретико-множинних операціях, доповнених деякими спеціальними операціями, специфічними для баз даних.
Використовується трохи розширений початковий варіант алгебри, який був запропонований Коддом. У цьому варіанті набір основних алгебраїчних операцій складається з восьми операцій, які діляться на два класи - теоретико-множинні операції та спеціальні реляційні операції. До складу теоретико-множинних операцій входять операції:
об'єднання відносин;
перетину відносин;
взяття різниці відносин;
прямого твори відносин.
Спеціальні реляційні операції включають:
обмеження відносини;
проекцію відносини;
підключення відносин;
поділ відносин.
Крім того, до складу алгебри включається операція присвоювання, що дозволяє зберегти в базі даних результати обчислення алгебраїчних виразів, і операція перейменування атрибутів, що дає можливість коректно сформувати заголовок (схему) результуючого відносини.
Загальна інтерпретація реляційних операцій.
При виконанні операції об'єднання двох відносин проводиться ставлення, що включає всі кортежі, що входять хоча б у одне з відносин-операндів.
Операція перетину двох відносин виробляє ставлення, що включає всі кортежі, що входять в обидва відносини-операнда.
Відношення, яке є різницею двох відносин включає всі кортежі, що входять у відношення - перший операнд, такі, що жоден з них не входить до відношення, яке є другим операндом.
При виконанні прямого твори двох відносин проводиться ставлення, кортежі якого є конкатенації (зчепленням) кортежів перших і других операндів.
Результатом обмеження відносини по деякому умовою є відношення, що включає кортежі відносини-операнда, що задовольняє цій умові.
При виконанні проекції відносини на заданий набір його атрибутів проводиться ставлення, кортежі якого виробляються шляхом знаходження відповідних значень з кортежів відносини-операнда.
При з'єднанні двох відносин по деякому умові утворюється результуюче ставлення, кортежі якого є конкатенації кортежів першого і другого відносин і задовольняють цій умові.
У операції реляційного поділу два операнда - бінарне і Унарне відносини. Результуюче відношення складається з одно-атрібутних кортежів, що включають значення першо
