Класифікація службових програмних засобів

Базовий рівень

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

Системний рівень

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

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

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

Службовий рівень

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

Прикладний рівень

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

САМОСТОЯТЕЛЬНАЯ РАБОТА № 2

«Стиснення даних»

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

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

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

1. Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв'язку або до транспортування на зовнішніх носіях малої ємності;
2. Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні;
3. Стиснення (ущільнення) дисків: використовується для підвищення ефективності використання дискового простору шляхом стиснення даних при записі їх на носії інформації (як правило, засобами операційної системи).

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

Якщо при стисненні даних відбувається зміна їх вмісту, то метод стиснення є незворотнім, тобто при відновленні (розархівуванні) даних з архіву не відбувається повне відновлення інформації. Такі методи часто називаються методами стиснення з регульованими втратами інформації. Зрозуміло, що ці методи можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не приводить до суттєвого спотворення інформації. До таких типів даних відносяться відео- та аудіодані, а також графічні дані. Методи стиснення з регульованими втратами інформації забезпечують значно більший ступінь стиснення, але їх не можна застосовувати до текстових даних. Прикладами форматів стиснення з втратами інформації можуть бути: JPEG (Joint Photographic Experts Group) для графічних даних; MPG - для для відеоданих; MP3 - для аудіоданих.

Якщо при стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадкові з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення у порівнянні з незворотними методами стиснення. Приклади форматів стиснення без втрати інформації: GIF (Graphics Interchange Format), TIFF (Tagged Image File Format) - для графічних даних; AVI - для відеоданих; ZIP, ARJ, RAR, CAB, LH - для довільних типів даних. Існує багато різних практичних методів стиснення без втрати інформації, які, як правило, мають різну ефективність для різних типів даних та різних обсягів. Однак, в основі цих методів лежать три теоретичних алгоритми:

• алгоритм RLE (Run Length Encoding);
• алгоритми групи KWE(KeyWord Encoding);
• алгоритм Хафмана.

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

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

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

Чим менше значення коефіцієнта стиснення, тим ефективніший метод стиснення. Зрозуміло, що алгоритм RLE буде давати кращий ефект стиснення при більшій довжині послідовності даних, що повторюється. У випадкові розглянутого вище прикладу, якщо вхідна послідовність матиме такий вигляд: 1 1 1 1 1 1 3 4 4 4, то коефіцієнт стиснення буде рівний 60%. У зв'язку з цим найбільша ефективність алгоритму RLE досягається при стисненні графічних даних (особливо для однотонових фонових зображень).

Алгоритми групи KWE

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

Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано або пізно поточний рядок перестає відповідати якій-небудь фразі словника. У цей момент, коли поточний рядок являє собою останній збіг зі словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символа, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним снмвола, додається в словник. У наступний раз, коли ця фраза з'явиться в повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації.

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

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

Алгоритм Хафмана

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

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

Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера 'А' входить 10 разів, літера 'B' - 8 раз, 'C'- 6 разів , 'D' - 5 разів, 'E' і 'F' - по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у таблиці 1.

Таблиця 1.

Символ	Частота входження	Бітовий код
A	10	00
B	8	01
C	6	100
D	5	101
E	4	110
F	4	111

Як видно з таблиці 1, розмір вхідного тексту до стиснення рівний 37 байт, тоді як після стиснення - 93 біт, тобто майже 12 байт (без врахування довжини словника). Коефіцієнт стиснення рівний 32%. Алгоритм Хафмана універсальний, тобто його можна застосовувати для стиснення даних будь-яких типів, але він малоефективний для файлів малих розмірів (за рахунок необхідності зберігання словника).

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

Таблиця 2.

Формат стиснення	Операційна система MS DOS		Операційна система Windows
	Програма архівування	Програма розархівування	Програма архівування	Програма розархівування
ARJ	Arj.exe	Arj.exe	WinArj.exe	WinArj.exe
RAR	Rar.exe	Unrar.exe	WinRar.exe	WinRar.exe
ZIP	Pkzip.exe	Pkunzip.exe	WinZip.exe	WinZip.exe

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

1. створення нового архіву;
2. додавання файлів в існуючий архів;
3. розпакування файлів з архіву;
4. створення архівів, що саморозпаковуються (self-extractor archive);
5. створення розподілених архівів фіксованих розмірів для носіїв малої ємності;
6. захист архівів паролями від несанкціонованого доступу;
7. перегляд вмісту файлів різних форматів без попереднього розархівування;
8. пошук файлів і даних всередині архіву;
9. перевірка на віруси в архіві до розпакування;
10. вибір та налаштування коефіцієнта стиснення.

Контрольні запитання

1. Які фактори впливають на ступінь надлишковості даних?
2. Що таке архів? Які програмні засоби називаються архіваторами?
3. Чому методи стиснення при яких відбувається зміна вмісту даних називаються незворотніми?
4. Наведіть приклади форматів стиснення з втратами інформації.
5. В чому полягає перевага зворотніх методів стиснення над незворотніми? А недолік?
6. Яка існує залежність між коефіцієнтом стиснення та ефективністю методу стиснення?
7. В чому полягає основна ідея алгоритму RLE?
8. В чому полягає основна ідея алгоритмів групи KWE?
9. В чому полягає основна ідея алгоритму Хафмана?
10. Які ви знаєте програми-архіватори? Коротко охарактеризуйте їх.

 

САМОСТОЯТЕЛЬНАЯ РАБОТА №3

ТЕМА:  Средства для работы с БД. Работа с утилитой BDE Administrator

Общий обзор средств для работы с базами данных

В состав Delphi Client/Server Suite входят следующие средства для разработки и эксплуатации приложений, использующих базы данных:

• BDE (Borland Database Engine), машина баз данных фирмы Borland

Представляет собой набор библиотек. Должна устанавливаться на каждом компьютере, который использует приложения для работы с БД, написанные на Delphi. Выполняет действия по доступу к данным и проверке их правильности. Является, по существу, центральным средством для работы с БД из приложений, созданных с помощью Delphi.

•SQL Links

Драйверы для работы с удаленными "промышленными" СУБД, такими как Sybase, MS SQL Server, Oracle. Для работы с "родным" SQL-сервером Borland InterBase устанавливать SQL Links нет необходимости. Доступ к таблицам локальных ("настольных", "персональных") СУБД типа Paradox, dBase также осуществляется BDE напрямую, без использования SQL Links.

• BDE Administrator

Утилита для установки псевдонимов (имен) баз данных, параметров БД и драйверов баз данных на конкретном компьютере. При работе с БД из приложения, созданного с помощью Delphi, доступ к базе данных производится по ее псевдониму (имени). Параметры БД, определяемой псевдонимом, действуют только для этой БД; параметры, установленные для драйвера БД, действуют для всех баз данных, использующих драйвер. Кроме этого, в утилите BDE Administrator можно произвести установку таких общих для всех БД параметров, как формат даты и времени, форматы представления числовых значений, используемый языковый драйвер и т.д. Поддерживает информацию о конфигурации БД на конкретном компьютере в файле IDAPI32.CFG.

 

• Database Desktop (DBD)

Средство для создания, изменения и просмотра БД. Эта утилита прежде всего ориентирована на работу с таблицами локальных ("персональных") СУБД, таких как Paradox и dBase. В ряде случаев может использоваться и для работы с таблицами удаленных СУБД. Например, из DBD можно с некоторыми ограничениями создавать таблицы БД, работающих под управлением InterBase, Oracle, и просматривать их содержимое.

Общая модель взаимодействия приложения, реализованного с помощью Delphi, со средствами БД приведена на рис. 3.1.

• Database Explorer (SQL Explorer)

Утилита для конфигурирования псевдонимов БД, просмотра структуры БД, таблиц БД, выдачи запросов к БД, создания словарей данных.

•SQL Monitor

Средство для трассировки выполнения SQL-запросов.

• Visual Query Builder

Средство в составе интегрированной среды Delphi для автоматического создания SQL-запросов методом QBE (Query By Example, запрос по образцу).

• Data Dictionary

Словарь данных. Средство для хранения атрибутов полей таблиц БД отдельно от самих БД и приложений. Информация о полях может использоваться различными приложениями.

• Data Module

Невизуальные компоненты типа TDataModule применяются для централизованного хранения наборов данных в приложении, работающем с БД. Одним из главных удобств является приписывание каждому набору данных правил по управлению данными. Такие правила называются бизнес-правилами. Они обычно определяют реакцию системы при добавлении, изменении, удалении данных, при вводе ошибочных значений и реализуют блокировку действий, которые могут разрушить ссылочную и смысловую целостность БД.

Такие бизнес-правила, хранящиеся централизованно на уровне приложения, при использовании одного и того же набора данных в разных формах приложения, позволяют унифицировать поведение БД на уровне всего приложения.

• Object Repository

Репозиторий объектов Delphi. Будучи единожды разработанными для какого-либо приложения, формы с визуальными и невизуальными компонентами, а также компоненты TDataModule могут сохраняться в репозитории. Тогда они могут использоваться другими, вновь создаваемыми приложениями. Таким образом устраняется необходимость повторного написания идентичного или схожего кода в приложениях.

• Data Migration Wizard

Средство для перемещения данных между БД различных типов

• Невизуальные компоненты для работы с БД

Невизуальные компоненты Delphi служат для соединения приложения с таблицами БД. Они расположены на странице компонентов Data Access палитры компонентов в интегрированной среде разработки Delphi. Невизуальный компонент "перетаскивается" из палитры компонентов в форму разрабатываемого приложения. После этого Delphi автоматически описывает в форме экземпляр компонента указанного класса. Далее разработчик определяет свойства компонента, кодирует обработчики событий, где в программном коде вызывает необходимые ему методы компонента.

• Визуальные компоненты для работы с БД

Визуальные компоненты Delphi предназначены доя визуализации записей наборов данных (например, компонент TDBGrid) или отдельных полей текущей записи набора данных (например, TDBEdit, TDBText). Эти компоненты расположены на странице компонентов Data Controls палитры компонентов в интегрированной среде разработки Delphi. Визуальный компонент "перетаскивается" из палитры компонентов в форму разрабатываемого приложения. После этого Delphi автоматически описывает в форме экземпляр компонента указанного класса. Далее разработчик определяет соединение визуального компонента с невизуальными компонентами, определяет по необходимости различные свойства компонента, кодирует обработчики событий, где в программном коде вызывает необходимые ему методы компонента.

• Компоненты для построения отчетов

В интегрированной среде разработчика Delphi на странице палитры компонентов QReport размещено около двух десятков компонентов для построения отчетов. Их добавление в приложение происходит аналогично добавлению визуальных компонентов для работы с данными.

Ранее поставлявшееся в составе Delphi автономное средство ReportSmith с Delphi версии 3 более не поставляется.

• Local InterBase Server

Локальная однопользовательская версия SQL-сервера Borland InterBase. Поддерживает 2 активных соединения клиентов с сервером. Используется в основном для создания БД, отладки клиентских приложений, которые будут работать с Удаленными БД. В дальнейшем, после отладки, БД переносятся на действительно удаленный сервер, а приложение клиентского места перенастраивается для работы с удаленной БД. Данная перенастройка обычно не требует больших трудозатрат.

 

• InterBase Server for Windows 95

4-х-пользовательская версия SQL-сервера Borland InterBase, которая может устанавливаться на компьютерах, работающих под управлением Windows 95. Используется для тех же целей что и Local InterBase Server, однако на InterBase for Windows 95 можно производить отладку в многопользовательском режиме, что важно для проверки корректности изменений, одновременно вносимых пользователями в БД при параллельной работе с ней.

Создание псевдонима БД

Параметры БД и ее местоположение определяются псевдонимом БД. Псевдоним - это некоторое имя (псевдоним БД). Именно этот псевдоним и используют при логическом обращении к БД компоненты типа "набор данных" приложения Delphi, например TTable и TQuery. BDE считывает параметры, поставленные в соответствие данному псевдониму, что во многом определяет ее дальнейшие действия по физической работе с БД.

Псевдонимы баз данных определяются в утилите BDE Administrator. Для того, чтобы определить псевдоним, необходимо:

 

1. Выбрать элемент меню Object \ New;

2. Выбрать в появившемся окне имя драйвера базы данных (STANDARD для Paradox и dBase, MSACCESS для Microsoft Access, ORACLE INTRBASE, SYBASE, MSSQL, INFORMIX, DB2 соответственно для баз данных Oracle, InterBase, Sybase, MS SQL Server, Informix, DB2 и, если установлен, драйвер ODBC);

4. Ввести имя псевдонима в левом окне;

5. Определить необходимые параметры псевдонима в правом окне.

6. Щелкнуть по псевдониму правой кнопкой мыши и выбрать во всплывающем меню элемент Apply для подтверждения или Cancel для отказа.

Поскольку в настоящей книге основной упор делается на использование "родных" баз данных Borland (Paradox и InterBase), опишем далее параметры драйверов этих баз данных. Для получения информации о создании псевдонимов БД иных типов обратитесь к системной документации и встроенной системе помощи.

Структуры данных

База данных, организованная с помощью инвертированных списков, похожа на реляционную БД, но с тем отличием, что хранимые таблицы и пути доступа к ним видны пользователям. При этом:

· строки таблиц упорядочены системой в некоторой физической последовательности;

· физическая упорядоченность строк всех таблиц может определяться и для всей БД (так делается, например, в Datacom/DB).

· для каждой таблицы можно определить произвольное число ключей поиска, для которых строятся индексы. Эти индексы автоматически поддерживаются системой, но явно видны пользователям.

Манипулирование данными

Поддерживаются два класса операторов:

1. Операторы, устанавливающие адрес записи, среди которых:

· прямые поисковые операторы (например, найти первую запись таблицы по некоторому пути доступа);

· операторы, находящие запись в терминах относительной позиции от предыдущей записи по некоторому пути доступа.

2. Операторы над адресуемыми записями

Примеры операторов:

· LOCATE FIRST - найти первую запись таблицы T в физическом порядке; возвращает адрес записи;

· LOCATE FIRST WITH SEARCH KEY EQUAL - найти первую запись таблицы T с заданным значением ключа поиска K; возвращает адрес записи;

· LOCATE NEXT - найти первую запись, следующую за записью с заданным адресом в заданном пути доступа; возвращает адрес записи;

· RETRIVE - выбрать запись с указанным адресом;

· UPDATE - обновить запись с указанным адресом;

· DELETE - удалить запись с указанным адресом;

· STORE - включить запись в указанную таблицу; операция генерирует адрес записи.

Ограничения целостности

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

Типичным представителем (наиболее известным и распространенным) является Information Management System (IMS) фирмы IBM. Первая версия появилась в 1968 г.

Манипулирование данными

Примерами типичных операторов манипулирования иерархически организованными данными могут быть следующие:

· найти указанное дерево БД;

· перейти от одного дерева к другому;

· перейти от одной записи к другой внутри дерева (например, от группы - к первому студенту);

· перейти от одной записи к другой в порядке обхода иерархии;

· вставить новую запись в указанную позицию;

Как можно добавить новую запись к данным, уничтожить старые записи и при этом не нарушить системы адресации и поиска, а также сами структуры данных.

Укажем основные факторы, влияющие на физическую организацию данных для конкретных БД:

1. произвольная или последовательная обработка данных. Для определения вид обработки используют коэффициент активности файла (k)

k=z1/z , где z1 – число записей, считанных за 1 прогон; z - число записей, просмотренных за 1 прогон. Если k высок, то используют последовательную обработку, например при расчете заработной платы;

2. частота обращения к определенным записям;

3. время ответа (важно для систем реального времени);

4. способность к расширению (особенно, если добавляется записей больше, чем уничтожается);

5. возможность организации поиска по нескольким ключам.

Можно выделить следующие способы адресации (поиска нужной записи):

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

2. Блочный поиск. Если записи упорядочены по ключу, то при сканировании не требуется чтение каждой записи. Считывается первая запись блока и ее ключ сравнивается с ключом искомой записи. А далее или просматриваются все записи данного блока или выбирается первая запись следующего блока.

3. Преобразование ключа в адрес - самая быстрая организация поиска. Сейчас применяется технология хеширования – технология быстрого доступа к хранимой записи на основе вычисления специальной функции от заданного значения некоторого поля. Это значение и является адресом для записи.

4. Поиск по индексу. Первичный индекс – индекс, использующий в качестве входной информации первичный ключ. В индексном файле запись состоит из индекса и указателя. Сначала проводится поиск в индексе, а потом по указателю обращаемся к основному файлу с записями. Эффективно, быстро, но требуется память для хранения индекса.

5. Бинарный (двоичный) поиск для записей, упорядоченных по ключу.

6. Поиск по В-дереву.

Исторически первыми системами хранения и доступа были файловые структуры и системы управления файлами (СУФ), которые фактически являлись частью операционных систем. СУБД создавала над этими файлами свою надстройку, которая позволяла организовать всю совокупность файлов таким образом, чтобы она работала как единое целое и получала централизованное управление от СУБД. При этом непосредственный доступ осуществлялся на уровне файловых команд, которые СУБД использовала при манипулировании файлами.

Однако механизмы буферизации и управления файловыми структурами не приспособлены для решения задач собственно СУБД, так как создавались для традиционной обработки файлов, и с ростом объемов хранимых данных они стали неэффективными для использования СУБД. Тогда постепенно произошел переход от базовых файловых структур к непосредственному управлению размещением данных на внешних носителях самой СУБД. При этом механизмы, применяемые в файловых системах, перешли во многом и в новые системы организации данных во внешней памяти, называемые чаще страничными системами хранения информации. Любое упорядоченное расположение данных на диске, называется структурой хранения. На рис. 2.5 приведена классификация структур хранения информации в БД.

Рисунок. 2.5 - Классификация структур хранения информации в БД

Этапы доступа к БД

Рисунок 2.7 Схема доступа к БД

 

 

Опишем последовательность действий при доступе к БД:

1. Сначала в СУБД определяется искомая запись, а затем для ее извлечения запрашивается диспетчер файлов (ДФ).

2. Диспетчер файлов одним из рассмотренных способов адресации определяет страницу, на которой находится искомая запись, а затем для ее извлечения запрашивается диспетчер дисков (ДД).

Возврат хранимых записей возврат хранимых записей возврат хранимых страниц

3. Диспетчер дисков определяет физическое положение искомой страницы на диске и посылает запрос на ввод – вывод данных (страница уже может находиться в ОЗУ).

С точки зрения СУБД база данных выглядит как набор записей, которые могут просматриваться с помощью ДФ. С точки зрения ДФ БД выглядит как набор страниц, которые могут просматриваться с помощью ДД.

ДД часто бывает компонентом ОС, с помощью которого выполняются все операции ввода/вывода, используя физические адреса записей. Однако ДФ не обязательно знать физические адреса записей, достаточно рассматривать диск как набор страниц фиксированного размера с уникальным идентификатором набора страниц.

Страница внутри набора обладает уникальным идентификационным номером страницы.

Соответствие физических адресов на диске и номера станиц достигается с помощью ДД.

Преимущества страничной организации - все компоненты высокого уровня не зависят от конкретного диска.

Диск – это набор хранимых файлов. Файл – хранимый набор однотипных записей. В общем случае хранимый файл может храниться в памяти различными способами:

· на одном томе памяти (диске);

· на нескольких томах;

· физически упорядоченным в соответствии со значением некоторого хранимого поля;

· упорядоченным с помощью одного или нескольких индексов;

· упорядоченным с помощью цепочек указателей;

· к нему может быть обеспечен доступ методом хэш-адресации;

· хранимые записи могут быть объединены в блоки (несколько логических записей в одной физической записи).

Набор страниц может содержать несколько хранимых файлов. Каждый хранимый файл имеет имя или идентификационный номер (file ID), уникальный в данном наборе страниц. А каждая хранимая (логическая) запись обладает идентификационным номером (record ID).

 

ДФ выполняет следующие операции с файлами:

1. извлечь хранимую запись r из хранимого файла f;

2. заменить хранимую запись r в хранимом файле f;

3. удалить хранимую запись r из хранимого файла f;

4. добавить новую хранимую запись r в хранимый файл f;

5. создать новый хранимый файл f;

6. удалить хранимый файл f.

Компоненты модели данных

Сущность - это что-то такое, о чем нужно хранить информацию в базе данных.

При проектировании баз данных достаточно описать происходящую ситуацию - и большинство существительных и часть глаголов будут кандидатами на сущности. Например: "Покупатели покупают товары. Сотрудники продают товары покупателям. Поставщики поставляют товары" - покупатели, товары, сотрудники и поставщики - это сущности. Глаголы "покупать" и "продавать" - тоже сущности (хотя могут быть и одной сущностью, разной с точки зрения покупателя и продавца).

При проектировании БД главный источник информации о сущностях - это беседа с заказчиком в целях уяснения его бизнес-процессов. Кроме того, анализируются стандартные документы, используемые в бизнес-процессах: бланки, отчеты, инструкции и т.п. После получения такого списка необходимо проверить его на полноту и связность, а также выявить дубли - одинаковые сущности, которые называются разными словами, и сущности, которые на самом деле отличаются, но описываются один и тем же термином.

Сущности могут моделировать конкретные понятия (клиенты, товары, звонки) и абстрактные (агент отвечает за клиента, студент записан на курс).

Последовательный метод

В этом методе предполагается физическое расположение записей в логической последовательности. Для выборки записи необходимо просмотреть все предшествующие ей. Очевидно, что эффективность доступа линейно зависит от длины файла. Как правило, время доступа в этом случае недопустимо велико. С другой стороны, для этого метода характерна очень высокая эффективность хранения. Кроме того, алгоритм доступа к данным крайне прост. Следовательно, метод не может применяться там, где необходим быстрый доступ к данным большого объема. Но его можно использовать в тех случаях, когда по характеру задачи следует выбирать записи последовательно (например, полное копирование данных), а также при очень небольших объемах данных в силу простоты алгоритма доступа.

Прямой метод

Для прямого метода необходимо взаимно однозначное соответствие между ключом и адресом записи. В этом случае некоторая адресная функция (возможно, тривиальная) формирует адрес, по которому выбирается запись. Это наиболее эффективный метод по времени доступа, эффективность доступа всегда равна единице. Эффективность хранения зависит от плотности размещения ключей. Если это справочная (неизменяемая) таблица, ключи могут располагаться достаточно плотно. В общем случае этот метод довольно расточителен по памяти.

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

Индексные методы

В основе индексных методов доступа лежит создание вспомогательной структуры – индекса, содержащего ключи поиска и ссылки на физические адреса данных. Термин «ключ поиска» не обязательно подразумевает его уникальность, это просто атрибут (комбинация атрибутов), который должен удовлетворять критерию поиска. Используются понятия первичного (уникального) ключа, и вторичного, который не обязательно должен быть уникальным.

Доступ к данным производится в два этапа. Вначале в индексе (индексном файле) находятся требуемые значения ключей, затем из основного файла по ссылке извлекается требуемая информация. Разумеется, ни эффективность доступа, ни эффективность хранения при использовании этих методов не могут достигать единицы, но производительность системы в целом может стать достаточно высокой. Для ее увеличения обычно требуют, чтобы индекс целиком размещался в оперативной памяти.

Индексы могут быть устроены по-разному. Различаются первичные и вторичные индексы в зависимости от вида ключа поиска. Если поиск и выборка производится по комбинации атрибутов (индексному выражению), соответствующий индекс называется составным. Индекс, построенный на иерархии ссылок, называется многоуровневым. Индекс, который содержит ссылки не на все записи, а на некоторый диапазон, называется неплотным. Плотный индекс содержит ссылки на все записи. Элемент индекса часто называют статьей.

Существует множество индексных методов доступа. Рассмотрим три из них: индексно-последовательный, индексно-произвольный и метод инвертированных списков.

Индексно-произвольный метод

В отличие от предыдущего, этот метод основан на использовании плотного индекса. В этом случае число статей индекса равно количеству информационных записей. Суть метода состоит в следующем. Для информационной структуры (файла) формируется индекс, который содержит значения ключей поиска и ссылки на соответствующие записи. При поиске записи вначале в индексе выбирается статья с искомым ключом, затем по ссылке выбирается непосредственно требуемая запись. Поиск однозначен, если он производится по первичному или другому уникальному индексу. В случае вторичного ключа результат поиска – выборка из записей с равными ключами.

Как и в индексно-последовательном методе, нужно стремиться к тому, чтобы весь индекс размещался в памяти. Но в данном случае, в силу плотности индекса, ситуация хуже из-за большего размера индекса. Более того, иногда он может превышать размер информационного файла. Уменьшение области поиска достигается, например, построением многоуровневого индекса. Ключи обычно бывают упорядоченными для последующего дихотомического поиска, но не исключаются и другие алгоритмы. Естественно, упорядоченность записей в информационном файле не существенна, однако иногда она позволяет заметно сократить время работы. Например, выдача отчета по всему файлу с сортировкой по ключу поиска приведет к последовательному просмотру статей индекса, но к хаотичному выбору записей в случае их сильного перемешивания по этому ключу. Это, в свою очередь, приводит к «дерганью» головки дисковода, что резко увеличивает время доступа. Решение проблемы – сортировка по ключу поиска. К замедлению поиска приводит и дублирование значений ключей, следовательно, этот метод наиболее эффективен для первичных индексов.

Итак, эффективность доступа во многом зависит от способа поиска статьи индекса, то есть от способа его организации. Кроме того, на него могут оказывать влияние некоторые свойства ключей (случайное расположение в файле, повторяемость).

Эффективность хранения зависит от размера индекса.

Пример

Бабаев  Назаров  Артюхов  Беляев  Днепров  Селин  Яковлева  Мурадян

Артюхов 3 Бабаев 1 Беляев 4 Днепров 5 Мурадян 8 Назаров 2 Селин 7 Яковлева 6

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

Инвертированные списки

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

Считается, что поиск может проводиться по значениям любых полей (вторичных ключей) или их комбинации. Для каждого вторичного ключа создается индекс. В нем на каждое значение ключа формируется список указателей на записи файла с этим значением. Это не обязательно физическая ссылка, допускается и первичный ключ. Таким образом, инвертированный индекс группируется по именам полей, которые в свою очередь группируются по значениям. При поиске записи с заданным значением ключа выбирается нужный индекс, в нем каким-то способом (например, индексно-произвольным) выбирается статья с этим значением, затем выбирается все список ссылок на записи с искомым значением. Легко видеть, что поиск по комбинации значений полей сводится к выбору соответствующих списков и их пересечению (операция И) или объединению (операция ИЛИ).

Достоинства метода – независимость от объема файла при выборе данных по произвольным значениям ключа, отбор списка записей по сложным условиям без обращения к файлу. Особенно эффективно применение инвертированных списков при выборке данных по совокупности критериев, если атрибуты имеют сравнительно небольшой диапазон значений. Недостаток – большие затраты времени на создание и обновление инвертированных индексов, причем, время зависит от объема данных. Этот метод обычно используется лишь для поиска. Для начальной загрузки данных и обновления используют другие методы.

Эффективность доступа зависит от эффективности поиска в индексе, но в любом случае она ниже 0,5 (доступ к индексу и доступ к записи файла). Для повышения эффективности следует размещать индексы в оперативной памяти.

Эффективность хранения зависит от метода хранения индекса, от числа инвертируемых полей и от множества значений каждого вторичного ключа (от длины инвертированного списка).

Пример

Студент     Оценка    Бабаев              3  Назаров            5  Артюхов          4  Беляев               5  Днепров               4  Селин               3  Яковлева              4

Запись 1 6

Запись 3 5 7

Запись 2 4 8

Оценка     список      3           1      4          2  5          3

 

В приведенном примере в информационном файле (правый прямоугольник) размещается список студентов с оценками. Требуется выбрать всех студентов, имеющих одинаковое значение оценки. Левый прямоугольник символизирует индекс, в котором находится единственный вторичный ключ – «оценка». Каждому его значению соответствует список, в котором перечислены соответствующие номера записей информационного файла. Выбор всех двоечников сводится к нахождению в индексе соответствующего значения ключа «оценка» и загрузки записей, указанных в списке. Если нужно найти тех, кто получил «4» или «5», следует найти и объединить соответствующие списки. Подобные действия выполнялись бы, если бы запись содержала еще один вторичный ключ, скажем, предмет. Тогда для выборки тех, кто получил пятерки по предмету «Базы данных», следовало бы в соответствующих индексах найти списки для требуемых значений и взять их пересечение.

 

Контрольные вопросы

1. Для чего предназначено свойство индексированное поле?

2. Есть ли необходимость в хэш-коде при индексировании? Почему?

3. Чем отличается бинарный метод поиска от последовательного?

4. В какой схеме индексирования таблиц недостатки менее существенны?

5. Приведите четыре примера оценки эффективности доступа и хранения.

6. В чём отличие индексно-последовательного метода от метода инвертирования списков?

7. Приведите несколько несхожих примеров для каждого из трёх основных методов доступа.

 

САМОСТОЯТЕЛЬНАЯ РАБОТА №7

ТЕМА: Основные принципы нормализации. Фундаментальные свойства отношений

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

Помните, что нормальные формы не являются руководством для создания «правильной» модели данных. Модель данных может быть совершенной с точки зрения теории нормализации, но созданная на ее основе реальная база данных будет выдавать требуемые результаты столь медленно и неуклюже, что ее просто не удастся использовать. Тем не менее, если ваша модель данных нормализована (то есть удовлетворяет принципам, принятым для реляционных структур) шансы получить в результате эффективную модель данных увеличиваются. Перед тем, как мы вернемся к нормализации, ознакомимся с несколькими принципами, лежащими в ее основе.

Декомпозиция без потерь

Реляционная модель позволяет различным образом соединять отношения, связывая их через атрибуты. Процесс получения полностью нормализованной модели данных включает в себя устранение избыточности. Для этого отношение, содержащее избыточные данные, разбивают на несколько других отношений. Нужно сделать это так, чтобы получившиеся в результате отношения можно было бы вновь соединить и получить точную копию структуры и данных исходного отношения. Это и есть принцип декомпозиции без потерь. Например, вы можете получить из отношения, два других отношения.

 

Накладная №123