Копитко М.Ф. Основи інформаційних технологій (на укр. языке)

Подождите немного. Документ загружается.

Диск Вміст

1) 11110000

2) 00001111

3) 00111000

4) 01000001

5) ????????

6) 10111110

7) 10001001

Рис. 19. Значення перших блоків усіх дисків після

відновлення диска 2

Додаткові зауваження до схеми RAID рівня 6:

1. Цілком можливо об’єднати ідеї, покладені в основу схем

RAID рівнів 5 і 6, щоб розподілити функції резервування за

номерами блоків або циліндрів з метою зменшення наван-

таження на виокремлені резервні диски.

2. Схема RAID 6-го рівня не є обмеженою чотирма дисками

даних. Загальна кількість дисків може бути на одиницю

меншою потрібного ступеня числа 2, наприклад, 2

-1, де k

дисків є резервними, а решта 2

-k-1 – це диски даних.

Ступінь резервування зростає приблизно як логарифм від

кількості дисків даних. Для довільного k не важко побуду-

вати матрицю, подібну до представленої на рис. 15, стовпці

якої містять усі різні k-бітові послідовності нулів і одиниць,

за винятком набору з k нулів. При цьому стовпці з єдиною

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

дискам даних.

Вправи для опрацювання

Вправа 13. Припустимо, що використовується схема створення

дзеркальних дисків, аналогічна до наведеної в прикладі 18,

причому ймовірність поломки кожного диска у будь-якому році

дорівнює 4%, а на заміну поламаного диска потрібно 8 годин. Який

у цьому випадку середній час напрацювання на відмову, що

спричинить до втрати даних?

Вправа 14. Нехай диск може вийти з ладу протягом певного

року з імовірністю F і на його заміну необхідно H годин.

Визначити:

1) середній час виникнення події втрати даних,

записаний як функція від F і H, якщо використовується

механізм дзеркальних дисків;

2) середній час виникнення події втрати даних,

записаний як функція від F, H і N, якщо використовується

масив RAID рівня 4 або 5, що містить N дисків.

Вправа 15. Припустимо, що група дзеркальних дисків

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

інформацію. Якщо значення ймовірності виходу одного диска з

ладу в будь-якому році дорівнює F, а на його заміну необхідно

H годин, то який середній час виникнення події втрати даних?

Вправа 16. Розглянемо масив RAID рівня 4 з чотирьох дисків

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

будь-якого диска складається з одного байта. Опишіть механізм

отримання даних для резервного диска і визначте вміст блока

резервного диска, якщо відповідні блоки дисків даних такі:

а) 01010110, 11000000, 00111011, 11111011;

б) 11110000, 11111000, 00111111, 00000001.

Вправа 17. Розглянемо масив RAID рівня 4 з чотирьох дисків

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

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

враховуючи такі вимоги:

1) диски 2-4 містять блоки 01010110, 11000000 і 00111011,

відповідно, а резервний диск – блок 11111011;

2) диски 2-4 містять блоки 11110000, 11111000 і 00111111,

відповідно, а резервний диск – блок 00000001.

Вправа 18. Припустимо, що вміст блока першого диска масиву,

розглянутого у прикладі 24, змінено на 10101010. Як треба

модифікувати блоки інших дисків?

Вправа 19. Дано масив RAID рівня 6, утворений відповідно до

схеми, розглянутої у прикладі 24. Блоки чотирьох дисків даних

масиву містять байти 00111100, 11000111, 01010101 і 10000100,

відповідно. Визначити:

1) як повинні виглядати відповідні блоки резервних дисків;

2) якщо значення блока третього диска змінено на 10000000,

то які дії для модифікації вмісту решти дисків треба

виконати?

Вправа 20. Опишіть порядок дій, які необхідно виконати з

метою відновлення даних у масиві RAID рівня 6 з сімома дисками,

розглянутому в прикладі 24, при виході з ладу таких дисків:

а) 1 і 7;

б) 1 і 4;

в) 3 і 6.

Вправа 21. Запропонуйте схему масиву RAID рівня 6 з п’ятнад-

цятьма дисками, чотири з яких є резервними, узагальнивши

матрицю Хеммінга для 7-ми дисків, зображену на рис. 15.

Вправа 22. Запропонуйте схему масиву RAID рівня 6 з десятьма

дисками таку, яка даватиме змогу відновлювати інформацію за

одночасного виходу з ладу трьох дисків.

ПРЕДСТАВЛЕННЯ ЕЛЕМЕНТІВ ДАНИХ

НА ВТОРИННИХ ПРИСТРОЯХ ЗБЕРІГАННЯ

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

вторинних пристроїв зберігання, проте вже на високому

структурному рівні. Розпочнемо з визначення того, як у вторинних

сховищах представляються відношення або множини об’єктів.

• Атрибути відображають як байтові послідовності постійної

або змінної довжини, які називають полями (fields).

• Поля знову ж об’єднуються в набори даних постійної чи

змінної довжини, які позначають терміном запис (record) і

відповідають кортежам або об’єктам.

• Записи зберігаються у фізичних блоках (blocks). Для

формування блоків використовують різні структури даних,

корисні, передусім, у тих ситуаціях, коли зміст даних

змінюється.

• Набори записів, які відповідають відношенням або

екземплярам класів, зберігаються як колекції блоків, які

називають файлами

(files). З метою забезпечення можли-

вості ефективної обробки запитів і команд модифікації таких

колекцій файли доповнюють однією або декількома

структурами індексів (index).

Тема 8. Елементи даних і поля

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

елементи інформації, які зберігаються в базах даних, що керуються

реляційними або об’єктно-орієнтованими системами, – представ-

ляють у формі полів. Зупинимося також на способах об’єднання

полів у більші структури – записи, блоки і файли.

Термін файл у контексті СКБД має ширше поняття, ніж однойменний термін

в операційних системах. Хоча файлом бази даних може бути і неструктурований

потік байтів, найчастіше такі файли складаються з наборів блоків, організованих у

строго визначеному порядку, які допускають індексування і застосування

ефективних спеціалізованих методів доступу до їхнього змісту.

8.1. Представлення елементів реляційних баз даних

Припустимо, що в контексті реляційної бази даних засобами

SQL-команди CREATE TABLE, яку представлено на рис. 20,

оголошено відношення з іменем MovieStar. Задача структурування

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

на відповідну СКБД. Оскільки відношення є множиною кортежів, а

кортежі за означенням подібні із записами або «структурами» (у

розумінні, яке прийнято в мові програмування С++), можна

припустити, що кожен кортеж буде збережено на диску як окремий

запис. Запис займає деякий дисковий блок або його частину, а в

середині запису значенню кожного компонента кортежу відповідає

певне поле.

1) CREATE TABLE Movie Star (

2) name CHAR(30) PRIMARY KEY,

3) address VARCHAR (255),

4) gender CHAR(1),

5) birthdate DATE

);

Рис. 20. Приклад відношення, оголошеного мовою SQL

Хоча на перший погляд все виглядає просто і прозоро, насправді

тут не все так просто, отож наберемось терпіння і спробуємо

відповісти на кілька запитань.

1. Як представляють у формі полів значення типів даних

SQL?

2. Як кортежі зберігаються у формі записів?

3. Як набори записів або кортежів відображаються у фізичних

блоках пам’яті?

4. Як відношення оформляються і зберігаються у вигляді

колекцій блоків?

5. Що робити, якщо кортежам відповідають записи різної

довжини або записи точно не поміщаються в межах блоків?

6. Що відбувається, коли після оновлення вмісту деякого поля

розмір запису змінюється? Як відшукати необхідний

простір усередині блока, передусім у тих випадках, коли

довжина запису збільшується?

Першій проблемі присвячено цю тему. Два наступні питання

висвітлено у темі 9, останні – у темах 11 і 12, відповідно. Четверта

тема, яка зачіпає такі способи представлення відношень, які

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

відношень, вивчатимемо у розділі 3.

Заслуговують уваги і методи низького рівня представлення

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

вуються в сучасних об’єктно-реляційних і об’єктно-орієнтованих

системах, а саме – ідентифікаторів об’єктів (або покажчиків на

записи) та об’єктів типу «BLOB» (наприклад, відеофрагментів

формату MPEG об’ємом у декілька гігабайтів). Цю інформацію

буде викладено у темах 10 і 11.

8.2. Представлення об’єктів

У деякому наближенні об’єкт можна сприймати як кортеж, а

його поля – як компоненти атрибутів. Кортежі в об’єктно-

реляційних базах даних вельми нагадують кортежі «звичайних»

(реляційних) баз даних. Однак існує кілька цікавих обставин, про

які ми не згадували у пункті 8.1.

1. Об’єкт можна асоціювати з функціями, які називають

методами. Код методів є частиною схеми класу, до якого

належить об’єкт.

2. Кожен об’єкт, зазвичай, володіє власним ідентифікаційним

номером (object identity – OID), який можна трактувати, як

певну адресу в деякому глобальному адресному просторі,

що однозначно визначає цей об’єкт. Об’єкти нерідко

зв’язують з іншими об’єктами. Подібні зв’язки описують

покажчиками або списками покажчиків.

Код методів зберігається у схемі, отож належить базі даних

загалом, а не окремим об’єктам. З метою забезпечення можливості

звертання до методу, однак, необхідно, щоб запис, який представ-

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

го класу.

Способи представлення адрес – чи це є ідентифікаційний номер

об’єкта чи посилання на інший об’єкт – обговорюватимемо у

темі 10. Зв’язки – як їх розглядають у мові ODL (Object Definition

Language – мова визначення об’єктів), – належать об’єктові,

й інформацію про них необхідно якось зберігати в базі даних.

Оскільки кількість взаємозв’язаних об’єктів, які підлягають

створенню, наперед невідома (щонайменше, у тих випадках, коли

йдеться про об’єкти, з’єднані зв’язками типу «багато до багатьох»

або які належать до категорії «багато» зв’язків вигляду «багато до

одного»), то для опису зв’язків випадає користуватися записами

змінної довжини (детальніше про це – у темі 11).

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

Розпочнемо з вивчення способів зберігання елементів даних, які

є основними типами SQL (Додаток Г). Їх представляють як поля

записів. Важливо розуміти, що всі дані описуються послі-

довностями байтів. Наприклад, значення атрибута типу INTEGER,

зазвичай, відображається у двох або чотирьох байтах, а для типу

FLOAT необхідно від 4-х до 8-ми байтів. Цілі і дійсні числа

представлено наборами бітів, які інтерпретуються апаратним забез-

печенням комп’ютера так, щоб зробити можливим виконання

традиційних арифметичних операцій.

Символьні рядки постійної довжини. Найпростіший різновид

рядків символів описується в SQL – типом CHAR(n), який визначає

множину рядків постійної довжини n. Поле, що відповідає

атрибуту подібного типу, є масивом з n байтів (це справедливо для

8-бітових наборів символів ASCII, адже символ у форматі Unicode

представляється як 16 бітів або 2 байта). Якщо значенням атрибута

є коротший рядок, то в кожну «зайву» позицію поля заноситься

спеціальний незначущий (pad) символ, 8-бітовий код якого не

збігається з кодом будь-якого з тих символів, які дозволено

включати в рядки SQL.

Приклад 26. Якщо оголошення атрибута А засвідчує його

приналежність до типу CHAR(5), то поля, які відповідають

атрибутові, в усіх кортежах становитимуть масиви з 5-ти символів.

Якщо компонент атрибута А в одному з кортежів повинен містити

'cat', то масив виглядатиме так

c a t ┴ ┴

Тут ┴ представляє незначущий символ-заповнювач, код якого

заноситься у четвертий і п’ятий байти-елементи масиву.

Зауважимо, що символи одинарних лапок, які використовують для

позначення рядків у SQL-програмах, до значення рядка не

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

Символьні рядки змінної довжини. Інколи довжина рядкових

значень компонента певного атрибута відношення може

змінюватися у широких межах. У таких випадках атрибути,

зазвичай, відносяться до типу VARCHAR(n). Загалом, при реалі-

зації подібних типів під значення можна відводити n+1 байт

незалежно від справжнього розміру рядка. Отож SQL-тип

VARCHAR насправді є полем фіксованої довжини, хоча розмір

вмісту може змінюватися. Особливості полів і записів даних

змінної довжини ми детально розглянемо у темі 11.

Згадаємо коротко два загальних способи представлення рядків

типу VARCHAR.

1. Довжина плюс вміст. Система організує масив з n+1 байта.

У першому байті як 8-бітове ціле число зберігається

кількість байтів у рядку. Довжина рядка не може

перевищувати n, а величина n, також не повинна бути

більшою від 255 – інакше довжину рядка не можна пред-

ставити за допомогою одного байта. Другий і наступні

байти відображають символи рядка. Якщо рядок склада-

ється з меншої кількості символів, решта байтів масиву не

може інтерпретуватися як частина вмісту, отож нею ігно-

рують.

2. Рядки, які закінчуються символом null. У цьому випадку

також формується масив з n+1 байта. Масив заповнюється

символами рядка, а в елемент, розташований за останнім

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

який не збігається з жодним із символів, що дозволено

використовувати всередині рядків SQL. Як і в поперед-

ньому випадку, рештою байтів масиву ігнорують.

Приклад 27. Припустимо, що оголошення атрибута А містить

тип VARCHAR (10). У записах, які представляють кортежі

відношення з атрибутом А, створюються поля-масиви довжиною

11 байтів для зберігання компонентів атрибута А. Нехай значенням

одного з компонентів є рядок ‘cat’. Тоді, згідно з першим підходом,

у початковий байт масиву заноситься число 3, яке задає довжину

рядка, а в наступні 3 байти – символи рядка. Значеннями решти

семи байтів ігнорують. У цьому випадку масив набуде вигляду:

3 c a t

Зауважимо, що «3» – це 8-бітове ціле число (тобто 00000011), а

не символ ‘3’.

Керуючись другим підходом, система заповнить три перших

байти масиву символами рядка, а в четвертий занесе символ null:

с a t ┴

Значення дати і часу. Значення дати, зазвичай, представляється

як символьні рядки постійної довжини і принципово нічим не

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

Часові величини передбачають аналогічне представлення. У кон-

кретних реалізаціях SQL значенням дати і часу відповідають спе-

ціальні типи даних DATE(‘1948-05-14’) і TIME (‘15:00:03.1415’).

Формат значень TIME належить до категорії рядків довільної

довжини, оскільки він дає змогу зберігати значення часу з точністю

до дробових часток секунди. Отже, існує два альтернативні засоби

опису значень часу:

1. Система здатна обмежити точність представлення часових

величин так, ніби вони належать до типу VARCHAR(n), де

n – максимально допустима довжина рядка з описом зна-

чення часу.

2. Часові значення можуть зберігатися і використовуватися як

рядки дійсно змінної довжини (за деталями звертайтесь до

теми 11).

Бітові послідовності. Послідовності бітів, описані значеннями

SQL-типу BIT(n), ділять на групи з 8-ми бітів у кожній, які

упаковуються в байти. Якщо n не ділиться на 8 без остачі, то

зайвими бітами останнього байта ігнорують. Наприклад, бітову

послідовність 010111110011 легко описати двома байтами –

01011111 і 00110000. Останні чотири нулі другого байта не є

частиною значення поля.

У частковому випадку байт можна використовувати для

представлення логічної величини, тобто вмісту єдиного біта –

10000000 (true) і 00000000 (false). У деяких ситуаціях вигіднішим є

представлення, коли величини true і false відрізняються в усіх бітах

байта – відповідно, 11111111 і 00000000.

Перелічені типи. Інколи зручне використання мають такі

атрибути, вміст яких вибирають із фіксованих множин значень.

Подібним значенням присвоюють символьні імена. Тип, в

оголошенні якого зазначають набір символьних імен, називають

переліченим (enumerative type). Прикладом перелічених типів слу-

гують множини назв днів тижня {SUN, MON, TUE, WED, THU,

FRI, SAT} або кольори {RED, GREEN, BLUE, YELLOW}.

Значення перелічених типів можна представити цілочисловими

кодами з використанням необхідної кількості байтів. Наприклад,

для опису значення RED можна взяти число 0, значення GREEN −

1, BLUE − 2; YELLOW − 3. Для представлення подібної множини

цілих чисел достатньо двох бітів – відповідно, 00, 01, 10, 11.

Зрештою, навіть у тих випадках, коли множина значень

переліченого типу мала, то зручніше використовувати цілі байти, а

не їхні частини. За такого підходу значенню YELLOW відповіда-

тиме байт 00000011. Загалом за допомогою одного байта можна

представити до 256-ти різних значень переліченого типу. За

необхідності беруть більше байтів (наприклад, цілочисловий тип

SHORTINT).

Тема 9. Записи

Поговоримо про способи формування записів (record), які

об’єднують у себе групи полів. Подібні питання розглядатимемо

також у темі 11, присвяченій полям і записам змінної довжини.

Загалом кожному типу запису, використаному в контексті бази

даних, необхідно ставити у відповідність схему, яка також