Реляційні бази данихдозволяють зберігати інформацію в декількох «плоських» (двовимірних) таблицях, пов'язаних між собою за допомогою полів даних, що спільно використовуються, званих ключами. Реляційні бази даних надають більш простий доступ до звітів, що оперативно складаються (зазвичай через SQL) і забезпечують підвищену надійність і цілісність даних завдяки відсутності надлишкової інформації

Всім відомо, що є простою базою даних: телефонні довідники, каталоги товарів і словники - все це бази даних. Вони можуть бути структурованими чи організованими іншим чином: як плоскі файли, як ієрархічні чи мережеві структури чи як реляційні таблиці. Найчастіше в організаціях зберігання інформації використовуються саме реляційні бази даних.

База даних - це набір таблиць, які з стовпців і рядків, аналогічно електронної таблиці. Кожен рядок містить один запис; кожен стовпець містить усі екземпляри конкретного фрагмента даних усіх рядків. Наприклад, звичайний телефонний довідник складається зі стовпців, які містять телефонні номери, імена абонентів та адреси абонентів. Кожен рядок містить номер, ім'я та адресу. Ця проста форма називається плоским файлом через його двомірної природи, і навіть те, що це дані зберігаються у одному файлі.

В ідеалі, кожна база даних має принаймні один стовпець з унікальним ідентифікатором, або ключем. Розглянемо телефонну книгу. У ній може бути кілька записів з абонентом Джоном Смітом, але жоден з телефонних номерів не повторюється. Телефонний номер і є ключем.

Насправді, все не так просто. Дві або кілька осіб, які використовують один і той же телефонний номер, можуть бути перераховані в телефонному довіднику окремо, внаслідок чого телефонний номер з'являється у двох або більше місцях, тому існує кілька рядків із ключами, які не є унікальними.

Дані створюють проблеми

У найпростіших базах даних кожен запис займає один рядок, іншими словами телефонної компанії необхідно заводити окремий стовпець для кожного фрагмента бухгалтерської інформації. Тобто одну – для другого абонента «спареного» телефону, ще одну – для третього тощо, залежно від того, скільки додаткових абонентів знадобиться.

Це означає, що кожен запис у базі даних повинен мати всі ці додаткові колонки, навіть якщо вони більше ніде не використовуються. Це також означає, що база даних повинна бути реорганізована щоразу, коли компанія пропонує нову послугу. Вводиться обслуговування тонального набору і змінюється структура бази, оскільки додається нова колонка. Вводиться підтримка ідентифікації номера абонента, очікування дзвінка тощо - і база даних перебудовується знову і знову.

У 60-ті роки тільки найбільші компанії могли дозволити собі купувати комп'ютери для керування своїми даними. Більш того, бази даних, побудовані на статичних моделях даних та за допомогою процедурних мов програмування, таких як Кобол, можуть виявитися надто дорогими в тому, що стосується підтримки, і не завжди надійними. Процедурні мови визначають послідовність подій, через які комп'ютер повинен пройти, щоб виконати завдання. Програмування таких послідовностей було складною справою, особливо якщо потрібно змінити структуру бази даних або складати новий вид звітів.

Потужні зв'язки

Едгар Кодд, співробітник дослідницької лабораторії корпорації IBM у Сан-Хосе, по суті, створив і описав концепцію реляційних баз даних у своїй основній роботі «Реляційна модель для великих банків даних, що спільно використовуються» (A Relational Model of Data for Large Shared Data Banks). Communications of the ACM, червень 1970).

Кодд запропонував модель, яка дозволяє розробникам розділяти свої бази даних на окремі, але взаємопов'язані таблиці, що збільшує продуктивність, але при цьому зовнішнє уявлення залишається тим самим, що й у вихідної бази даних. З того часу Кодд вважається батьком-засновником галузі реляційних баз даних.

Ця модель працює в такий спосіб. Телефонна компанія може створити основну таблицю, використовуючи як первинний ключ номер телефону, та зберігати його з іншою базовою інформацією про споживачів. Компанія може визначити окрему таблицю зі стовпцями для цього первинного ключа та для додаткових служб, таких як підтримка ідентифікації номера абонента та очікування дзвінка. Вона також може створити ще одну таблицю для контролю рахунків за переговори, де кожен запис складається з номера телефону та даних про оплату дзвінків.

Кінцеві користувачі можуть легко отримати інформацію, яку вони хочуть, і в тому вигляді, в якому вона їм потрібна, хоча ці дані зберігаються в різних таблицях. Тому представник служби підтримки споживачів телефонної компанії може відобразити на тому самому екрані інформацію про рахунки абонента, а також про стан спеціальних служб або про те, коли була отримана остання оплата.

Кодд сформулював 12 правил для реляційних баз даних, більшість яких стосуються цілісності та оновлення даних, а також доступу до них. Перші два досить зрозумілі навіть користувачам, які не мають технічних навичок.

Правило 1, інформаційне правило, показує, що вся інформація в реляційній базі даних представляється як набір значень, що зберігаються в таблицях.

Правило 2, правило гарантії доступу, визначає, що доступ до кожного елемента даних у реляційній базі даних можна отримати за допомогою імені таблиці, первинного ключа та назви стовпця. Іншими словами, всі дані зберігаються в таблицях, і, якщо відома назва таблиці, первинний ключ і стовпець, де знаходиться необхідний елемент даних, його можна витягти.

Суть роботи Кодда в тому, що пропонувалося з реляційними базами даних використовувати декларативні, а чи не процедурні мови програмування. Декларативні мови, такі як мова запитів SQL (Structured Query Language), дають користувачам можливість, по суті, повідомити комп'ютер: «Я хочу отримати наступні біти даних з усіх записів, які задовольняють певний набір критеріїв». Комп'ютер сам «зрозуміє», які кроки необхідно зробити, щоб отримати цю інформацію з бази даних.

Для роботи з величезною кількістю баз даних, що активно використовуються, застосовуються програмні системи управління реляційними базами даних, створені такими авторитетними виробниками, як Oracle, Sybase, IBM, Informix і Microsoft.

Хоча більшу частину варіантів реалізацій SQL можна назвати інтероперабельними лише з відомим наближенням, цей затверджений як міжнародний стандарт механізм дозволяє створювати складні системи, основу яких складають бази даних. Зручний для програмування інтерфейс між Web-сайтами та реляційними базами даних дає кінцевим користувачам можливість додавати нові записи та оновлювати існуючі, а також створювати звіти для різних служб, таких як виконання інтерактивних торгових операцій та доступ до інтерактивних бібліотечних каталогів.

Реляційна модель

Реляційна база даних використовує набір таблиць, пов'язаних один з одним за допомогою певного ключа (у цьому випадку це поле PhoneNumber)

База даних (БД) -це названа сукупність структурованих даних, що відносяться до певної предметної області і призначених для зберігання, накопичення та обробки за допомогою ЕОМ.

Реляційна база даних (РБД)- це набір відносин, імена яких збігаються з іменами схем відносин у схемі БД.

Основні поняттяреляційних баз даних:

· Тип даних- Тип значень конкретного стовпця.

· Домен(domain) – безліч всіх допустимих значень атрибуту.

· Атрибут(attribute) – заголовок стовпця таблиці, що характеризує названу властивість об'єкта, наприклад, прізвище студента, дата оформлення замовлення, стать співробітника і т.п.

· Кортеж- Рядок таблиці, що являє собою сукупність значень логічно пов'язаних атрибутів.

· Ставлення(relation) - таблиця, що відображає інформацію про об'єкти реального світу, наприклад, про студентів, замовлення, співробітників, жителів і т.д.

· Первинний ключ(primary key) – поле (або набір полів) таблиці, що однозначно ідентифікує кожну з її записів.

· Альтернативний ключ– це поле (або набір полів), що не співпадає з первинним ключем та унікально ідентифікує екземпляр запису.

· Зовнішній ключ– це поле (або набір полів), чиї значення збігаються з значеннями первинного ключа іншої таблиці. При зв'язку двох таблиць із первинним ключем першої таблиці зв'язується зовнішній ключ другої таблиці.

· Реляційна модель даних (РМД)- Організація даних у вигляді двовимірних таблиць.

Кожна реляційна таблиця повинна мати такі властивості:

1. Кожен запис таблиці унікальна, тобто. сукупність значень по полях не повторюється.

2. Кожне значення записується на перетині рядка і стовпця - є атомарним (нерозділним).

3. Значення кожного поля мають бути одного типу.

4. Кожне поле має унікальне ім'я.

5. Порядок розташування записів неістотний.

Основні елементи БД:

Поле- Елементарна одиниця логічної організації даних. Для опису поля використовуються такі характеристики:

· Ім'я, наприклад, Прізвище, Ім'я, По батькові, Дата народження;

· Тип, наприклад, рядковий, символьний, числовий, датовий;

· Довжина, наприклад, в байтах;

· Точність для числових даних, наприклад, два десяткові знаки для відображення дробової частини числа.

Запис- Сукупність значень логічно пов'язаних полів.

Індекс– засіб прискорення операції пошуку записів, що використовується встановлення зв'язків між таблицями. Таблиця, для якої використовується індекс, називають індексованою. p align="justify"> При роботі з індексами необхідно звертати увагу на організацію індексів, що є основою для класифікації. Простий індекс представлений одним полем або логічним виразом, що обробляє одне поле. Складовий індекс подано кількома полями з можливістю використання різних функцій. Індекси таблиці зберігаються у індексному файлі.

Цілісність даних- Це засіб захисту даних по полях зв'язку, що дозволяє підтримувати таблиці в узгодженому (несуперечливому) стані (тобто не допускає існування в підпорядкованій таблиці записів, що не мають відповідних записів у батьківській таблиці).

Запит- Сформульоване питання до однієї або кількох взаємопов'язаних таблиць, що містить критерії вибірки даних. Запит здійснюється за допомогою структурованої мови запитів SQL (Srtructured Query Language). В результаті вибірки даних з однієї або декількох таблиць може бути отримано безліч записів, що називають поданням.

Подання даних- Зберігається в базі даних іменований запит на вибірку даних (з однієї або декількох таблиць).

Подання по суті є тимчасовою таблицею, що формується в результаті виконання запиту. Сам запит може бути направлений до окремого файлу, звіту, тимчасової таблиці, таблиці на диску тощо.

Звіт– компонент системи, основне призначення якого – опис та виведення на друк документів на основі інформації з БД.

Загальна характеристика роботи з РБД:

Найбільш поширене трактування реляційної моделі даних, мабуть, належить Дейту, який відтворює її (з різними уточненнями) практично у всіх своїх книгах. Згідно з Дейтом реляційна модель складається з трьох частин, що описують різні аспекти реляційного підходу: структурної частини, маніпуляційної частини та цілісної частини.

У структурній частині моделі фіксується, що єдиною структурою даних, що використовується в реляційних БД, є нормалізоване n-арне відношення.

У маніпуляційній частині моделі затверджуються два фундаментальні механізми маніпулювання реляційними БД – реляційна алгебра та реляційне обчислення. Перший механізм базується переважно на класичної теорії множин (з деякими уточненнями), а другий - на класичному логічному апараті обчислення предикатів першого порядку. Зауважимо, що основною функцією маніпуляційної частини реляційної моделі є забезпечення міри реляційності будь-якої конкретної мови реляційних БД: мова називається реляційною, якщо вона має не меншу виразність і потужність, ніж реляційна алгебра або реляційне обчислення.

28. АЛГОРИТМІЧНІ МОВИ. ТРАНСЛЯТОРИ (ІНТЕРПРЕТАТОРИ І КОМПІЛЯТОРИ). АЛГОРИТМІЧНА МОВА БЕЙСИК. СТРУКТУРА ПРОГРАМИ. ІДЕНТИФІКАТОРИ. ЗМІННІ. ОПЕРАТОРИ. ОБРОБКА ОДНОМІРНИХ І ДВОМІРНИХ МАСИВІВ. ФУНКЦІЇ КОРИСТУВАЧА. ПІДПРОГРАМИ. РОБОТА З ФАЙЛАМИ ДАНИХ.

Мова високого рівня- мова програмування, поняття та структура якого зручні для сприйняття людиною.

Алгоритмічна мова(Algorithmic language) - мова програмування - штучна (формальна) мова, призначена для запису алгоритмів. Мова програмування задається своїм описом та реалізується у вигляді спеціальної програми: компілятора чи інтерпретатора. Прикладами алгоритмічних мов є Borland Pascal, C++, Basic і т.д.

Основні поняття алгоритмічної мови:

Склад мови:

Звичайна розмовна мова складається з чотирьох основних елементів: символів, слів, словосполучень та речень. Алгоритмічна мова містить подібні елементи, тільки слова називають елементарними конструкціями, словосполучення – виразами, речення – операторами.

Символи, елементарні конструкції, вирази та оператори становлять ієрархічну структуру, оскільки елементарні конструкції утворюються з послідовності символів.

Вирази- це послідовність елементарних конструкцій та символів,

Оператор- послідовність виразів, елементарних конструкцій та символів.

Опис мови:

Опис символів полягає у перерахуванні допустимих символів мови. Під описом елементарних конструкцій розуміють правила освіти. Опис виразів - це правила освіти будь-яких виразів, що мають сенс у цій мові. Опис операторів складається з всіх типів операторів, допустимих у мові. Опис кожного елемента мови задається його СИНТАКСИСОМ та СЕМАНТИКОЮ.

СинтаксичніВизначення встановлюють правила побудови елементів мови.

Семантикавизначає зміст і правила використання тих елементів мови, котрим були дані синтаксичні визначення.

Символи мови- це основні неподільні знаки, терміни яких пишуться всі тексти мовою.

Елементарні конструкції- це мінімальні одиниці мови, які мають самостійне значення. Вони утворюються із основних символів мови.

Виразв алгоритмічній мові складається з елементарних конструкцій та символів, воно задає правило обчислення деякого значення.

Операторзадає повний опис деякої дії, яку необхідно виконати. Для опису складної дії може знадобитися група операторів.

У цьому випадку оператори об'єднуються в Складовий операторабо Блок. Дії, задані операторами, виконуються над даними. Пропозиції алгоритмічної мови, в яких даються відомості про типи даних, називаються описами або операторами, що не виконуються. Об'єднана єдиним алгоритмом сукупність описів та операторів утворює програму алгоритмічною мовою. У процесі вивчення алгоритмічного мови необхідно відрізняти алгоритмічний мову від мови, з допомогою якого здійснюється опис досліджуваного алгоритмічного мови. Зазвичай мову, що вивчається називають просто мовою, а мова, в термінах якої дається опис мови, що вивчається - Метамовою.

Транслятори - (англ. translator – перекладач) – це програма-перекладач. Вона перетворює програму, написану однією з мов високого рівня, на програму, що складається з машинних команд.

Програма, написана якоюсь алгоритмічною мовою високого рівня, не може бути безпосередньо виконана на ЕОМ. ЕОМ розуміє лише мову машинних команд. Отже, програма алгоритмічною мовою повинна бути перекладена (трансльована) мовою команд конкретної ЕОМ. Такий переклад здійснюється автоматично спеціальними програмами-трансляторами, що створюються для кожної алгоритмічної мови та для кожного типу комп'ютерів.

Існують два основні способи трансляції - компіляція та інтерпретація.

1.Компіляція: Компілятор(англ. compiler - укладач, збирач) читає всю програму цілком, робить її переклад і створює закінчений варіант програми машинною мовою, який потім і виконується.

При компіляціївся вихідна програма відразу перетворюється на послідовність машинних команд. Після цього отримана результуюча програма виконується ЕОМ з вихідними даними. Перевага такого способу полягає в тому, що трансляція виконується один раз, а (багаторазове) виконання результуючої програми може здійснюватися з великою швидкістю. Разом з тим, результуюча програма може зайняти в пам'яті ЕОМ дуже багато місця, оскільки один оператор мови при трансляції замінюється сотнями або навіть тисячами команд. Крім того, налагодження та видозміни трансльованої програми дуже утруднені.

2. Інтерпретація: Інтерпретатор(англ. interpreter - тлумач, усний перекладач) перекладає та виконує програму рядок за рядком.

При інтерпретаціївихідна програма зберігається у пам'яті ЕОМ майже у постійному вигляді. Програма-інтерпретатор декодує оператори вихідної програми по одному і відразу забезпечує їх виконання з наявними даними. Інтерпретована програма займає в пам'яті комп'ютера мало місця, її легко налагоджувати та видозмінювати. Проте виконання програми відбувається досить повільно, оскільки при кожному виконанні заново здійснюється почергова інтерпретація всіх операторів.

Відкомпільовані програми працюють швидше, але інтерпретовані простіше виправляти та змінювати

Кожна конкретна мова орієнтована або на компіляцію, або на інтерпретацію - в залежності від того, для яких цілей він створювався. Наприклад, Паскаль зазвичай використовується на вирішення досить складних завдань, у яких важлива швидкість роботи програм. Тому ця мова зазвичай реалізується за допомогою компілятора.

З іншого боку, Бейсік створювався як мова для програмістів-початківців, для яких строкове виконання програми має незаперечні переваги.

Іноді однієї мови є і компілятор, і інтерпретатор. У цьому випадку для розробки та тестування програми можна скористатися інтерпретатором, а потім відкомпілювати налагоджену програму, щоб підвищити швидкість виконання.

• Переклад

Примітка перекладача: хоч стаття досить стара (опублікована 2 роки тому) і носить гучну назву, в ній все ж таки дається гарне уявлення про відмінності реляційних БД і NoSQL БД, їх переваги і недоліки, а також наводиться короткий огляд нереляційних сховищ.

Останнім часом з'явилося багато нереляційних баз даних. Це говорить про те, що якщо вам потрібна практично необмежена масштабованість на вимогу, вам потрібна нереляційна база даних.

Якщо це правда, чи це означає, що могутні реляційні БД стали вразливими? Чи означає це, що дні реляційних БД минають і незабаром пройдуть? У цій статті ми розглянемо популярний перебіг нереляційних баз даних стосовно різних ситуацій і подивимося, чи це вплине на майбутнє реляційних БД.

Реляційні бази даних існують близько 30 років. За цей час спалахували кілька революцій, які мали покласти край реляційним сховищам. Звичайно, жодна з цих революцій не відбулася, і одна з них ні на йоту не похитнула позиції реляційних БД.

Почнемо з основ

Реляційна база даних є набір таблиць (сутностей). Таблиці складаються з колонок та рядків (кортежів). Усередині таблиць можна визначити обмеження, між таблицями існують відносини. За допомогою SQL можна виконувати запити, які повертають набори даних, що одержуються з однієї чи кількох таблиць. В рамках одного запиту дані виходять з кількох таблиць шляхом їх з'єднання (JOIN), найчастіше для з'єднання використовуються самі колонки, які визначають відносини між таблицями. Нормалізація - це процес структурування моделі даних, що забезпечує зв'язність і відсутність надмірності даних.

Доступ до реляційних баз даних здійснюється через реляційні системи управління базами даних (РСУБД). Майже всі системи баз даних, які ми використовуємо є реляційними, такі як Oracle, SQL Server, MySQL, Sybase, DB2, TeraData і так далі.

Причини такого домінування є неочевидними. Протягом усього існування реляційних БД вони постійно пропонували найкращу суміш простоти, стійкості, гнучкості, продуктивності, масштабованості та сумісності у сфері управління даними.

Однак, щоб забезпечити всі ці особливості, реляційні сховища неймовірно складні всередині. Наприклад, простий запит SELECT може мати сотні потенційних шляхів виконання, які оптимізатор оцінить безпосередньо під час виконання запиту. Все це приховано від користувачів, проте всередині РСУБД створює план виконання, що ґрунтується на речах на кшталт алгоритмів оцінки вартості та найкраще відповідає запиту.

Проблеми реляційних БД

Хоча реляційні сховища забезпечують найкращу суміш простоти, стійкості, гнучкості, продуктивності, масштабованості та сумісності, їх показники по кожному з цих пунктів не обов'язково вищі, ніж у аналогічних систем, орієнтованих на якусь одну особливість. Не було великою проблемою, оскільки загальне домінування реляційних СУБД переважувало будь-які недоліки. Проте якщо звичайні РБД не відповідали потребам, завжди існували альтернативи.

Сьогодні ситуація трохи інша. Різноманітність додатків зростає, а з ним зростає і важливість перерахованих особливостей. І зі зростанням кількості баз даних, одна особливість починає затьмарювати всі інші. Це масштабованість. Оскільки все більше програм працює в умовах високого навантаження, наприклад, таких як веб-сервіси, їх вимоги до масштабованості можуть дуже швидко змінюватись і сильно зростати. Першу проблему може бути дуже складно вирішити, якщо у вас є реляційна база даних, розташована на власному сервері. Припустимо, навантаження на сервер за ніч збільшилося втричі. Як швидко ви зможете проапгрейдити залізо? Вирішення другої проблеми також викликає труднощі у разі використання реляційних БД.

Реляційні БД добре масштабуються лише у разі, якщо розташовуються на єдиному сервері. Коли ресурси цього сервера закінчаться, вам доведеться додати більше машин і розподілити навантаження між ними. І ось тут складність реляційних БД починає грати проти масштабованості. Якщо ви спробуєте збільшити кількість серверів не до декількох штук, а до сотні або тисячі, складність зросте на порядок, і характеристики, які роблять реляційні БД такими привабливими, стрімко знижують шанси використовувати їх як платформу для великих розподілених систем.

Щоб залишатися конкурентоспроможними, вендорам хмарних сервісів доводиться якось боротися з цим обмеженням, бо яка ж це хмарна платформа без сховища даних, що масштабується. Тому у вендорів залишається лише один варіант, якщо вони хочуть надавати користувачам масштабоване місце для зберігання даних. Потрібно застосовувати інші типи баз даних, які мають більш високу здатність до масштабування, нехай і ціною інших можливостей, доступних у реляційних БД.

Ці переваги, а також існуючий попит на них призвели до хвилі нових систем управління базами даних.

Нова хвиля

Такий тип баз даних прийнято називати сховище типу ключ-значення (key-value store). Фактично, жодної офіційної назви не існує, тому ви можете зустріти її в контексті документо-орієнтованих, атрибутно-орієнтованих, розподілених баз даних (хоча вони також можуть бути реляційними), шардованих упорядкованих масивів (sharded sorted arrays), розподілених хеш-таблиць та сховищ типу ключ-значення. І хоча кожна з цих назв вказує на конкретні особливості системи, всі вони є варіаціями на тему, яку ми назватимемо сховище типу ключ-значення.

Втім, як би ви його не називали, цей «новий» тип баз даних не такий вже й новий і завжди застосовувався переважно для додатків, для яких використання реляційних БД було б непридатним. Однак без потреби Інтернету та «хмари» в масштабованості ці системи залишалися не дуже затребуваними. Тепер завдання полягає в тому, щоб визначити, який тип сховища більше підходить для конкретної системи.
Реляційні БД та сховища типу ключ-значення відрізняються докорінно і призначені для вирішення різних завдань. Порівняння характеристик дозволить лише зрозуміти різницю між ними, проте почнемо з цього:

Характеристики сховищ

Реляційна БД	Сховище типу ключ-значення
База даних складається з таблиць, таблиці містять колонки та рядки, а рядки складаються із значень колонок. Усі рядки однієї таблиці мають єдину структуру.	Для доменів можна провести аналогію з таблицями, проте на відміну таблиць для доменів не визначається структура даних. Домен - це така коробка, в яку ви можете складати все, що завгодно. Записи всередині одного домену можуть мати різну структуру.
Модель даних 1 визначено заздалегідь. Є строго типізованою, містить обмеження та відносини для забезпечення цілісності даних.	Записи ідентифікуються за ключом, при цьому кожен запис має динамічний набір атрибутів, пов'язаних із ним.
Модель даних заснована на природному поданні даних, що містяться, а не на функціональності програми.	У деяких реалізація атрибути можуть бути лише рядковими. В інших реалізаціях атрибути мають прості типи даних, які відображають типи, що використовуються у програмуванні: цілі числа, масив рядків і списки.
Модель даних піддається нормалізації, щоб уникнути дублювання даних. Нормалізація породжує відносини між таблицями. Відносини пов'язують дані різних таблиць.	Між доменами, як і всередині одного домену, відносини явно не визначені.

Жодних join'ів

Сховища типу ключ-значення орієнтовані працювати із записами. Це означає, що вся інформація, що стосується цього запису, зберігається разом з нею. Домен (про який ви можете думати як про таблицю) може містити незліченну кількість різних записів. Наприклад, домен може містити інформацію про клієнтів та замовлення. Це означає, що дані зазвичай дублюються між різними доменами. Це прийнятний підхід, оскільки дисковий простір дешевий. Головне, що він дозволяє всі пов'язані дані зберігати в одному місці, що покращує масштабованість, оскільки зникає необхідність з'єднувати дані з різних таблиць. При використанні реляційної БД, потрібно використовувати сполуки, щоб згрупувати в одному місці потрібну інформацію.

Хоча для зберігання пар ключ-значення потреба у відносинах різко падає, відносини все ж таки потрібні. Такі відносини зазвичай є між основними сутностями. Наприклад, система замовлень мала б записи, які містять дані про покупців, товари та замовлення. При цьому неважливо, ці дані знаходяться в одному домені або в декількох. Суть у тому, що коли покупець розміщує замовлення, вам швидше за все не захочеться зберігати інформацію про покупця та замовлення одного запису.
Натомість, запис про замовлення має містити ключі, які вказують на відповідні записи про покупця та товар. Оскільки в записах можна зберігати будь-яку інформацію, а відносини не визначені у самій моделі даних, система управління базою даних зможе проконтролювати цілісність відносин. Це означає, що ви можете видаляти покупців та товари, які вони замовляли. Забезпечення цілісності даних повністю лягає на додаток.

Доступ до даних

Реляційна БД	Сховище типу ключ-значення
Дані створюються, оновлюються, видаляються та запитуються з використанням мови структурованих запитів (SQL).	Дані створюються, оновлюються, видаляються та запитуються за допомогою виклику API методів.
SQL-запити можуть отримувати дані як з одиночної таблиці, так і з декількох таблиць, використовуючи при цьому з'єднання (join'и).	Деякі реалізації надають SQL-подібний синтаксис завдання умов фільтрації.
SQL-запити можуть містити агрегації та складні фільтри.	Найчастіше можна використовувати лише базові оператори порівнянь (=, !=,<, >, <= и =>).
Реляційна БД зазвичай містить вбудовану логіку, таку як тригери, процедури, що зберігаються і функції.	Вся бізнес-логіка і логіка підтримки цілісності даних міститься у коді додатків.

Взаємодія з програмами

Сховища типу ключ-значення: переваги

Є дві чіткі переваги таких систем перед реляційними сховищами.

Підходять для хмарних сервісів

Перша перевага сховищ типу ключ-значення полягає в тому, що вони простіші, а значить мають більшу масштабованість, ніж реляційні БД. Якщо ви розміщуєте разом власну систему, і плануєте розмістити дюжину або сотню серверів, яким потрібно справлятися зі зростаючим навантаженням, за вашим сховищем даних, тоді ваш вибір - сховища типу ключ-значення.

Завдяки тому, що такі сховища легко і динамічно розширюються, вони також стануть у нагоді вендорам, які надають розраховану на багато користувачів веб-платформу зберігання даних. Така база є відносно дешевим засобом зберігання даних з великим потенціалом до масштабованості. Користувачі зазвичай платять лише за те, що вони використовують, проте їхні потреби можуть зрости. Вендор зможе динамічно та практично без обмежень збільшити розмір платформи, виходячи з навантаження.

Більш природна інтеграція з кодом

Реляційна модель даних та об'єктна модель коду зазвичай будуються по-різному, що веде до деякої несумісності. Розробники вирішують цю проблему за допомогою написання коду, який відображає реляційну модель об'єктну модель. Цей процес не має чіткої та швидко досяжної цінності і може зайняти досить значний час, який міг бути витрачений на розробку самого додатка. Тим часом багато сховищ типу ключ-значення зберігають дані в такій структурі, яка відображається в об'єкти більш природно. Це може значно зменшити час розробки.

Інші аргументи на користь використання сховищ типу ключ-значення, на кшталт «Реляційні бази можуть стати незграбними» (до речі, без поняття, що це означає), є менш переконливими. Але перш ніж стати прихильником таких сховищ, ознайомтеся з наступним розділом.

Сховища типу ключ-значення: недоліки

Обмеження в реляційних БД гарантують цілісність даних на найнижчому рівні. Дані, які не задовольняють обмежень, фізично не можуть потрапити до бази. У сховищах типу ключ-значення таких обмежень немає, тому контроль цілісності даних лежить на додатках. Однак у будь-якому коді є помилки. Якщо помилки правильно спроектованої реляційної БД зазвичай не ведуть до проблем цілісності даних, то помилки в сховищах типу ключ-значення зазвичай призводять до таких проблем.

Інша перевага реляційних БД у тому, що вони змушують вас пройти через процес розробки моделі даних. Якщо ви добре спроектували модель, то база даних міститиме логічну структуру, яка повністю відображає структуру даних, що зберігаються, проте розходиться зі структурою програми. Таким чином, дані стають незалежними від програми. Це означає, що інший додаток зможе використовувати ті ж дані і логіка програми може бути змінена без будь-яких змін в моделі бази. Щоб зробити те саме зі сховищем типу ключ-значення, спробуйте замінити процес проектування реляційної моделі проектуванням класів, при якому створюються загальні класи, засновані на природній структурі даних.

І не забудьте про сумісність. На відміну від реляційних БД, сховища, орієнтовані використання у «хмарі», мають набагато менше загальних стандартів. Хоча концептуально вони й не відрізняються, вони мають різні API, інтерфейси запитів і свою специфіку. Тому вам краще довіряти вашому вендору, тому що в разі чого ви не зможете легко переключитися на іншого постачальника послуг. А враховуючи той факт, що майже всі сучасні сховища типу ключ-значення знаходяться на стадії бета-версій 2 , довіряти стає ще ризикованішим, ніж у разі використання реляційних БД.

Обмежена аналітика даних

Зазвичай усі хмарні сховища будуються за типом множинної оренди, що означає, що ту саму систему використовує велику кількість користувачів і додатків. Щоб запобігти «захопленню» загальної системи, вендори зазвичай якимось чином обмежують виконання запитів. Наприклад, у SimpleDB запит не може виконуватися довше 5 секунд. У Google AppEngine Datastore за один запит не можна отримати більше 1000 записів 3 .

Ці обмеження не страшні для простої логіки (створення, оновлення, видалення та вилучення невеликої кількості записів). Але що якщо ваш додаток стає популярним? Ви отримали багато нових користувачів і багато нових даних, і тепер хочете створити нові можливості для користувачів або якимось чином отримати вигоду з даних. Тут ви можете жорстко обламатися з виконанням навіть найпростіших запитів для аналізу даних. Фічі на кшталт відстеження шаблонів використання програми чи системи рекомендацій, заснованої на історії користувача, у разі можуть бути складні у реалізації. А в гіршому – просто неможливі.

У такому випадку для аналітики краще зробити окрему базу даних, яка заповнюватиметься даними з вашого сховища типу ключ-значення. Продумайте заздалегідь, як це можна буде зробити. Чи будете ви розміщувати сервер у хмарі чи у себе? Чи не буде проблем через затримки сигналу між вами та вашим провайдером? Чи підтримує ваше сховище таке перенесення даних? Якщо у вас 100 мільйонів записів, а за один раз ви можете взяти 1000 записів, скільки потрібно перенести всі дані?

Однак не ставте масштабування понад усе. Вона буде марна, якщо ваші користувачі вирішать користуватися послугами іншого сервісу, тому що той надає більше можливостей та налаштувань.

Хмарні сховища

Безліч постачальників веб-сервісів пропонують розраховані на багато користувачів сховища типу ключ-значення. Більшість із них задовольняють критеріям, переліченим вище, проте кожне має свої відмінні фічі та відрізняється від стандартів, описаних вище. Давайте поглянемо на конкретні приклади сховищ, такі як SimpleDB, Google AppEngine Datastore і SQL Data Services.

Amazon: SimpleDB

SimpleDB – це атрибутно-орієнтоване сховище типу ключ-значення, що входить до складу Amazon WebServices. SimpleDB знаходиться у стадії бета-версії; користувачі можуть користуватись їй безкоштовно - доти їх потреби не перевищать певну межу.

SimpleDB має кілька обмежень. Перше - час виконання запиту обмежено 5 секундами. Друге – немає жодних типів даних, крім рядків. Все зберігається, витягується та порівнюється як рядок, тому для того, щоб порівняти дати, вам потрібно буде перетворити їх у формат ISO8601. Третє - максимальний розмір будь-якого рядка становить 1024 байта, що обмежує розмір тексту (наприклад, опис товару), який ви можете зберігати як атрибут. Однак оскільки структура даних є гнучкою, ви можете обійти це обмеження, додаючи атрибути «ОписТовара1», «Опис товару2» і т.д. Але кількість атрибутів також обмежена – максимум 256 атрибутів. Поки SimpleDB знаходиться в стадії бета-версії, розмір домену обмежений 10 гігабайтами, а вся база не може займати більше одного терабайта.

Однією із ключових особливостей SimpleDB є використання моделі кінцевої констистенції (eventual consistency model). Ця модель підходить для багатопотокової роботи, проте слід мати на увазі, що після того, як ви змінили значення атрибута в якомусь записі, при наступних операціях читання ці зміни можуть бути не видно. Імовірність такого розвитку подій досить низька, проте про неї треба пам'ятати. Ви ж не хочете продати останній квиток п'ятьом покупцям тільки тому, що ваші дані були неконсистентні в момент продажу.

Google AppEngine Data Store

Google"s AppEngine Datastore побудований на основі BigTable, внутрішньої системи зберігання структурованих даних від Google. AppEngine Datastore не надає прямий доступ до BigTable, але може сприйматися як спрощений інтерфейс взаємодії з BigTable.

AppEngine Datastore підтримує більше типів даних всередині одного запису, ніж SimpleDB. Наприклад, списки, які можуть містити колекції всередині запису.

Швидше за все, ви будете використовувати саме це сховище даних при розробці за допомогою Google AppEngine. Однак, на відміну від SimpleDB, ви не зможете використовувати AppEngine Datastore (або BigTable) поза веб-сервісами Google.

Microsoft: SQL Data Services

SQL Data Services є частиною платформи Microsoft Azure. SQL Data Services є безкоштовною, перебуває у стадії бета-версії і має обмеження розмір бази. SQL Data Services є окремим додатком - надбудову над безліччю SQL серверів, які зберігають дані. Ці сховища можуть бути реляційними, однак для вас SDS є сховищем типу ключ-значення, як і описані вище продукти.

Нехмарні сховища

Існує також ряд сховищ, якими ви можете скористатися за межами хмари, встановивши їх у себе. Майже всі ці проекти є молодими, знаходяться на стадії альфа- або бета-версії, і мають відкритий код. З відкритими вихідними джерелами ви, можливо, будете більше поінформовані про можливі проблеми та обмеження, ніж у разі використання закритих продуктів.

CouchDB

CouchDB - це документо-орієнтована БД, що вільно розповсюджується, з відкритим вихідним кодом. Як формат зберігання даних використовується JSON. CouchDB покликана заповнити пробіл між документоорієнтованими та реляційними базами даних за допомогою «уявлень». Такі уявлення містять дані з документів у вигляді, схожим на табличний, і дозволяють будувати індекси і виконувати запити.

В даний час CouchDB не є по-справжньому розподіленою базою даних. У ній є функції реплікації, що дозволяють синхронізувати дані між серверами, проте це не та розподіл, яка потрібна для побудови оточення, що високомасштабується. Однак, розробники CouchDB працюють над цим.

Проект Voldemort

Проект Voldemort - розподілена база даних типу ключ-значення, призначена для горизонтального масштабування на великій кількості серверів. Він народився в процесі розробки LinkedIn і використовувався для декількох систем, що мають високі вимоги до масштабованості. У проекті Voldemort також використовується модель кінцевої консистенції.

Mongo

Mongo - це база даних, що розробляється в 10gen Гейром Магнуссоном і Дуайтом Мерріменом (якого ви можете знати по DoubleClick). Як і CouchDB, Mongo - це документоорієнтована база даних, що зберігає дані в JSON форматі. Однак Mongo скоріше є об'єктною базою, ніж чистим сховищем типу ключ-значення.

Drizzle

Drizzle представляє зовсім інший підхід до вирішення проблем, з якими покликані боротися сховища типу ключ-значення. Drizzle починався як одна з гілок MySQL 6.0. Пізніше розробники видалили ряд функцій (включаючи уявлення, тригери, скомпіловані вирази, процедури, що зберігаються, кеш запитів, ACL, і частина типів даних), з метою створення більш простої і швидкої СУБД. Тим не менш, Drizzle все ще можна використовувати для зберігання реляційних даних. Мета розробників - побудувати напівреляційну платформу, призначену для веб-додатків та хмарних додатків, що працюють на системах з 16 і більше ядрами.

Рішення

Зрештою, є чотири причини, з яких ви можете вибрати нереляційне сховище типу ключ-значення для вашого застосування:

1. Ваші дані дуже документо-орієнтовані, і більше підходять для моделі даних ключ-значення, ніж для реляційної моделі.
2. Ваша доменна модель об'єктно-орієнтована, тому використання сховища типу ключ-значення зменшить розмір додаткового коду для перетворення даних.
3. Сховище даних дешево та легко інтегрується з веб-сервісами вашого вендора.
4. Ваша головна проблема - висока масштабованість на запит.

Однак приймаючи рішення, пам'ятайте про обмеження конкретних БД та ризики, які ви зустрінете, пішовши шляхом використання нереляційних БД.

Для решти вимог краще вибрати старі добрі реляційні СУБД. То чи приречені вони? Звичайно, ні. Принаймні поки що.

1 - на мою думку, тут найбільше підходить термін «структура даних», проте залишив оригінальне data model.
2 - швидше за все, автор мав на увазі, що за своїми можливостями нереляційні БД поступаються реляційним.
3 – можливо, дані вже застаріли, стаття датується лютим 2009 року.

Додати теги

Реляційна модель

Реляційна модель бази даних була запропонована в 1969 математиком і науковим співробітником фірми IBM Е.Ф. Коддім (E.F. Codd). Деякі початкові відомості про реляційні бази даних містяться в оглядовій статті БД та СУБД 2. Оскільки саме реляційні бази даних є домінуючими, у цій статті (а також у статтях “ Опис даних”, “Обробка даних” та “ Проектування БД 2) докладно розглядаються найбільш суттєві поняття реляційної моделі.

Відразу зазначимо, що теорія реляційних баз даних спочатку була сформульована суворою математичною мовою, і саме суворі, формально визначені математичні поняття найкраще описують суть речей. Разом з тим у більшості випадків можна без особливої ​​шкоди пожертвувати строгістю термінології на користь прозорості викладу, що ми намагатимемося робити.

Основна ідея реляційної моделі полягає у наступному. База даних складається з низки невпорядкованих таблиць(У найпростішому випадку – з однієї таблиці). Таблицями можна маніпулювати за допомогою непроцедурних (декларативних) операцій. запитіврезультатами яких також є таблиці.

Нерідко слово "реляційна" ( relational) у терміні "реляційна модель" трактують, ґрунтуючись на тому, що в реляційній базі даних встановлюються зв'язки ( relate) між таблицями. Таке пояснення зручне, але воно не є точним. В оригінальній системі термінів Кодда терміни зв'язку ( relations), атрибути ( attributes) та кортежі ( tuples) вживалися там, де більшість із нас користується більш звичними термінами таблиці, стовпці (поля) та рядки (записи).

При побудові інфологічної моделі предметної області (див. БД та СУБД”, “Проектування БД” 2) виділяються сутності(об'єкти), описуються їх властивостейа (характеристики, атрибути), суттєві для моделювання, і встановлюються зв'язки між сутностями. На етапі переходу від інфологічної до даталогічної реляційної моделі таки з'являються таблиці. Як правило, кожна сутність є однією таблицею. Кожен рядок таблиці (один запис) відповідає одному екземпляру сутності, а кожне поле описує певну властивість (атрибут).

Наприклад, якщо нам потрібно зберігати інформацію про людей, що включає прізвище кожного, ім'я, по батькові, ІПН, країну проживання та дату народження, то сутністю є саме людина, а зазначені дані – атрибутами. Сама сутність природно стає назвою таблиці.

Таблиця "Людина"

Реляційна модель вимагає, щоб кожен рядок таблиці був унікальним, тобто. щоб будь-які два рядки відрізнялися значенням хоча б одного атрибута.

Традиційна таблична форма зручна, коли потрібно надати самі дані. Якщо ж, як у наведеному вище прикладі, цікавить лише структура- імена полів, то з погляду наочності, зручності використання у схемах та економії місця зручніше зображати її так:

Ключі

Ключем таблиціназивається поле або група полів, що містять унікальні в рамках даної таблиці значення. Ключ однозначно визначає відповідний рядок таблиці. Якщо ключ складається з одного поля, його часто називають простим, якщо з кількох - складовим. У наведеному вище прикладі ключем є поле ІПН (ми вважаємо відомим той факт, що ІПН в межах країни є унікальними).

Розглянемо приклад таблиці зі складеним ключем. На сайтах прогнозів погоди нерідко подають інформацію наступним чином: для кожної дати вказують прогнозовану температуру вночі, вранці, вдень та ввечері. Для зберігання зазначеної інформації можна використати таблицю такого виду:

У цій таблиці ні поле Дата, ні Час доби, ні Температура є ключами - у кожному з цих полів значення можуть повторюватися. Проте комбінація полів Дата+Час доби є унікальною і однозначно визначає рядок таблиці. Це і є складовим ключем.

Нерідко трапляється ситуація, у якій вибір ключа перестав бути однозначним. Повернемося до першого прикладу. Припустимо, на додаток до прізвища, імені, по батькові, ІПН, дати народження потрібно зберігати серію та номер загальногромадянського паспорта та серію та номер закордонного паспорта. Таблиця матиме такий вигляд.

У цій таблиці можна вибрати цілих три ключі. Один з них - простий (ІПН), два інші - складові (Серія+Номер загальногромадянського паспорта та Серія+Номер закордонного паспорта). У такій ситуації розробник вибирає найзручніший з погляду організації БД ключ (загалом - ключ, на пошук значення якого потрібно найменший час). Вибраний ключ у цьому випадку часто називають головним, або первинним, ключем, а інші комбінації стовпців, з яких можна зробити ключ, - можливими, або альтернативними ключами. Зазначимо, що хоча один можливий ключ у таблиці є завжди, оскільки рядки що неспроможні повторюватися і, отже, комбінація всіх стовпців гарантовано є можливим ключем.

При зображенні таблиць первинні ключі таблиць прийнято виділяти. Наприклад, відповідні поля часто наголошують. А Microsoft Access виділяє ключові поля напівжирним шрифтом.

Ще частіше, ніж із неоднозначністю вибору ключа, розробники стикаються з відсутністю ключа серед даних, які потрібно зберігати. Подібний факт може бути встановлений у процесі аналізу предметної галузі. Наприклад, якщо потрібно зберігати простий список людей - імена, прізвища, по батькові та дати народження, то ключа в цьому наборі атрибутів немає зовсім - можлива ситуація, коли у двох різних людей зазначені дані збігаються повністю. У такому разі доводиться штучно вводити додаткове поле, наприклад унікальний номер людини. Такий ключ у літературі іноді називають сурогатним. Нерідко сурогатний ключ вводять і з міркувань ефективності. Якщо, наприклад, у таблиці є довгий складовий ключ, то розробники часто вводять додатковий короткий цифровий сурогатний ключ і саме його роблять первинним. Нерідко так чинять навіть за наявності простого ключа, що має "незручний" (неефективний для пошуку) тип даних, наприклад, рядковий. Подібні операції вже не мають відношення до теорії, але часто зустрічаються на практиці.

Уважний читач, можливо, зверне увагу на те, що ключ практично завжди можна розширити (якщо в нього не входять усі поля таблиці) за рахунок включення надлишкових полів. Формально такий ключ залишиться ключем, але з практичного погляду це лише гра поняттями. Такі ключі і за можливі не вважають, оскільки завжди необхідно прагнути до мінімізації довжини (складності) ключа.

Нормальні форми, нормалізація

Не всяка таблиця, яку ми можемо намалювати на папері чи Word'і, може бути таблицею реляційної бази даних. І не будь-яка таблиця, яка може використовуватися в реляційній базі даних, є правильною з погляду вимоги реляційної моделі.

По перше, потрібно, щоб усі дані в межах одного стовпця мали один і той самий тип(про типи див.“Опис даних”2). З цього погляду наведений нижче приклад не має сенсу навіть обговорювати:

По-друге, потрібно, щоб у таблиці було призначено первинний ключ.

Вказані вимоги є необхідними, але недостатніми. Теоретично реляційних баз даних вводяться поняття про “нормальних форм” - вимог до організації даних у таблицях. Нормальні форми нумеруються послідовно, в міру посилення вимог. У правильно спроектованій БД таблиці знаходяться як мінімум у третій нормальній формі. Відповідно, ми розглянемо перші три нормальні форми. Нагадаємо, що ми маємо справу з таблицями, що задовольняють двом сформульованим вище основним вимогам.

Перша нормальна форма (1НФ)

Перша нормальна форма наказує, що всі дані, що містяться в таблиці, повинні бути атомарними(неподільними). Перелік відповідних атомарних типів даних визначається СУБД. Вимога 1НФ цілком природна. Воно означає, що в кожному полі кожного запису повинна бути лише одна величина, але не масив і не якась інша структура даних. Наведемо осмислений приклад таблиці, яка знаходиться в 1НФ. Нехай ми маємо списки оцінок учнів з деякого предмета.

Оскільки значення поля Оцінки перестав бути атомарним, таблиця відповідає вимогам 1НФ.

Про можливий спосіб подання списку оцінок написано у методичних рекомендаціях до статті "Проектування БД" 2.

Друга нормальна форма (2НФ)

Кажуть, що таблиця знаходиться в другій нормальній формі, якщо вона знаходиться в 1НФ і кожен ключовий стовпець повністю залежить від первинного ключа.Інакше кажучи, значення кожного поля має повністю визначатися значенням первинного ключа. Важливо, що залежність від первинного ключа розуміється як залежність від ключа цілком, а чи не від окремої його складової (у разі складеного ключа). Наведемо приклад таблиці, яка перебуває у 2НФ. Для цього повернемося наприклад прогнозу погоди і доповнимо таблицю ще одним стовпцем - часом сходу сонця (це цілком правдоподібний приклад, такого роду інформація часто наводиться на сайтах прогнозу погоди).

Як ми пам'ятаємо, ця таблиця має складовий ключ Дата + Час доби. Температура повністю залежить від первинного ключа - з ним проблем немає. А ось поле Схід залежить лише від поля Дата, Час доби на час сходу природним чином не впливає.

Тут доречно поставити запитання: а в чому практичний зміст 2НФ? Яка користь від цих обмежень? Виявляється – велика. Припустимо, що у наведеному вище прикладі розробник проігнорує вимоги 2НФ. По-перше, швидше за все виникне так звана надмірність- Зберігання зайвих даних. Адже якщо для одного запису з цією датою вже зберігається час сходу, то для всіх інших записів з цією датою воно має бути таким самим і зберігати його, взагалі кажучи, нема чого.

Звернімо увагу на слова "має бути". А як не буде? Адже на рівні БД це ніяк не контролюється – ключ у таблиці складової, однакові дати можуть бути (і за змістом швидше за все будуть). І жодні формальні обмеження (а наше розуміння, що “такого не може бути”, до таких не належить) не забороняють вказати різний час сходу на одну й ту саму дату.

Третя нормальна форма (3НФ)

Кажуть, що таблиця знаходиться в 3НФ, якщо вона відповідає 2НФ і всі ключові стовпці взаємно незалежні.

Взаємну залежність стовпців зручно розуміти так: стовпці є взаємно залежними, якщо не можна змінити одне із них, не змінюючи інший.

Наведемо приклад таблиці, що у 3НФ. Розглянемо приклад простої записника для зберігання домашніх телефонів людей, які проживають, можливо, в різних регіонах країни.

У цій таблиці є залежність між не ключовими стовпцями Місто і Код міста, отже, таблиця не знаходиться в 3НФ.

Зазначимо, що наявність зазначеної вище залежності розробник визначає, аналізуючи предметну область, - жодними формальними методами подібну колізію не можна побачити. При зміні властивостей предметної області залежність між стовпцями може зникнути. Наприклад, якщо в межах одного міста вводяться різні коди (як 495 і 499 у Москві), відповідні стовпці перестають бути пов'язаними з погляду порушення вимог 3НФ.

Теоретично реляційних баз даних розглядаються і форми вищих порядків - нормальна форма Бойса - Кодда, 4НФ, 5НФ і навіть вище. Великого практичного значення ці форми немає, і розробники, зазвичай, завжди зупиняються на 3НФ.

Нормалізація БД

Нормалізація є процесом приведення таблиць бази даних до обраної нормальної форми. Нормалізація до 2НФ, зазвичай, зводиться до декомпозиції - розбиття однієї таблиці на кілька. Нормалізація до 3НФ зазвичай може бути виконана видаленням залежних (обчислюваних) стовпців. У деяких випадках при нормалізації до 3НФ також доводиться виробляти декомпозицію.

Багатотабличні БД, зв'язки між таблицями, зовнішні ключі

Насправді однотабличні бази даних зустрічаються досить рідко, оскільки з погляду моделювання базою даних предметної області наявність однієї таблиці означає наявність однієї сутності. Натомість, наявність кількох сутностей зазвичай означає наявність зв'язків з-поміж них.

Не ставлячи за мету повне проектування БД, розглянемо приклад, що дозволяє продемонструвати зв'язки у багатотабличних БД.

Нехай ми маємо справу зі школою, в якій є учні, згруповані за класами, та вчителі, які викладають деякі предмети. У нас одразу виділяються чотири сутності: учні, вчителі, класи та предмети. Ці сутності вже дають чотири таблиці.

Далі нам потрібно вирішити питання про атрибути сутностей - яку саме інформацію ми зберігатимемо. Оскільки наш приклад має виключно демонстраційний характер, постараємося мінімізувати обсяг інформації, що зберігається. Домовимося для кожного учня зберігати прізвище та ім'я, для класу – номер паралелі та букву, що ідентифікує клас усередині паралелі, для вчителя – прізвище, ім'я та по батькові, для предмета – тільки його назва.

Тепер слід вирішити питання з первинними ключами. Таблиці учнів та вчителів у принципі не мають ключа, тому ми введемо в них сурогатний числовий ключ – номер. Таблиці класів та предметів, взагалі кажучи, мають ключі. У таблиці класів ключ складовий, його утворюють атрибути Номер паралелі+Літера, а таблиці предметів простий ключ складається з єдиного поля - назви предмета. Згадаймо, що, говорячи про ключі, ми згадували про те, що сурогатні ключі часто додають з міркувань ефективності, прагнучи позбутися складових ключів або ключових полів незручних типів, наприклад, рядкових. Так ми й зробимо. Додамо в кожну таблицю сурогатний числовий ключ.

В результаті ми отримаємо наступний набір таблиць, що відповідають сутностям, що описуються.

Розуміючи, з якою предметною областю маємо справу, ми знаємо, що наші сутності існують не власними силами - вони пов'язані деякими відносинами, які ми позначили вище. Але як їх пов'язати технічно? Тут не обійтися без запровадження додаткових полів і навіть додаткових таблиць. Розберемося із відносинами між сутностями по порядку.

Щоб віднести учня до деякого класу, заведемо у таблиці "Учень" додаткове поле Номер класу. (Зрозуміло, що його тип повинен повністю збігатися з типом поля Номер класу в таблиці “Клас”.) Тепер ми можемо зв'язати таблиці “Учень” та “Клас” за відповідними значеннями полів. так часто роблять, щоб легко орієнтуватися у зв'язуючих полях). Зауважимо, що одного запису в таблиці “Клас” може відповідати багато записів у таблиці “Учень” (і практично швидше за все відповідає - важко уявити клас з одного учня). Про такі таблиці говорять, що вони пов'язані ставленням “ один до багатьох”. А поле Номер класу у таблиці "Учень" називають зовнішнім ключем. Як бачимо, призначення зовнішніх ключів – зв'язування таблиць. Зазначимо, що зовнішній ключ завжди посилається на первинний ключ пов'язаної таблиці (тобто. зовнішній ключ знаходиться на стороні "багатьох"). Пов'язаний із зовнішнім первинний ключ називають батьківськимхоча цей термін використовується рідше.

Проілюструємо сказане схемою у стилі Microsoft Access (докладніше про “Схему даних” Access написано у статті "Опис даних" 2).

Тепер згадаємо про вчителів та предмети. Аналізуючи предметну область (тільки так - адже справжній стан речей із самої формальної моделі витягти неможливо), ми помічаємо, що тип зв'язку між сутностями "вчитель" і "предмет" інший, ніж розглянутий вище. Адже не лише один предмет може вести багато вчителів, а й один учитель може вести багато предметів. Таким чином, між цими сутностями є зв'язок багато хто до багатьох”. Тут не обійтися введенням додаткових полів (спробуйте!). Зв'язки "багато до багатьох" завжди дозволяються за допомогою введення додаткової таблиці. Зокрема, організуємо таблицю “Учитель-Предмет”, що має таку структуру:

Таблиця "Учитель-Предмет"

Ця таблиця має складовий ключ, утворений із двох її полів. І таблиця "Учитель", і таблиця "Предмет" пов'язані з цією таблицею ставленням "один до багатьох" (зрозуміло, в обох випадках "багато" знаходяться на стороні "Учитель-Предмет"). Відповідно, у таблиці “Учитель-Предмет” є два зовнішніх ключа (обидва - частини складового первинного ключа, що забороняється), службовці зв'язки України із відповідними таблицями.

Насправді, крім розглянутих відносин “один до багатьох” і “багато хто до багатьох”, зустрічається і ставлення “ один до одного”. З погляду теорії таке ставлення інтересу не представляє, оскільки дві таблиці, пов'язані ставленням "один до одного", завжди можна просто об'єднати в одну. Проте в реальних базах даних ставлення "один до одного" застосовується для оптимізації обробки даних. Проілюструємо сказане прикладом.

Допустимо, ми зберігаємо дуже багато різноманітної інформації про людей - дані їх різноманітних документів, телефони, адреси та ін. Швидше за все більша частина цих даних буде використовуватися дуже рідко. А часто нам знадобляться лише прізвище, ім'я, по батькові та телефон. Тоді має сенс організувати дві таблиці та пов'язати їх ставленням "один до одного". В одній (невеликій) таблиці зберігати інформацію, що часто використовується, в іншій - іншу. Природно, що таблиці, пов'язані ставленням "один до одного", мають той самий первинний ключ.

Правила цілісності

Реляційна модель визначає два загальні правила цілісності бази даних: цілісність об'єктів і цілісність посилань.

Правило цілісності об'єктівдуже просте. Воно вимагає, щоб первинні ключі таблиць не містили невизначених (порожніх) значень.

Правило посилальної цілісності вимагає, щоб зовнішні ключі не містили неузгоджених із батьківськими ключами значень. Повертаючись до розглянутого вище прикладу, ми повинні вимагати, наприклад, щоб учні ставилися лише до класу, номер якого вказано у таблиці “Класи”.

Більшість СУБД вміють стежити за цілісністю даних (зрозуміло, це вимагає відповідних зусиль і від розробника на етапі опису структур даних). Зокрема, для підтримки цілісності посилань використовуються механізми каскадуванняоперацій. Каскадування передбачає, зокрема, те, що з видаленні записи з “батьківської” таблиці, що з іншою таблицею ставленням “один до багатьох”, з таблиці “багатьох” автоматично (самої СУБД, без участі користувача) видаляються все пов'язані записи. І це природно, адже такі записи “повисають у повітрі”, вони ні з чим не пов'язані.

Індексація

Індексація - украй важлива з погляду практичного застосування, але факультативна з позиції чистої теорії річ. Основне призначення індексації – оптимізація (прискорення) пошуку (і, відповідно, деяких інших операцій із базою даних). Індексація у разі потребує додаткових ресурсів (фізично найчастіше створюються спеціальні індексні файли). Операції, пов'язані з модифікацією даних, індексація може навіть уповільнювати, тому індексують зазвичай таблиці, що рідко змінюються, в яких часто проводиться пошук.

Індексний файл дуже схожий на індекс звичайної книги. Для кожного значення індексу зберігається список рядків таблиці, де міститься дане значення. Відповідно, для пошуку не треба переглядати всю таблицю - достатньо заглянути до індексу. Зате при модифікації записів може знадобитися перебудувати індекс. І на це йде додатковий час.

Зрозуміло, і не йдеться про те, щоб викладати теорію реляційних баз даних у рамках базового курсу інформатики! Тим не менш, ця стаття дуже важлива для нашої енциклопедії, оскільки в даному випадку ми маємо справу з матеріалом, який не може бути в повному обсязі викладений на уроках, але вчитель повинен володіти ним. Чому?

По-перше, тому що ряд понять вивчаються якраз у рамках базового курсу. Це табличне представлення даних, і ключі таблиць. Всі ми знаємо, що дуже важко грамотно і точно викласти лише деякі поняття, не представляючи загальної картини.

По-друге, виконуючи з дітьми прості запити до баз даних (відповідний матеріал викладено у статті "Обробка даних" 2) необхідно мати справу з правильними з точки зору реляційної теорії таблицями. Не потрібно пояснювати учням, що ці таблиці правильні, а “якби…, то таблиця була б неправильною”, але неприпустимо використовувати погані приклади.

У профільному курсі інформатики ситуація може бути іншою. Найважливіша і вкрай продуктивна форма роботи у профільних класах – проектна. У рамках навчальних проектів можна і потрібно розробляти нескладні бази даних, і тут не обійтись без основ викладеної теорії. Необхідно, проте, враховувати таке:

Моделювані предметні області повинні бути не надто великими;

Вони повинні бути дуже добре знайомі учням (у цьому сенсі неабияк набридлий всім проект "Школа" - не гірший вибір!);

Наївно очікувати, що прослухавши основи теорії, учні зможуть щось спроектувати самі. Кожен крок необхідно проходити разом із ними, докладно аргументуючи свої дії.

Усі сучасні БД використовують CBO (Cost Based Optimization), вартісну оптимізацію. Суть її у тому, що з кожної операції визначається її «вартість», та був загальна вартість запиту зменшується з допомогою використання «дешевих» ланцюжків операцій.

Для кращого розуміння вартісної оптимізації ми розглянемо три поширені способи об'єднання двох таблиць і побачимо, як простий запит на об'єднання може перетворитися на кошмар для оптимізатора. У нашому розгляді ми орієнтуватимемося на тимчасову складність, хоча оптимізатор обчислює «вартість» в ресурсах процесора, пам'яті та операціях введення/виводу. Просто тимчасова складність - поняття приблизне, а визначення необхідних ресурсів процесора потрібно підраховувати всі операції, включаючи додавання, оператори if, множення, ітерації тощо.

Крім того:

• Для кожної високорівневої операції процесор виконує різну кількість низькорівневих операцій.
• Вартість процесорних операцій (з погляду циклів) різна в різних видів процесорів, тобто залежить від конкретної архітектури ЦПУ.

Тому нам буде простіше оцінювати як складність. Але пам'ятайте, що найчастіше продуктивність БД обмежується дисковою підсистемою, а чи не процесорними ресурсами.

Ми говорили про них, коли розглядали В-дерева. Як ви пам'ятаєте, індекси вже відсортовані. До речі, є інші види індексів, наприклад, бітові (bitmap index). Але вони не дають виграшу з точки зору використання процесора, пам'яті та дискової підсистеми порівняно з індексами В-дерев. Крім того, багато сучасних БД можуть динамічно створювати часові індекси для поточних запитів, якщо це допоможе зменшити вартість виконання плану.

4.4.2. Способи звернень

Перш ніж використовувати оператори об'єднання, потрібно спочатку отримати необхідні дані. Зробити це можна такими способами.

• Повне сканування.БД просто зчитує таблицю чи індекс. Як ви знаєте, для дискової підсистеми індекс читати дешевше, ніж таблицю.
• Сканування діапазону.Використовується, наприклад, коли ви використовуєте предикати на кшталт WHERE AGE > 20 AND AGE< 40. Конечно, для сканирования диапазона индекса вам нужно иметь индекс для поля AGE.

  У першій частині статті ми вже з'ясували, що тимчасова складність запиту діапазону визначається як M + log(N), де N - кількість даних в індексі, а М - кількість рядків всередині діапазону. Значення обох цих змінних відомі завдяки статистиці. При скануванні діапазону зчитується лише частина індексу, тому ця операція коштує менше, ніж повне сканування.

• Сканування за унікальними значеннями.Використовується в тих випадках, коли вам потрібно отримати з індексу лише одне значення.
• Звертання за ID рядка.Якщо БД використовує індекс, то більшу частину часу вона займатиметься пошуком пов'язаних з ним рядків. Наприклад, ми робимо такий запит:

  SELECT LASTNAME, FIRSTNAME від PERSON WHERE AGE = 28
  Якщо у нас є індекс для колонки віку, то оптимізатор скористається індексом для пошуку всіх 28-річних, а потім запитатиме ID відповідних рядків таблиці, оскільки індекс містить інформацію лише про вік.

  Припустимо, у нас інший запит:

  SELECT TYPE_PERSON.CATEGORY від PERSON, TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE
  Для об'єднання з TYPE_PERSON використовуватиметься індекс по колонці PERSON. Але оскільки ми не запитували інформацію у таблиці PERSON, то й звертатися до неї за ID рядків ніхто не буде.

  Даний підхід хороший лише при невеликій кількості звернень, оскільки він дорогий з погляду введення/виведення. Якщо вам потрібно часто звертатися по ID, краще скористатися повним скануванням.

• Інші способи. Про них можна почитати в документації Oracle. У різних БД можуть використовуватися різні назви, але принципи скрізь одні й самі.

4.4.3. Операції об'єднання

Отже, ми знаємо, як отримати дані, настав час їх об'єднати. Але спочатку давайте визначимося з новими термінами: внутрішні залежності та зовнішні залежності. Залежністю може бути:

• таблиця,
• індекс,
• проміжний результат попередньої операції (наприклад, попереднього об'єднання).

Коли об'єднуємо дві залежності, алгоритми об'єднання управляють ними по-різному. Допустимо, A JOIN B є об'єднанням А і В, де А є зовнішньою залежністю, а В - внутрішньою.

Найчастіше вартість A JOIN B не дорівнює вартості B JOIN A.

Припустимо, що зовнішня залежність містить N елементів, а внутрішня - М. Як пам'ятаєте, оптимізатору відомі ці значення завдяки статистиці. N і M є кардинальними числами залежностей.

• Об'єднання за допомогою вкладених циклів.Це найпростіший спосіб об'єднання.

  

  Працює він так: для кожного рядка зовнішньої залежності шукаються збіги по всіх рядках внутрішньої залежності.

  Приклад псеводокоду:

  Nested_loop_join(array outer, array inner) для кожного рядка в іншу для кожного ряду в inner if (match_join_condition(a,b)) write_result_in_output(a,b) end if end for end for
  Оскільки тут подвійна ітерація, тимчасова складність визначається як О(N*M).

  Для кожного з N рядків зовнішньої залежності слід вважати М рядків зовнішньої залежності. Тобто, цей алгоритм вимагає N + N*M читань з диска. Якщо внутрішня залежність досить мала, можна помістити її цілком у пам'ять, і тоді частку дискової підсистеми доведеться лише M + N читань. Тож рекомендується робити внутрішню залежність якомога компактніше, щоб загнати на згадку.

  З погляду тимчасової складності різниці ніякої.

  Також можна замінити внутрішню залежність індексом, це дозволить заощадити операції введення/виведення.
  Якщо внутрішня залежність не влазить у пам'ять цілком, можна використовувати інший алгоритм, більш економно використовує диск.

  • Замість читання обох залежностей рядково вони зчитуються групами рядків (bunch), при цьому в пам'яті зберігається по одній групі з кожної залежності.
  • Рядки з цих груп порівнюються між собою, а знайдені збіги зберігаються окремо.
  • Потім у пам'ять підвантажуються нові групи і також порівнюються одна з одною.
  І так далі, доки групи не закінчаться.

  Приклад алгоритму:

  // Неможлива версія для зменшення диска I/O. nested_loop_join_v2(file outer, file inner) для кожного кнопки ba in outer // ba is now in memory for each bunch bb in iner // bb is now in memory for each row a in ba for each row b in bb if (match_join_ a,b)) write_result_in_output(a,b) end if end for end for end for end for
  В даному випадку тимчасова складність залишається тією ж, зате знижується кількість звернень до диска: (кількість зовнішніх груп + кількість зовнішніх груп * кількість груп внутрішньої). Зі збільшенням розміру груп ще більше зменшується кількість звернень до диска.

  Примітка: у цьому алгоритмі при кожному зверненні зчитується більший обсяг даних, але це не має значення, оскільки звернення послідовні.

• Хеш-об'єднання.Це складніша операція, але у часто її вартість нижче.

  

  Алгоритм наступний:

  1. Зчитуються всі елементи із внутрішньої залежності.
  2. У пам'яті створюється хеш-таблиця.
  3. Один за одним зчитуються всі елементи із зовнішньої залежності.
  4. Для кожного елемента обчислюється хеш (за допомогою відповідної функції хеш-таблиці), щоб можна було знайти відповідний блок у внутрішній залежності.
  5. Елементи з блоку порівнюються з елементами зовнішньої залежності.
  Щоб оцінити цей алгоритм з погляду тимчасової складності, потрібно зробити кілька припущень:
  • Внутрішня залежність містить Х блоків.
  • Хеш-функція розподіляє хеш майже однаково для обох залежностей. Тобто, всі блоки мають ідентичний розмір.
  • Вартість пошуку відповідності між елементами зовнішньої залежності та всіма елементами всередині блоку дорівнює кількості елементів усередині блоку.
  Тоді тимчасова складність дорівнюватиме:

  (М / Х) * (N / X) + вартість_створення_хеш-таблиці(М) + вартість_хеш-функції * N

  А якщо хеш-функція створює достатню маленькі блоки, то тимчасова складність дорівнюватиме О(М + N).

  Є ще один спосіб хеш-об'єднання, що більш економно витрачає пам'ять і не вимагає більше операцій введення/виводу:

  1. Обчислюються хеш-таблиці обох залежностей.
  2. Кладуться на диск.
  3. А потім порівнюються поводерно один з одним (один блок завантажується на згадку, а другий зчитується рядково).
  Об'єднання злиттям.Це єдиний спосіб об'єднання, в результаті якого дані виходять відсортовані. У рамках цієї статті ми розглядаємо спрощений випадок, коли залежності не діляться на зовнішню та внутрішню, оскільки поводяться однаково. Однак у житті вони можуть відрізнятися, скажімо, під час роботи з дублікатами.

  Операцію об'єднання можна поділити на два етапи:

  1. (Опціонально) спочатку здійснюється об'єднання сортуванням, коли обидва набори вхідних даних сортуються за ключами об'єднання.
  2. Потім здійснюється злиття.
  Сортування

  Алгоритм сортування злиттям вже обговорювався вище, в даному випадку він цілком виправдовує себе, якщо вам важливо економити пам'ять.

  Але буває, що набори даних надходять відсортованими, наприклад:

  • Якщо таблицю організовано нативно.
  • Якщо залежність є індексом за умови об'єднання.
  • Якщо об'єднання відбувається із проміжним відсортованим результатом.
  Об'єднання злиттям

  

  Ця операція дуже подібна до операції злиття при процедурі сортування злиттям. Але замість вибору всіх елементів обох залежностей ми вибираємо лише рівні елементи.

  1. Порівнюються два поточні елементи обох залежностей.
  2. Якщо вони рівні, то заносяться до результуючої таблиці, і далі порівнюються два наступні елементи, по одному з кожної залежності.
  3. Якщо вони не рівні, порівняння повторюється, але замість найменшого з двох елементів береться наступний елемент з тієї ж залежності, оскільки ймовірність збігу в цьому випадку вище.
  4. Кроки 1-3 повторюються, поки не закінчаться елементи однієї із залежностей.
  Якщо обидві залежності вже відсортовані, то тимчасова складність дорівнює (N + M).

  Якщо обидві залежності ще потрібно відсортувати, то тимчасова складність дорівнює O(N * Log (N) + M * Log (M)).

  Цей алгоритм працює добре, тому що обидві залежності вже відсортовані, і нам не доводиться пересуватися ними туди-назад. Проте тут допущено деяке спрощення: алгоритм не обробляє ситуації, коли одні й самі дані зустрічаються багаторазово, тобто коли відбуваються багаторазові збіги. Насправді використовується складніша версія алгоритму. Наприклад:

  MergeJoin(relation a, relation b) relation output integer a_key:=0; integer b_key:=0; while (a!=null and b!=null) if (a< b) a_key++; else if (a >b) b_key++; else //Join predicate satisfied write_result_in_output(a,b) //Ви потребуєте, щоб сприяти тому, що зростає потік integer a_key_temp:=a_key; integer b_key_temp:=b_key; if (a != b) b_key_temp:= b_key + 1; end if if (b != a) a_key_temp:= a_key + 1; end if if (b == a && b == a) a_key_temp:= a_key + 1; b_key_temp:= b_key + 1; end if a_key:= a_key_temp; b_key:= b_key_temp; end if end while

Який алгоритм вибрати?

Якби існував найкращий спосіб об'єднання, то не існувало всіх цих різновидів. Отже, відповідь на це питання залежить від купи факторів:

• Об'єм доступної пам'яті. Якщо її мало, забудьте про потужне хеш-об'єднання. Принаймні про його виконання цілком у пам'яті.
• Розмір двох наборів вхідних даних.Якщо у вас одна таблиця велика, а друга дуже маленька, швидше за все спрацює об'єднання за допомогою вкладених циклів, тому що хеш-об'єднання передбачає дорогу процедуру створення хешів. Якщо у вас дві дуже великі таблиці, об'єднання за допомогою вкладених циклів поглине всі ресурси процесора.
• Наявність індексів.Якщо у вас два індекси В-дерев, то краще використовувати об'єднання злиттям.
• Чи потрібно сортувати результат?Можливо, ви захочете використовувати дороге поєднання злиттям (з сортуванням), якщо працюєте з несортованими наборами даних. Тоді на виході ви отримаєте сортовані дані, які зручніше поєднати з результатами іншого об'єднання. Або тому, що запит побічно чи явно передбачає отримання даних, відсортованих операторами ORDER BY/GROUP BY/DISTINCT.
• Чи відсортовані вихідні залежності. У разі краще використовувати об'єднання злиттям.
• Залежність яких типів ви використовуєте. Об'єднання за еквівалентністю (таблиця А. колонка 1 = таблиця Б. колонка 2)? Внутрішні залежності, зовнішні, декартове твір чи самооб'єднання (self-join)? У різних ситуаціях деякі засоби об'єднання не працюють.
• Розподіл даних. Якщо дані відхилені за умовою об'єднання (наприклад, ви об'єднуєте людей на прізвища, але часто зустрічаються однофамільці), то в жодному разі не можна використовувати хеш-об'єднання. Інакше хеш-функція створюватиме кошики з дуже поганим внутрішнім розподілом.
• Чи потрібно виконувати об'єднання у кілька процесів/потоків.

Прагнучи знань можуть заглибитися в документацію з DB2, ORACLE та SQL Server.

4.4.4. Спрощені приклади

Припустимо, нам необхідно об'єднати п'ять таблиць, щоб отримати повне уявлення деяких людей. Кожна людина може мати:

• Декілька номерів мобільних телефонів.
• Декілька адрес електронної пошти.
• Декілька фізичних адрес.
• Декілька номерів банківських рахунків.

Тобто потрібно швидко дати відповідь на цей запит:

SELECT * від PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS WHERE PERSON.PERSON_ID = MOBILES.PERSON_ID AND PERSON.PERSON_ID = MAILS.PERSON_ID AND PERSON.PERSON_ID = ADRESSES.PERSON_ID AND PERSON.PERSON_ID = BANK_ACCOUNTS
Оптимізатору потрібно знайти найкращий спосіб обробки даних. Але є дві проблеми:

1. Який спосіб об'єднання використати? Є три варіанти (хеш-об'єднання, поєднання злиттям, поєднання за допомогою вкладених циклів), з можливістю використання 0, 1 або 2 індексів. Не кажучи вже про те, що індекси також можуть бути різними.
2. В якому порядку потрібно проводити об'єднання?

Наприклад, нижче представлені можливі плани для трьох об'єднань чотирьох таблиць:

З описаного, які є варіанти дій?

1. Використовувати брутфорс-підхід. За допомогою статистики підрахувати вартість кожного з можливих планів виконання запиту та вибрати найдешевший. Але варіантів досить багато. Для кожного порядку об'єднання можна використовувати три різних способи об'єднання, разом 34 = 81 можливих планів виконання. У випадку з бінарним деревом завдання вибору порядку об'єднання перетворюється на задачу про перестановки, і кількість варіантів дорівнює (2*4)! / (4 + 1)!.. В результаті, в даному дуже спрощеному прикладі загальна кількість можливих планів виконання запиту складає 34*(2*4)! /(4+1)! = 27 216. Якщо додати до цього варіанти, коли при об'єднанні злиттям використовується 0, 1 або 2 індекси В-дерева, то кількість можливих планів підвищується до 210 000. Ми вже згадували, що це ДУЖЕ ПРОСТОЙ запит?
2. Поплакати та звільнитися. Дуже спокусливо, але непродуктивно, та й гроші потрібні.
3. Спробувати кілька планів і вибрати найдешевший. Якщо обрахувати вартість всіх можливих варіантів не виходить, можна взяти довільний тестовий набір даних і прогнати по ньому всі види планів, щоб оцінити їхню вартість і вибрати найкращий.
4. Застосувати «розумні» правила зменшення кількості можливих планів.
   Є два типи правил:
   1. Логічні, за допомогою яких можна виключити марні варіанти. Але вони далеко не завжди застосовні. Наприклад, «при об'єднанні з допомогою вкладених циклів внутрішня залежність має бути найменшим набором даних».
   2. Можна шукати найвигідніше рішення і застосувати жорсткіші правила зменшення кількості можливих планів. Скажімо, «якщо залежність мала, використовуємо об'єднання за допомогою вкладених циклів, але ніколи – об'єднання злиттям чи хеш-об'єднання».

Навіть такий простий приклад ставить нас перед величезним вибором. А в реальних запитах можуть бути й інші оператори відносини: OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT і т.д. Тобто кількість можливих планів виконання буде ще більшою.

То як же БД робить вибір?

4.4.5. Динамічне програмування, «жадібний» алгоритм та евристика

Реляційна БД використовує різні підходи, про які було сказано вище. І завданням оптимізатора є пошук відповідного рішення протягом обмеженого часу. Найчастіше оптимізатор шукає не найкраще, а просто гарне рішення.

Брутфорс може підійти у разі маленьких запитів. А завдяки способам унеможливлення непотрібних обчислень навіть для запитів середнього розміру можна використовувати грубу чоловічу силу. Це називається динамічним програмуванням.

Його суть полягає в тому, що багато планів виконання дуже схожі.

На цій ілюстрації всі чотири плани використовують піддерево A JOIN B. Замість обчислення його вартості для кожного плану ми можемо порахувати його лише раз і потім використовувати ці дані стільки, скільки потрібно. Інакше кажучи, з допомогою мемоізації ми вирішуємо проблему перекриття, тобто уникаємо зайвих обчислень.

Завдяки такому підходу замість тимчасової складності (2*N)!/(N+1)! ми отримуємо «лише» 3 N . Щодо попереднього прикладу з чотирма об'єднаннями це означає зменшення кількості варіантів з 336 до 81. Якщо взяти запит із 8 об'єднаннями (невеликий запит), то зменшення складності буде з 57 657 600 до 6 561.

Якщо ви вже знайомі з динамічним програмуванням або алгоритмізацією, можете грати з цим алгоритмом:

Відповідь findbestplan(S) if (bestplan[S].cost infinite) return bestplan[S] // else bestplan[S] не може бути комп'ютером earlier, compute it now if (S contains only 1 relation) set bestplan[S]. план і bestplan[S]. cost based on the best way of accessing S /* Using selections on S and indices on S */ else for each non-empty subset S1 of S таке, що S1 != S P1= findbestplan(S1) P2 = findbestplan(S - S1) A = кращий algorithm для joining результатів P1 і P2 cost = P1.cost + P2.cost + cost A if cost< bestplan[S].cost bestplan[S].cost = cost bestplan[S].plan = “execute P1.plan; execute P2.plan; join results of P1 and P2 using A” return bestplan[S]
Динамічне програмування можна використовувати і для більших запитів, але доведеться вводити додаткові правила (евристику), щоб зменшити кількість можливих планів:


Жадібні алгоритми

Але якщо запит дуже великий, або якщо нам потрібно дуже швидко отримати відповідь, використовується інший клас алгоритмів – жадібні алгоритми.

У разі план виконання запиту будується покроково з допомогою певного правила (евристики). Завдяки йому жадібний алгоритм шукає найкраще рішення кожного етапу окремо. План починається з оператора JOIN, а потім на кожному етапі додається новий JOIN відповідно до правила.

Розглянемо найпростіший приклад. Візьмемо запит із 4 об'єднаннями 5 таблиць (A, B, C, D та E). Дещо спростимо завдання і уявімо, що єдиним варіантом є об'єднання за допомогою вкладених алгоритмів. Будемо використовувати правило "застосовувати об'єднання з найменшою вартістю".

• Починаємо з однієї з таблиць, наприклад А.
• Обчислюємо вартість кожного об'єднання з А (вона буде як у ролі зовнішньої, і внутрішньої залежності).
• Знаходимо, що найдешевше нам обійдеться A JOIN B.
• Потім обчислюємо вартість кожного об'єднання з результатом A JOIN B (його також розглядаємо у двох ролях).
• Знаходимо, що найвигідніше буде (A JOIN B) JOIN C.
• Знову робимо оцінку можливих варіантів.
• Наприкінці отримуємо такий план виконання запиту: (((A JOIN B) JOIN C) JOIN D) JOIN E)/

Той самий алгоритм можна застосувати для оцінки варіантів, що починаються з таблиці B, потім C і т.д. В результаті отримаємо п'ять планів, з яких вибираємо найдешевший.

Цей алгоритм називається «алгоритм найближчого сусіда».

Не заглиблюватимемося в подробиці, але при хорошому моделюванні складності сортування N*log(N) ця проблема може бути . Тимчасова складність алгоритму дорівнює О(N*log(N)) замість О(3 N) для повної версії з динамічним програмуванням. Якщо у вас великий запит з 20 об'єднаннями, то це буде 26 проти 3486784401. Велика різниця, вірно?

Але є нюанс. Ми припускаємо, що якщо знайдемо найкращий спосіб об'єднання двох таблиць, то отримаємо найнижчу вартість об'єднання результатом попередніх об'єднань з наступними таблицями. Однак навіть якщо A JOIN B буде найдешевший варіант, то (A JOIN C) JOIN B може мати вартість нижче, ніж (A JOIN B) JOIN C.

Так що якщо вам конче потрібно знайти найдешевший план усіх часів і народів, то можна порадити багаторазово проганяти жадібні алгоритми з використанням різних правил.

Інші алгоритми

Якщо ви вже ситі по горло всіма цими алгоритмами, можете пропустити цей розділ. Вона не обов'язкова для засвоєння решти матеріалу.

Багато дослідників займаються проблемою пошуку найкращого плану виконання запиту. Найчастіше намагаються знайти рішення для якихось конкретних завдань та шаблонів. Наприклад, для зіркоподібних об'єднань, виконання паралельних запитів тощо.

Шукаються варіанти заміни динамічного програмування виконання великих запитів. Ті ж жадібні алгоритми є підмножиною евристичних алгоритмів. Вони діють за правилом, запам'ятовують результат одного етапу і використовують його для пошуку кращого варіанту для наступного етапу. І алгоритми, які завжди використовують рішення, знайдене для попереднього етапу, називаються евристичними.

Як приклад можна навести генетичні алгоритми:

• Кожне рішення є планом повного виконання запиту.
• Замість одного рішення (плану) алгоритм кожному етапі формує Х рішень.
• Спочатку створюється Х планів, робиться це випадковим чином.
• З них зберігаються ті плани, чия вартості задовольняє певному критерію.
• Потім ці плани змішуються, щоб створити Х нових планів.
• Деякі з нових планів модифікуються випадковим чином.
• Попередні три кроки повторюються у Y разів.
• З планів останнього циклу ми отримуємо кращий.

Що більше циклів, то дешевший план можна розрахувати. Природний відбір, закріплення ознак, це все.
До речі, генетичні алгоритми інтегровані в PostgreSQL.

У БД використовуються й такі евристичні алгоритми, як симульована нормалізація (Simulated Annealing), ітеративне покращення (Iterative Improvement), двофазна оптимізація (Two-Phase Optimization). Але не факт, що вони застосовуються в корпоративних системах, можливо, їхня доля - дослідні продукти.

4.4.6. Справжні оптимізатори

Теж необов'язковий розділ, можна й пропустити.

Давайте відійдемо від теоретизації та розглянемо реальні приклади. Наприклад, як працює оптимізатор SQLite. Це "легка" БД, яка використовує просту оптимізацію на основі жадібного алгоритму з додатковими правилами:

• SQLite ніколи не змінює порядок таблиць операції CROSS JOIN.
• Використовується об'єднання за допомогою вкладених циклів.
• Зовнішні об'єднання завжди оцінюються у порядку, в якому вони здійснювалися.
• До версії 3.8.0 для пошуку найкращого плану виконання запиту використовується жадібний алгоритм «найближчого сусіда» (Nearest Neighor). А з версії 3.8.0 застосовується "N найближчих сусідів" (N3, N Nearest Neighbors).

А ось інший приклад. Якщо почитати документацію IBM DB2, ми дізнаємося, що її оптимізатор використовується 7 різних рівнів оптимізації:

• Жадібні алгоритми:
  • 0 – мінімальна оптимізація. Використовується сканування індексу, об'єднання за допомогою вкладених циклів та виключення перезапису деяких запитів.
  • 1 – низька оптимізація
  • 2 – повна оптимізація
• Динамічне програмування:
  • 3 - середня оптимізація та груба апроксимація
  • 5 - повна оптимізація, використовуються всі евристичні методики
  • 7 - те саме, але без евристики
  • 9 - максимальна оптимізація за будь-яку ціну, не дивлячись на зусилля, що витрачаються. Оцінюються всі можливі способи об'єднання, включаючи декартові твори.

За промовчанням застосовується рівень 5. Сюди входить:

• Збір усієї можливої ​​статистики, включаючи частотні розподіли та квантили.
• застосування всіх правил перезапису запитів, включаючи складання табличного маршруту для матеріалізованих запитів). Виняток становлять правила, потребують інтенсивних обчислень, які застосовуються дуже обмеженого числа випадків.
• При переборі варіантів поєднання за допомогою динамічного програмування:
  • Обмежено використовується складова внутрішня залежність.
  • Для зіркоподібних схем із таблицями перетворення обмежено використовуються декартові твори.
• Розглядається широкий діапазон способів доступу, включаючи попередню вибірку списку (про це нижче), спеціальну операцію з індексами AND та складання табличного маршруту для матеріалів запитів.

Звичайно, розробники не діляться подробицями про евристику, яка використовується в їхньому продукті, адже оптимізатор - чи не найважливіша частина БД. Проте відомо, що за умовчанням визначення порядку об'єднання використовується динамічне програмування, обмежуване евристикою.

Інші умови (GROUP BY, DISTINCT тощо) обробляються простими правилами.

4.4.7. Кеш плану запитів

Оскільки план плану вимагає часу, більшість БД зберігають план в кеші плану запитів. Це допомагає уникнути непотрібних обчислень тих самих етапів. БД має знати, коли саме їй потрібно оновити застарілі плани. І тому встановлюється якийсь поріг, і якщо зміни у статистиці його перевищують, то план, який належить до цієї таблиці, видаляється з кешу.

Виконавець запитів

На цьому етапі наш план вже оптимізований. Він перекомпілюється у виконуваний код і, якщо ресурсів достатньо, виконується. Оператори, які у плані (JOIN, SORT BY тощо.) можуть оброблятися як послідовно, і паралельно, рішення приймає виконавець. Для отримання та запису даних він взаємодіє з диспетчером даних.

5. Диспетчер даних

Диспетчер запитів виконує запит і потребує даних із таблиць та індексів. Він запитує їх у диспетчера даних, але тут є дві проблеми:

• Реляційні БД використовують трансакційну модель. Не можна в конкретний час отримати будь-які бажані дані, тому що в цей час вони можуть кимось використовуватися/модифікуватися.
• Вилучення даних - найповільніша операція у БД. Тому диспетчеру даних потрібно вміти прогнозувати свою роботу, щоби своєчасно заповнювати буфер пам'яті.

5.1. Диспетчер кешу

Як неодноразово говорилося, найвужчим місцем у БД є дискова підсистема. Тому збільшення продуктивності використовується диспетчер кеша.

Замість отримання даних безпосередньо від файлової системи, виконавець запитів звертається за ними до диспетчера кеша. Той використовує буферний пул, що міститься в пам'яті, що дозволяє радикально збільшити продуктивність БД. У цифрах це важко оцінити, оскільки багато залежить від того, що вам потрібно:

• Послідовний доступ (повне сканування) або випадковий (доступ ID рядка).
• Читати чи записувати.

Також велике значення має тип накопичувачів, що використовуються в дисковій системі: вінчестери з різною швидкістю обертання шпинделя, SSD, наявність RAID в різних конфігураціях. Але можна сказати, що використання пам'яті в 100-100 000 разів швидше за диск.

Однак тут ми стикаємося з іншою проблемою. Диспетчеру кешу потрібно покласти дані на згадку ДО того, як вони знадобляться виконавцю запитів. Інакше тому доведеться чекати на їх отримання з повільного диска.

5.1.1. попередження

Виконавець запитів знає, які дані йому знадобляться, оскільки йому відомий весь план, які дані містяться на диску і статистика.

Коли виконавець обробляє першу порцію даних, просить диспетчер кеша заздалегідь підвантажити наступну порцію. А коли переходить до її обробки, просить ДК підвантажити третю і підтверджує, що першу порцію можна видалити з кешу.

Диспетчер кеша зберігає ці дані у буферному пулі. Він також додає до них сервісну інформацію (тригер, latch), щоб знати, чи потрібні вони ще в буфері.

Іноді виконавець не знає, які дані будуть йому потрібні, або деякі БД не мають подібного функціоналу. Тоді використовується спекулятивне попередження (speculative prefetching) (наприклад, якщо виконавець запитує дані 1, 3, 5, то напевно запросить у майбутньому 7, 9, 11) або послідовне попередження (sequential prefetching) (у даному випадку ДК просто підвантажує з диска наступну порядку порцію даних.

Не можна забувати, що буфер обмежений обсягом доступної пам'яті. Тобто для завантаження одних даних нам доводиться періодично видаляти інші. Заповнення та очищення кешу споживає частину ресурсів дискової підсистеми та мережі. Якщо у вас є запит, що часто виконується, то було б контрпродуктивно щоразу завантажувати і очищати використовувані ним дані. Для вирішення цієї проблеми у сучасних БД використовується стратегія заміни буфера.

5.1.2. Стратегії заміни буфера

Більшість БД (принаймні SQL Server, MySQL, Oracle і DB2) використовують для цього алгоритм LRU (Least Recently Used). Він призначений для підтримки в кеші тих даних, які нещодавно використовувалися, а значить, велика ймовірність, що вони можуть знадобитися знову.

Для полегшення розуміння роботи алгоритму приймемо, що у буфері не блокуються тригерами (latch), отже можуть бути видалені. У нашому прикладі буфер може зберігати три порції даних:

1. Диспетчер кешу використовується дані 1 і кладе в порожній буфер.
2. Потім він використовує дані 4 і також відправляє їх у буфер.
3. Те саме робиться і з даними 3.
4. Далі беруться дані 9. Але буфер уже заповнений. Тому з нього видаляються дані 1, оскільки вони не використовувалися найдовше. Після цього буфер поміщаються дані 9.
5. Диспетчер кешу знову використовує дані 4. Вони вже є у буфері, тому позначаються як останні використані.
6. Знову стають затребувані дані 1. Щоб їх помістити в буфер, з нього видаляються дані 3, як найдовше.

Це хороший алгоритм, але має деякі обмеження. Що, якщо у нас здійснюється повне сканування великої таблиці? Що буде, якщо розмір таблиці/індексу перевищує обсяг буфера? В цьому випадку алгоритм видалить з кешу взагалі весь його вміст, таким чином дані повного сканування, швидше за все, будуть використовуватися лише один раз.

Поліпшення алгоритму

Щоб цього не сталося, деякі БД використовуються спеціальні правила. Згідно з документацією Oracle :

«Для великих таблиць зазвичай використовується прямий доступ, тобто блоки даних зчитуються безпосередньо, щоб уникнути переповнення буфера кеша. Для таблиць середнього розміру можна використовувати як прямий доступ, і читання з кеша. Якщо система вирішить використовувати кеш, то БД поміщає блоки даних у кінець списку LRU, щоб запобігти очищенню буфера».

Також використовується покращена версія LRU – LRU-K. У SQL Server застосовується LRU-K при К = 2. Суть цього алгоритму в тому, що при оцінці ситуації він враховує більше інформації про попередні операції, а не тільки запам'ятовує останні використані дані. Літера К у назві означає, що алгоритм бере до уваги, які дані використовувалися останні рази. Їм надається певна вага. Коли в кеш завантажуються нові дані, то старі, але часто використовувані не видаляються, тому що їхня вага вища. Звичайно, якщо дані більше не використовуються, то вони будуть видалені. І чим довше дані залишаються незатребуваними, тим сильніше зменшується з часом їхня вага.

Обчислення ваги досить накладно, тому в SQL Server використовується LRU-K при рівному лише 2. При деякому збільшенні значення До ефективність алгоритму покращується. Ви можете ближче познайомитись з ним завдяки .

Інші алгоритми

Звісно, ​​LRU-K не єдине рішення. Існують також 2Q і CLOCK (обидва схожі на LRU-K), MRU (Most Recently Used, в якому використовується логіка LRU, але застосовується інше правило, LRFU (Least Recently and Frequently Used) і т.д. який алгоритм використовуватиметься.

5.1.3. Буфер запису

Ми говорили тільки про буфер читання, але БД використовують і буфери записи, які накопичують дані та скидають на диск порціями, замість послідовного запису. Це дозволяє заощаджувати операції введення/виводу.
Пам'ятайте, що буфери зберігають сторінки(неподільні одиниці даних), а чи не ряди з таблиць. Сторінка в буферному пулі називається "брудною", якщо вона модифікована, але не записана на диск. Існує багато різних алгоритмів, за допомогою яких вибирається час запису брудних сторінок. Але це багато в чому пов'язане із поняттям транзакцій.

5.2. Диспетчер транзакцій

До його обов'язків входить відстеження, щоб кожен запит виконувався за допомогою власної транзакції. Але перш ніж поговорити про диспетчера, прояснимо концепцію ACID-транзакцій.

5.2.1. «Під кислотою» (гра слів, якщо хтось не зрозумів)

ACID-транзакція (Atomicity, Isolation, Durability, Consistency) – це елементарна операція, одиниця роботи, яка задовольняє 4 умовам:

• Атомарність (Atomicity).Немає нічого «меншого» за транзакцію, ніякої дрібнішої операції. Навіть якщо транзакція триває 10 годин. У разі невдалого виконання транзакції система повертається у стан "до", тобто транзакція відкочується.
• Ізольованість (Isolation). Якщо в один час виконуються дві транзакції А і В, то їх результат не повинен залежати від того, чи одна з них завершилася до, під час або після виконання іншої.
• Надійність (Durability).Коли транзакція зафіксована (commited), тобто успішно завершена, дані, що нею використовувалися, залишаються в БД незалежно від можливих подій (помилки, падіння).
• Консистентність (узгодженість) (Consistency).У БД записуються лише валідні дані (з погляду реляційних та функціональних зв'язків). Консистентність залежить від атомарності та ізольованості.

Під час виконання будь-якої транзакції можна виконувати різні SQL-запити на читання, створення, оновлення та видалення даних. Проблеми починаються, коли дві транзакції використовують одні й самі дані. Класичний приклад - переказ грошей з рахунку А на рахунок Б. Припустимо, ми маємо дві транзакції:

• Т1 бере $100 з рахунку А та відправляє їх на рахунок Б.
• Т2 бере $50 з рахунку А і також відправляє їх на рахунок Б.

Тепер розглянемо цю ситуацію з погляду ACID-властивостей:

• Атомарністьдозволяє бути впевненим, що яка б подія не відбулася в ході Т1 (падіння сервера, збій мережі), не може статися так, що $100 будуть списані з А, але не прийдуть на Б (інакше говорять про «неузгоджений стан»).
• Ізольованістьговорить про те, що навіть якщо Т1 і Т2 здійснюються одночасно, в результаті з А буде списано $100 і та сама сума надійде на Б. У всіх інших випадках знову говорять про неузгоджений стан.
• Надійністьдозволяє не перейматися тим, що Т1 зникне, якщо база впаде відразу після комміту Т1.
• Консистентністьзапобігає можливості створення грошей або їх знищення в системі.

Нижче можна не читати, це вже не важливо для розуміння решти матеріалу.

Багато БД не забезпечують повну ізольованість за умовчанням, оскільки це призводить до великих витрат у продуктивності. У SQL використовується 4 рівні ізольованості:

• Серіалізовані транзакції (Serializable).Найвищий рівень ізольованості. За промовчанням використовується в SQLite. Кожна транзакція виконується у своєму, повністю ізольованому середовищі.
• Повторюване читання (Repeatable read).За замовчуванням використовується MySQL. Кожна транзакція має своє середовище, крім однієї ситуації: якщо транзакція додає нові даніі успішно завершується, то вони будуть видимі для інших транзакцій, що все ще виконуються. Але якщо транзакція модифікує даніі успішно завершується, то ці зміни будуть не видно для транзакцій, що все ще виконуються. Тобто для нових даних принцип ізольованості порушується.

  Наприклад, транзакція А виконує

  SELECT count(1) від TABLE_X
  Потім транзакція Б додає таблицю Х і комітить нові дані. І якщо після цього транзакція А знову виконує count(1), результат буде вже іншим.

  Це називається фантомним читанням.

• Читання зафіксованих даних (Read commited). За замовчуванням використовується в Oracle, PostgreSQL та SQL Server. Це те саме, що й повторюване читання, але з додатковим порушенням ізольованості. Допустимо, транзакція А читає дані; потім вони модифікуються або видаляються транзакцією Б, яка комітує ці дії. Якщо А знову вважає ці дані, вона побачить зміни (чи факт видалення), зроблені Б.

  Це називається неповторним читанням (non-repeatable read).

• Читання незафіксованих даних (Read uncommited).Найнижчий рівень ізольованості. До читання зафіксованих даних додається нове порушення ізольованості. Допустимо, транзакція А читає дані; потім вони модифікуються транзакцією Б (зміни не комітуються, Б все ще виконується). Якщо А рахує дані знову, то побачить зроблені зміни. Якщо ж Б буде відкачена назад, то при повторному читанні А не побачить змін, наче нічого й не було.

  Це називається брудним читанням.

Більшість БД додають власні рівні ізольованості (наприклад, на основі снепшотів, як у PostgreSQL, Oracle та SQL Server). Також у багатьох БД не реалізовано всі чотири вищеописані рівні, особливо читання незафіксованих даних.

Користувач або розробник може відразу після встановлення з'єднання перевизначити рівень ізольованості за замовчуванням. Для цього достатньо додати дуже простий рядок коду.

5.2.2. Управління паралелізмом

Головне, для чого нам потрібні ізольованість, узгодженість та атомарність, це можливість здійснювати операції запису над одними й тими самими даними (додавати, оновлювати та видаляти).

Якщо всі транзакції лише читатимуть дані, то зможуть працювати одночасно, не впливаючи на інші транзакції.
Якщо хоча б одна транзакція змінює дані, які читають інші транзакції, то БД потрібно знайти спосіб приховати від них ці зміни. Також потрібно переконатися, що зроблені зміни не будуть видалені іншими транзакціями, які не бачать змінених даних.

Це називається керуванням паралелізмом.

Найпростіше просто виконувати транзакції по черзі. Але такий підхід зазвичай неефективний (задіюється лише одне ядро ​​одного процесора), до того ж втрачається можливість масштабування.

Ідеальний спосіб вирішення проблеми виглядає так (при кожному створенні чи скасуванні транзакції):

• Моніторити усі операції кожної транзакції.
• Якщо дві і більше транзакції конфліктують через читання/зміни тих самих даних, то змінювати черговість операцій усередині учасників конфлікту, щоб звести до мінімуму кількість причин.
• Виконувати конфліктуючі частини транзакцій у певному порядку. Неконфліктуючі транзакції у цей час виконуються паралельно.
• Мати на увазі, що транзакції можуть бути скасовані.

Якщо підходити до питання формальніше, це проблема конфлікту розкладів. Вирішувати її дуже важко, а оптимізація потребує великих ресурсів процесора. Корпоративні БД не можуть дозволити собі годинами шукати найкращий розклад кожної нової транзакції. Тому використовуються менш досконалі підходи, коли на конфлікти витрачається більше часу.

5.2.3. Диспетчер блокувань

Для вирішення вищеописаної проблеми у багатьох БД використовуються блокування (locks) та/або версійність даних.
Якщо транзакції потрібні якісь дані, вона блокує їх. Якщо інший транзакції вони теж знадобилися, то доведеться чекати, поки перша транзакція не зніме блокування.

Це називається ексклюзивним блокуванням.

Але занадто марнотратно використовувати ексклюзивні блокування у випадках, коли транзакціям потрібно лише вважати дані. Навіщо заважати читання даних? У разі використовуються спільні блокування. Якщо транзакції потрібно рахувати дані, вони застосовує до них спільне блокування та читає. Це не заважає іншим транзакціям також застосовувати спільні блокування та читати дані. Якщо ж якийсь із них потрібно змінити дані, то їй доведеться почекати, доки всі спільні блокування не будуть зняті. Тільки після цього вона зможе застосувати ексклюзивне блокування. І тоді вже всім іншим транзакціям доведеться чекати на її зняття, щоб зчитувати ці дані.

Диспетчер блокувань - це процес, який застосовує та знімає блокування. Вони зберігаються в хеш-таблиці (ключами є дані, що блокуються). Диспетчер знає для всіх даних, які транзакції застосували блокування або чекають на їх зняття.

Взаємне блокування (deadlock)

Використання блокувань може призвести до ситуації, коли дві транзакції нескінченно чекають на зняття блокувань:

Тут транзакція А ексклюзивно заблокувала дані 1 і чекає на звільнення даних 2. У той же час транзакція Б ексклюзивно заблокувала дані 2 і чекає на звільнення даних 1.

При взаємному блокуванні диспетчер вибирає яку транзакцію скасувати (відкотити назад). І рішення ухвалити не так просто:

• Чи краще вбити транзакцію, яка змінила останній набір даних (а отже, відкат буде найменш болючим)?
• Чи краще вбити наймолодшу транзакцію, оскільки користувачі інших транзакцій чекали довше?
• Чи краще вбити транзакцію, якій потрібно менше часу для завершення?
• На скільки інших транзакцій вплине відкат?

Але перш ніж ухвалити рішення, диспетчер повинен переконатися, чи справді виникло взаємне блокування.

Уявімо хеш-таблицю у вигляді діаграми, як на ілюстрації вище. Якщо на діаграмі є циклічний зв'язок, то взаємне блокування підтверджено. Але оскільки перевіряти на наявність циклів досить дорого (адже діаграма, на якій відображені всі блокування, буде дуже великою), найчастіше використовується простіший підхід: використання таймаутів. Якщо блокування не знімається протягом певного часу, це означає, що транзакція увійшла до стану взаємного блокування.

Перед накладанням блокування диспетчер також може перевірити, чи це призведе до виникнення взаємного блокування. Але щоб однозначно відповісти, теж доведеться витратитися на обчислення. Тому подібні передперевірки найчастіше представлені у вигляді набору базових правил.

Двофазне блокування

Найпростіше повна ізольованість забезпечується, коли блокування застосовується на початку та знімається наприкінці транзакції. Це означає, що транзакції перед початком доводиться чекати на зняття всіх блокувань, а застосовані нею блокування знімаються лише після завершення. Такий підхід можна застосовувати, але тоді втрачається купа часу на всі ці очікування зняття блокувань.

У DB2 і SQL Server застосовується протокол двофазного блокування, у якому транзакція ділиться на дві фази:

• Фазу підйому (growing phase), коли транзакція може застосовувати блокування, але не знімати їх.
• Фазу спаду (shrinking phase)коли транзакція може тільки знімати блокування (з даних, які вже оброблені і не будуть оброблятися знову), але не застосовувати нові.

Частий конфлікт, що трапляється у відсутності двофазного блокування:

До транзакції А X = 1 і Y = 1. Вона обробляє дані Y = 1, які були змінені транзакцією вже після початку транзакції А. У зв'язку з принципом ізольованості транзакція А повинна обробляти Y = 2.

Цілі, які вирішуються за допомогою цих двох простих правил:

• Знімати блокування, які не потрібні, щоб зменшити час очікування інших транзакцій.
• Запобігати випадкам, коли транзакція одержують дані, модифіковані раніше запущеною транзакцією. Такі дані не збігаються із запитуваними.

Цей протокол працює чудово, за винятком ситуації, коли транзакція модифікувала дані та зняла з них блокування, після чого було скасовано. При цьому інша транзакція може вважати та змінити дані, які потім будуть відкачені назад. Щоб уникнути подібної ситуації, всі ексклюзивні блокування мають бути зняті після завершення транзакції.

Звичайно, реальні БД використовують складніші системи, більше видів блокувань і з більшою гранулярністю (блокування рядків, сторінок, партій, таблиць, табличних просторів), але суть та ж.

Версійність даних

Ще один спосіб вирішення проблеми конфлікту транзакцій – використання версійності даних.

• Усі транзакції можуть модифікувати одні й самі дані в один і той самий час.
• Кожна транзакція працює із власною копією (версією) даних.
• Якщо дві транзакції змінюють одні й самі дані, то приймається лише одне з модифікацій, інша буде відхилена, а транзакція, що зробила її, буде відкачена (і, можливо, перезапущена).

Це дозволяє збільшити продуктивність, оскільки:

• Транзакції, що читають, не блокують записуючі, і навпаки.
• Неповоротливий диспетчер блокувань не впливає.

Загалом, все що завгодно буде краще, ніж блокування, за винятком випадків, коли дві транзакції записують ті самі дані. І це може призвести до великого перевитрати дискового простору.

Обидва підходи – блокування та версійність – мають плюси та мінуси, багато що залежить від того, в якій ситуації вони застосовуються (більше читань або більше записів). Можете вивчити дуже хорошу презентацію, присвячену реалізації мультиверсійного управління паралелізмом у PostgreSQL.

У деяких базах даних (DB2 до версії 9.7, SQL Server) використовуються тільки блокування. Інші, на кшталт PostgreSQL, MySQL та Oracle, використовуються комбіновані підходи.

Примітка: версійність цікаво впливає на індекси. Іноді в унікальному індексі з'являються дублікати, індекс може містити більше записів, ніж рядків у таблиці і т.д.

Якщо частина даних зчитується при одному рівні ізольованості, а потім він збільшується, то зростає кількість блокувань, а отже, втрачається більше часу на очікування транзакцій. Тому більшість БД не використовують за промовчанням максимальний рівень ізольованості.

Як завжди, за більш детальною інформацією звертайтеся до документації: MySQL, PostgreSQL, Oracle.

5.2.4. Диспетчер логів

Як ми вже знаємо, задля збільшення продуктивності БД зберігає частину даних у буферній пам'яті. Але якщо сервер падає під час коміту транзакції, дані, що знаходяться в пам'яті, будуть втрачені. І це порушує принцип надійності транзакцій.

Звичайно, можна все писати на диск, але при падінні ви залишитеся з недописаними даними, а це вже є порушенням принципу атомарності.

Будь-які зміни, записані транзакцією, мають бути скасовані або завершені.

Це робиться двома способами:

• Тіньові копії/сторінки.Кожна транзакція створює власну копію БД (чи його частина), і з цією копією. У разі помилки копія видаляється. Якщо все пройшло успішно, то БД миттєво перемикається на дані з копії за допомогою одного хитрощі на рівні файлової системи, а потім видаляє «старі» дані.
• Лог транзакції.Це спеціальне сховище. Перед кожним записом на диск БД пише інформацію в лог транзакції. Тож у разі збою БД знатиме, як видалити чи завершити незавершену транзакцію.

WAL

У великих БД з численними транзакціями тіньові копії/сторінки займають багато місця в дисковій підсистемі. Тому в сучасних БД використовується лог транзакції. Він повинен розміщуватись у захищеному від збоїв сховищі.

Більшість продуктів (зокрема, Oracle, SQL Server, DB2, PostgreSQL, MySQL та SQLite) працюють з логом транзакції через протокол WAL (Write-Ahead Logging). Даний протокол містить три правила:

1. Кожна модифікація в БД повинна супроводжуватися записом в балку, і вона повинна вноситися ДО того, як дані будуть записані на диск.
2. Записи в лозі повинні розташовуватися відповідно до черговості відповідних подій.
3. Коли транзакція комітується, запис про це повинен вноситися в лог до моменту успішного завершення транзакції.

За виконанням цих правил стежить диспетчер логів. Логічно він розташований між диспетчером кешу та диспетчером доступу до даних. Диспетчер логів реєструє кожну операцію, яку виконують транзакції, до моменту запису на диск. Начебто правильно?

НЕВЕРНО! Після всього, через що ми з вами пройшли в цій статті, настав час вже запам'ятати, що все пов'язане з БД піддається прокльону «ефекту бази даних». Якщо серйозно, то проблема в тому, що потрібно знайти спосіб писати в балку, при цьому зберігаючи хорошу продуктивність. Адже якщо лог транзакцій працює повільно, то він гальмує всі інші процеси.

ARIES

У 1992 дослідники з IBM створили розширену версію WAL, яку назвали ARIES. У тому чи іншому вигляді ARIES використовується більшістю сучасних БД. Якщо ви захочете вивчити цей протокол глибше, можете проштудувати відповідну роботу .

Отже, ARIES розшифровується як A lgorithms for R ecovery and I solation E xploiting S emantics. Ця технологія має два завдання:

1. Забезпечити хорошу продуктивність під час запису логів.
2. Забезпечити швидке та надійне відновлення.

Є кілька причин, з яких БД доводиться відкочувати транзакцію:

1. Користувач скасував її.
2. Помилка сервера чи мережі.
3. Транзакція порушила цілісність БД. Наприклад, ви застосували до колонки умову UNIQUE, а транзакція додала дублікат.
4. Наявність взаємних блокувань.

Але іноді БД може і відновлювати транзакцію, припустимо, у разі помилки мережі.

Як це можливо? Щоб відповісти на це, спочатку потрібно розібратися з тим, яка інформація зберігається в лозі.

Логи
Кожна операція (додавання/видалення/зміни) під час транзакції веде до появи запису в лозі. Запис містить:

• LSN (Log Sequence Number). Це унікальний номер, значення якого визначається хронологічним порядком. Тобто якщо операція А відбулася до операції Б, LSN для А буде меншим за LSN для Б. Насправді спосіб генерування LSN складніший, оскільки він пов'язаний і зі способом зберігання лога.
• TransID.Ідентифікатор транзакції, яка здійснила операцію.
• PageID. Місце на диску, де є змінені дані.
• PrevLSN. Посилання на попередній запис у лозі, створений тією ж транзакцією.
• UNDO. Спосіб відкату операції.

  Наприклад, якщо була проведена операція оновлення, то в UNDO записується попереднє значення/стан зміненого елемента (фізичний UNDO) або зворотна операція, що дозволяє повернутися до попереднього стану (логічного UNDO). У ARIES використовується лише логічний, з фізичним працювати дуже важко.

• REDO. Спосіб повторення операції.

Крім того, кожна сторінка на диску (для зберігання даних, а не лога) містить LSN останньої операції, модифіковані дані, що містяться тут.

Наскільки відомо, UNDO не використовується лише у PostgreSQL. Натомість використовується збирач сміття, що прибирає старі версії даних. Це з реалізацією версійності даних у цій СУБД.

Щоб вам було легше уявити склад запису в лозі, візуальний спрощений приклад, в якому виконується запит UPDATE FROM PERSON SET AGE = 18;. Нехай він виконується у транзакції номер 18:

Кожен бал має унікальний LSN. Пов'язані логи ставляться до однієї й тієї транзакції, причому лінкуються вони у хронологічному порядку (останній лог списку належить до останньої операції).

Буфер логів
Щоб запис у лог не перетворилася на вузьке місце системи, використовується буфер логів.

Коли виконавець запитів запитує модифіковані дані:

1. Диспетчер кеша зберігає їх у буфері.
2. Диспетчер логів зберігає у своєму буфері відповідний лог.
3. Виконавець запитів визначає, чи завершено операцію, і, відповідно, можна запитувати змінені дані.
4. Диспетчер логів зберігає потрібну інформацію в лог транзакції. Момент внесення запису задається алгоритмом.
5. Менеджер кешу записує зміни на диск. Момент здійснення запису також задається алгоритмом.

Коли транзакція комітується, це означає, що виконані всі кроки з 1 по 5. Запис у лог транзакції здійснюється швидко, оскільки є «додавання лога кудись у лог транзакції». У той же час запис даних на диск є складнішою процедурою, при цьому враховується, що дані згодом повинні бути швидко зчитані.

Політики STEAL та FORCE

Для збільшення продуктивності крок номер 5 потрібно робити після комміту, оскільки у разі збою все ще можна відновити транзакцію за допомогою REDO. Це називається "політика NO-FORCE".

Але БД може вибрати політику FORCE заради зменшення навантаження під час відновлення. Тоді крок номер 5 виконується до коміту.

Також БД вибирає, чи записувати дані на диск покроково (політика STEAL) або якщо диспетчер буфера повинен дочекатися комміта, записати все разом (NO-STEAL). Вибір залежить від того, що вам потрібно: швидкий запис із тривалим відновленням чи швидке відновлення?

Як згадані політики впливають процес відновлення:

• Для STEAL/NO-FORCE потрібні UNDO та REDO. Продуктивність висока, але складніша структура логів і процесів відновлення (на кшталт ARES). Цю комбінацію політик використовує більшість БД.
• Для STEAL/FORCE потрібен лише UNDO.
• Для NO-STEAL/NO-FORCE – тільки REDO.
• Для NO-STEAL/FORCE взагалі нічого не потрібне. Продуктивність у разі найнижча, і потрібно дуже багато пам'яті.

Відновлення

Отже, як нам можна використати наші чудові логи? Припустимо, новий співробітник порушив БД (правило №1: завжди винен новачок!). Ви перезапускаєте її і починається процес відновлення.
ARIES відновлює у три етапи:

1. Аналіз. Зчитується весь лог транзакції, щоб можна було відновити хронологію подій, що сталися під час падіння бази. Це допомагає визначити, яку транзакцію слід відкотити. Відкочуються всі транзакції без наказу про комітет. Також система вирішує, які дані мали записатися на диск під час збою.
2. Повторення. Для оновлення БД до стану перед падінням використовується REDO. Його логи обробляються у хронологічному порядку. Для кожного лога зчитується сторінка LSN на диску, що містить дані, які потрібно змінити.

   Якщо LSN(сторінки_на_диску)>=LSN(записи_в_логе), це означає, що дані вже були записані на диск перед збоєм. Але значення було перезаписано операцією, яка була виконана після запису в лог та до збою. Так що нічого не зроблено насправді.

   Якщо LSN(сторінки_на_диску)

   Повтор виконується навіть для транзакцій, які будуть відкачені, тому що це спрощує відновлення. Але сучасні БД, напевно, цього не роблять.

3. Відміна.На цьому етапі відкочуються всі незавершені на момент збою транзакції. Процес починається з останніх логів кожної транзакції та обробляє UNDO у зворотному хронологічному порядку за допомогою PrevLSN.

У процесі відновлення лог транзакції повинен знати про дії, що виконуються при відновленні. Це потрібно для синхронізації даних, що зберігаються на диск, тими, що записані в лозі транзакції. Можна видалити записи транзакцій, які відкочуються, але це дуже важко зробити. Натомість ARIES вносить компенсуючі записи в лог транзакції, логічно анулюючі записи транзакцій, що відкочуються.

Якщо транзакцію скасовано «вручну», або диспетчером блокувань, або через збій мережі, то етап аналізу не потрібен. Адже інформація для REDO та UNDO міститься у двох таблицях, розміщених у пам'яті:

• У таблиці транзакцій (тут зберігаються стани всіх поточних транзакцій).
• У таблиці брудних сторінок (тут міститься інформація, які дані потрібно записати на диск).

Як тільки з'являється нова транзакція, ці таблиці оновлюються диспетчером кешу та диспетчером транзакцій. Оскільки таблиці зберігаються у пам'яті, то при падінні БД вони пропадають.

Етап аналізу потрібен для відновлення обох таблиць за допомогою інформації з лога транзакцій. Для прискорення цього етапу ARIES використовуються контрольні точки. На диск іноді записується вміст обох таблиць, а також останній на момент запису LSN. Так що під час відновлення аналізуються лише логи, що йдуть після цього LSN.

6. Висновок

Як додатковий оглядовий чтив для бази даних можна порекомендувати статтю Architecture of a Database System. Це добре введення в тему, написане досить зрозумілою мовою.

Якщо ви уважно прочитали весь вищевикладений матеріал, то, напевно, отримали уявлення про те, наскільки великі можливості баз даних. Однак у цій статті не порушені інші важливі проблеми:

• Як керувати кластеризованими БД та глобальними транзакціями.
• Як отримати снепшот, якщо база працює.
• Як ефективно зберігати та стискати дані.
• Як керувати пам'яттю.

Так що подумайте двічі, перш ніж вибирати між забагованою NoSQL та цільною реляційною БД. Не зрозумійте неправильно, деякі NoSQL бази дуже хороші. Але вони ще далекі від досконалості і можуть допомогти лише у вирішенні специфічних проблем, пов'язаних із деякими додатками.

Отже, якщо вас хтось запитає, а як же працюють бази даних, то замість того, щоб плюнути та піти, ви можете відповісти:

Теги: Додати теги