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

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

Міністерство освіти і науки України

Львівський національний університет імені Івана Франка

М.Ф. Копитко

Основи інформаційних технологій

Тексти лекцій

Львів

Видавничий центр ЛНУ імені Івана Франка

2007

УДК [004.08+004.42+004.6](042.4)

ББК З 973я73-2+3988я73-2

К-65

Рецензенти:

Д-р. фіз.-мат. наук, проф. М.М.Притула

(Львівський національний університет імені Івана Франка)

Д-р. фіз.-мат. наук, проф. Р.О.Слоньовський

(Національний університет «Львівська політехніка»)

Рекомендовано до друку Вченою радою

факультету прикладної математики та інформатики

Протокол № 4 від 21.09.2005р.

Рекомендовано до друку Вченою радою

Львівського національного університету імені Івана Франка

Протокол № 35/9 від 28.09.2005р.

Копитко М.Ф.

К-65 Основи інформаційних технологій: Тексти лекцій. −

Львів: Видавничий центр ЛНУ ім. Івана Франка, 2007.−

259 с.

Викладено основи інформаційних технологій: вирішення

проблем зберігання інформації, представлення елементів

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

ефективного доступу до даних.

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

програмістів, які створюють сучасні інформаційні технології.

ВСТУП

Інформаційні технології – це сукупність методів і програмно-

технічних засобів, об’єднаних у технологічний ланцюжок, що

забезпечує збирання, оброблення, зберігання, поширення та відо-

браження інформації з метою зменшення трудомісткості процесів

використання інформаційного ресурсу, а також підвищення їхньої

надійності та оперативності.

За роки розвитку технічних засобів комп’ютера і відповідного

програмного забезпечення виникло стільки інформаційних техно-

логій, скільки потрібно, щоб охопити всі сторони життєдіяльності

людини. Залежно від того, яку інформацію вони обробляють або де

їх використовують, інформаційні технології отримують назви:

Internet-технології, WWW-технології, офісні інформаційні системи,

мережеві технології, геоінформаційні технології, технології баз

даних тощо. Кожен з цих напрямів використання вивчають студен-

ти в базових і спеціальний курсах. Тож що є основою усіх цих

технологій?

На думку автора, в основі інформаційних технологій, передусім

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

виникають такі проблеми: як зберігати великі об’єми інформації; як

змістовно формувати інформацію в записи і блоки; як ефективно

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

висвітленню цих проблем присвячено тексти лекцій.

У першому розділі розглянуто проблеми зберігання інформації.

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

інформації, передусім дискам. Оцінено швидкодію алгоритмів

обробки даних, які необхідно переміщати між оперативною

пам’яттю і вторинними або третинними пристроями зберігання. На

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

злиттям проілюстровано, як використовувати різні прийоми

пониження часових затрат на операції читання даних з диска і

записування даних на диск. Розглянуто також методи підвищення

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

помилки читання-запису, а також зберегти дані після поломки

одного чи декількох дисків.

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

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

рівноцінних щодо них сутностей, які застосовують в інших

моделях представлення інформації, – згідно з вимогами блочної

моделі дискових даних. Тобто проілюстровано відображення

атрибутів як байтових послідовностей (їх називають полями)

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

об’єднуються в набори даних постійної або змінної довжини (їх

називають записами) і відповідають кортежам або об’єктам.

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

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

при модифікації даних.

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

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

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

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

вторинні індекси для невпорядкованих файлів, В-дерева для

організації індексів для довільних файлів, геш-таблиці для

представлення індексів.

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

які використовують в геоінформаційних системах і системах

підтримки прийняття рішень. У ньому розглянуто особливості

побудови індексів для швидкого доступу до просторових даних.

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

функцій, індексів з декількома ключами, kd-дерев, дерев

квадрантів, R-дерев.

Протягом усього видання виклад матеріалу супроводжується

прикладами і вправами для самостійного виконання.

ПРИНЦИПИ ЗБЕРІГАННЯ ІНФОРМАЦІЇ

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

(СКБД) справляються з великими об’ємами інформації. Проблема

зводиться до двох основоположних питань:

1) як комп’ютерна система зберігає дані і керує ними;

2) які форми представлення і структури даних найкраще

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

даних?

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

ня крупних масивів інформації (зокрема, диски), розглянемо

ієрархію пристроїв пам’яті і продемонструємо, як швидкодія

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

порцій інформації між оперативною пам’яттю і вторинними

(зазвичай, дисками) або навіть третинними пристроями зберігання.

Звернемо увагу на різні прийоми зниження часових затрат на

операції читання даних з диска та їхнє записування. Також

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

дають змогу подолати помилки читання-записування і навіть

випадки цілковитої «відмови» диска.

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

вигаданої СКБД, в основу якої покладено неправильні проектні

рішення, що не відповідають загальноприйнятій практиці.

Тема 1. Приклад вигаданої системи баз даних

Якщо Ви вже користувались будь-якою СКБД, то, ймовірно,

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

Назвемо нашу вигадану СКБД Straw. Ця система належить до

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

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

1.1. Особливості реалізації СКБД Straw

У базовій версії Straw для збереження відношень (інформацію

про реляційну модель даних подано у додатоку А) використовують

файлову систему UNIX. Наприклад, відношення Students (name,

id, dept) можна подати як файл /USR/db/Students. Кожен запис у

файлі Students відповідає одному кортежу. Значення компонентів

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

символами-маркерами #. Вміст файла /USR/db/Students може

виглядати, наприклад, так:

Smith # 123 # CS

Vasyl Sydorchuk # 522 # EE

…

Опис схеми бази даних розміщується у спеціальному файлі

/usr/db/schema. Кожному відношенню бази даних відповідає один

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

далі подано пари імен атрибутів і їхні типи. Всі елементи рядка

розділяються позначкою # Файл /usr/db/schema може зберігати

такі рядки:

Students # name # STR # id # INT # dept # STR

Depts # name # STR # office # STR

…

Тут ми вважаємо, що файл schema містить опис відношення

Students (name, id, dept) із рядковими (STR) атрибутами name i

dept і цілочисловим (INT) атрибутом id, а також відношення

Deps(name, office).

Приклад 1. Розглянемо звичайний сеанс взаємодії з СКБД

Straw. Нам надано право звертатися до користувального інтерфейсу

Straw, вводячи необхідні команди SQL у відповідь на запрошення

(&) системи. Отож запит до бази даних вигляду

& SELECT ∗ FROM Students #

повертає таблицю:

Name id dept

Smith 23 CS

Vasyl Sydorchuk 522 EE

СКБД Straw дає змогу зберігати результати виконання запитів у

нових файлах: з цією метою текст команди необхідно доповнити

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

виконання команди

& SELECT ∗ FROM Students WHERE id >= 500 | Highid #

створить файл /usr/db/Highid, який містить один рядок:

Vasyl Sydorchuk #522 # ЕЕ

1.2. Як СКБД Straw виконує запити

Розглянемо типову форму SQL-запиту:

SELECT ∗ FROM R WHERE <умова>

У відповідь на подібний запит Straw виконує такі дії:

1) звертається до файла schema за інформацією про атрибути

відношення R і їхні типи;

2) перевіряє, чи правильно задана <умова> з погляду

семантики відношення R;

3) передає на екран комп’ютера заголовок результату запиту з

найменуванням атрибутів, підкреслений лінією;

4) зчитує файл, який відповідає відношенню R, і для кожного

рядка-запису:

а) перевіряє <умову>;

в) якщо <умова> правильна, виводить на екран рядок-

кортеж.

Під час виконання команди типу

SELECT ∗ FROM R WHERE <умова> | T

Straw виконує такі дії:

1) опрацьовує запит так, як і раніше, проте пропускає п.3,

тобто не генерує заголовка результуючого відношення;

2) зберігає результат у новому файлі /usr/db/T;

3) додає у файл /usr/db/schema рядок з описом відношення T,

подібний до рядка з інформацією про схему відношення R.

Приклад 2. Розглянемо складніший запит, який передбачає

з’єднання (join) кортежів двох відношень Students і Depts :

SELECT office

FROM Students, Depts

WHERE Students.name = `Smith` AND

Studets.dept = Depts.name #

Запит змушує систему здійснити з’єднання відношень Students

і Depts, тобто розглянути кожну пару кортежів (по одному з

перелічених відношень) і визначити, чи :

1) містять компоненти Studets.dept і Depts.name один і той

самий рядок з назвою факультету;

2) є прізвищем студента (Students.name) рядок "Smith".

Алгоритм виконання цього запиту неформально може виглядати

так:

FOR (ДЛЯ) кожного кортежу s із Studets (ВИКОНАТИ) DO

FOR (ДЛЯ) кожного кортежу d із Depts (ВИКОНАТИ) DO

IF (ЯКЩО) s і d задовольняють умову WHERE (ТОДІ) THEN

відобразити значення компонента office кортежу d;

1.3. Негативні моменти в системі Straw

Зазвичай, ні для кого не є сюрпризом, що «справжні» СКБД

реалізуються зовсім не так, як вигадано Straw. Можна назвати

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

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

водночас підключених до системи користувачів. Перерахуємо

тільки деякі з багатьох можливих проблем.

• Методика розміщення кортежів на дисках не відзначається

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

Якщо, наприклад, в одному з кортежів відношення Students

необхідно змінити значення компонента dept з EE на ECOM,

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

кожен наступний символ на дві позиції «вниз».

• Операції пошуку надзвичайно трудомісткі. Система завжди

повинна переглядати відношення загалом – навіть у тих

випадках, коли (як в запиті з прикладу 2) задано одне чи

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

обмеженій групі кортежів.

• Система не передбачає можливості буферизації окремих

«корисних» фрагментів даних в оперативній пам’яті;

кожного разу, коли виникає потреба в отриманні тієї чи

іншої інформації, вони зчитуються з диска знову.

• У системі не передбачено засобів керування паралельними

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

модифікувати один і той самий файл, що може спричинити

до непередбачуваних наслідків.

• Система ненадійна. У випадку збоїв дані можна втратити, а

операції – перервати.

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

вирішувати перелічені вище проблеми і які використовують для

роботи з великими об’ємами інформації.

Тема 2. Ієрархія пристроїв пам’яті

Типова комп’ютерна система налічує кілька компонентів,

призначених для зберігання даних. Компоненти розрізняють за

місткістю і швидкістю доступу до даних, а також вартістю

зберігання байта інформації. Ступінь відмінностей значень перших

двох параметрів оцінюється, щонайменше, у сім порядків.

Величини вартості зберігання байта інформації в компонентах

також відрізняються, проте не так серйозно – вартість найдешев-

ших компонентів на три порядки нижча, ніж найдорожчих. Не має

нічого дивного в тому, що пристрої найменшої ємності мають

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

вартість зберігання одного байта. Схему ієрархії пристроїв пам’яті

комп’ютера наведено на рис. 1.

9 Корисно знати. Одиниці вимірювання об’є-

мів пам’яті. За традицією говорять про місткість

комп’ютерних компонентів пам’яті так, ніби її

вимірюють степенями числа 10 – мегабайти, гіга-

байти і т.д. Насправді, пристрої пам’яті,

(наприклад, напівпровідниковий чіп) проектують

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

дорівнює степені числа 2. Саме тому, що величина

=1024 не дуже відрізняється від тисячі,

прийнято використовувати для скороченого запису

префікс «кіло», 2

– «мега», 2

– «гіга», 2

– «тера» і 2

– «пета». Ті ж префікси в

областях, далеких від інформаційних технологій,

означають, відповідно – 10

, 10

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

шується, адже 10

=1 000 000, а один мегабайт −

=1 048 576 байт. Для позначення префікса

«кіло» використовують стандартне скорочення «К»,

«мега» – «М», «гіга» –»Г», «тера» – «Т», «пета»

– «П». Наприклад, 16 Гбайт – це, строго кажучи,

байт.

Для вимірювання часу роботи тих чи інших при-

строїв комп’ютера використовують, здебільшого,

секунди, помножені на від’ємну степінь числа 10,

а саме 10

-3

с – 1 мілісекунда (мс); 10

-6

с – 1

мікросекунда (мкс), 10

-9

с – 1 наносекунда (нс),

-12

с – 1 пікосекунда (пс).

Третинні

пристрої

зберігання

Кеш-пам’ять

Оперативна пам’ять

Вірту

альна

пам’ять

Файлова

система

Диск

Програми;

СКБД,

розташовані в

оперативній

пам’яті

СКБД

Рис.1. Ієрархія пристроїв пам’яті