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

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

Линейный список – самый простой способ физической организации баз данных. В отличие от остальных трех способов он не требует создания дополнительных файлов. В соответствие с этим способом файл базы данных рассматривается как последовательность невзаимосвязанных записей. Поиск любой из них выполняется путем вычисления адреса записи по некоторому алгоритму. По критерию “минимум памяти” это самый экономичный способ. Однако по быстродействию он проигрывает остальным способам.

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

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

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

Пример цепного списка приведен в графическом и табличном виде.

Фиксатор списка

4

Адрес начала списка

АС

АС

АС

АС

КС

Ясин

Сидоров

Петров

Иванов

АНС

ФС

4

Иванов

a+0

a+3

a+1

Петров

+1

a+2

+2

КС

Сидоров

+3

a+0

Ясин

В этом примере элементы списка размещены в памяти последовательно в порядке: Иванов – Петров – Сидоров – Ясин, а выборка элементов, заданная указателями, записанными в АНС и АС, осуществляется в порядке: Петров – Иванов – Ясин – Сидоров. В поле АС последнего, читаемого в логическом порядке элемента списка указан признак конца списка (КС).

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

Цепные списки наиболее удобны для представления во внешней памяти сетевых модулей данных.

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

---

Пример:

Основной файл Инвертированный файл

Фамилия	Год		Фамилия	Год
Борисов А.А.	1970		Иванов Р.С.	1969
Ярин С.Д.	1969		Ярин С.Д.	1969
Иванов Р.С.	1969		Борисов А.А.	1970

Здесь приведена база данных в составе основного файла, где записи упорядочены по ключевому полю ФАМИЛИЯ, и инвертированного файла ИФ_ГОД, записи которого упорядочены по неключевому полю Год основного файла. При вводе запроса “найти сотрудников с годом рождения, меньшим 1970” поиск данных необходимо вести не в основном файле, в котором для нашего примера достаточно прочитать две первые записи.

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

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

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

Основной файл Индекс И 1

	Фамилия	Год	…		Год	Адреса
001	Борисов А.А.	1970	…		1959	004
002	Ярин С.Д.	1969	…		1969	002, 003
003	Иванов Р.С.	1969	…		1970	001
004	Петров О.П.	1959	…

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

14. Хешированные, индексированные файлы

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

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

---

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

Если индексирование организовано на основе ключевого поля, то индекс называется первичным. Ключевые поля, как правило, индексируются автоматически.

Если индекс организован на основе другого поля, то он называется вторичным. Индекс, организованный на основе ключевого поля или другого ключа, называется уникальным.

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

- последовательного доступа к индексированному файлу, т. е. в последовательности, заданной значениями индексного поля;

- прямого доступа к отдельным записям индексированного файла на основе заданного значения индексного поля.

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

Хеширование распределяет записи в таблице по определённым участкам. То есть выбирается столбец, по которому производится индексирование и для каждого значения столбца хеш-функция должна вырабатывать значение, соответствующее номеру участка (например, старые записные телефонные книжки, ключ – фамилия, имена людей). Функция хеширования для ключа выдаёт номер участка. При поиске записи по значению ключа K хеш-функция выдаст адрес, указывающий на начало того участка памяти, в котором надо искать эту запись. Доступ к данным возможен за одно обращение к диску. Пример, функция – деление на 5. И берётся остаток от этого деления, то есть распределим данные таблицы по 5-ти участкам.

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

15. Защита баз данных.

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

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

В журнальном файле регистрируются все изменения в БД с некоторого периода времени. Копия БД должна быть выполнена на момент начала введения журнального файла, такой тип восстановления БД принято называть восстановлением “вперед”.

---

Защита от некорректных обновлений. Она предупреждает неверное использование данных (в первую очередь – обновления другими пользователями).

Такая защита данных называется логической целостностью.

Каким же средствами она обеспечивается? По всей видимости, это должны быть механизмы управления доступом пользователей к данным. К ним, во – первых, относятся ограничения доступа пользователя ко всей базе данных. Благодаря программным “фильтрам”, определенным администратором БД, каждый пользователь имеет возможность обрабатывать лишь некоторое подмножество данных. Следовательно, все прочие данные уже защищены от возможных искажений этим пользователем.

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

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

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

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

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

Проблемы могут возникнуть, когда процедура обновления завершается аварийно. В данном случае разблокировать данные для доступа к ним других пользователей не достаточно, поскольку предварительно требуется выполнить откат, и эта задача возлагается на администратора БД. При откате (или восстановлении “назад”) будут аннулироваться все изменения БД, инициализированные процедурой обновления.

Для выполнения ряда специальных обработок (не обязательно связанных с обновлением БД), а также при работе с ИС администратора БД или администратора предметной области может быть использован абсолютно монопольный режим. В этом режиме данные полностью блокируются до завершения сеанса их обработки.

---

Шифровка – преобразование читаемого текста в нечитаемый текст при помощи алгоритма; Метод простой шифровки состоит в замене каждой буквы на следующий за ней в алфавите.

16.Целостность и сохранность баз данных.

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

Выделяют три группы правил целостности:

1. Целостность по сущностям.

2. Целостность по ссылкам.

3. Целостность, определяемая пользователем.

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

Организация ЭВМ и систем

1. Основные характеристики, области применения ЭВМ различных классов;

2. функциональная и структурная организация процессора;

3. организация памяти ЭВМ;

4. основные стадии выполнения команды; организация прерываний в ЭВМ;

5. организация ввода-вывода; периферийные устройства;

6. архитектурные особенности организации ЭВМ различных классов;

7. параллельные системы;

8. понятие о многомашинных и многопроцессорных вычислительных системах.

1. Основные характеристики, области применения ЭВМ различных классов

Тактовая частота — более мелкая единица измерения, чем операции в секунду.

Надежность — это способность ЭВМ при определенных услови­ях выполнять требуемые функции в течение заданного времени (стан­дарт ISO (Международная организация стандартов) -2382/14-78).

Точность ~ возможность различать почти равные значения.

Традиционно электронную вычислительную техни­ку подразделяют на аналоговую и цифровую.

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

В настоящее время под словом ЭВМ обычно понимают цифровые вычислительные машины, в которых информация кодируется двоич­ными кодами чисел.

Академик В.М. Глушков указывал, что существуют три глобаль­ные сферы деятельности человека, которые требуют использования качественно различных типов ЭВМ.

---

Смотрите также файлы

• Рабочая тетрадь по теоретической механике 3.pdf

• Информационные технологии. Лекции.docx

• Инструктаж по технике безопасности на уроках информатики.docx

• Тема 1.1 Основные понятия теории множеств.docx

• ЧМ Контрольная работа 1.docx