- •Предисловие
- •Тема 13 посвящена актуальной в настоящее время проблеме компьютерных вирусов, также рассмотрены некоторые свойства компьютерных вирусов, их классификация, программы обнаружения и защиты от них.
- •Тема 1. Обработка данных средствами электронных таблиц Область применения
- •Основные понятия электронных таблиц
- •Общая характеристика интерфейса ms Excel
- •Технология ввода данных в ms Excel
- •Формулы, функции, мастер функций
- •Контрольные вопросы
- •Тема 2. Введение в технологию баз данных Базы данных и системы управления базами данных
- •Основные понятия теории баз данных
- •Модели данных
- •Средства ускорения доступа к данным
- •Язык запросов
- •Программные системы управления базами данных
- •Структура простейшей базы данных
- •Объекты базы данных
- •Режимы работы с базами данных
- •Разработка схемы данных
- •Контрольные вопросы
- •Тема 3. Этапы создания программ
- •Контрольные вопросы
- •Тема 4. Системы и языки программирования Системы программирования
- •Классификация языков программирования
- •Контрольные вопросы
- •Тема 5. Методологии программирования
- •Структурное программирование
- •Нисходящее проектирование
- •Концепция модульного программирования
- •Объектно-ориентированное программирование (ооп)
- •Декларативное программирование
- •Параллельное программирование
- •Case-системы
- •Индустрия искусственного интеллекта
- •Данные и знания
- •Модели представления знаний
- •Экспертные системы
- •Контрольные вопросы
- •Тема 6. Паскаль – структурный язык программирования высокого уровня Структура программы
- •Константы и переменные
- •Основные типы данных
- •Выражения, операнды, операции
- •Совместимость и преобразование типов
- •Основные операторы языка
- •Массивы
- •Процедуры и функции
- •Контрольные вопросы
- •Тема 7. Основные принципы построения компьютерных сетей
- •Основные показатели качества ивс
- •Виды информационно-вычислительных сетей
- •Контрольные вопросы
- •Тема 8. Способы связи компьютеров
- •Контрольные вопросы
- •Тема 9. Модель взаимодействия открытых систем osi
- •Физический уровень
- •Канальный уровень
- •Сетевой уровень
- •Транспортный уровень
- •Сеансовый уровень
- •Представительский уровень
- •Прикладной уровень
- •Контрольные вопросы
- •Тема 10. Техническое и программное обеспечение ивс Техническое обеспечение информационно-вычислительных сетей
- •Серверы и рабочие станции
- •Маршрутизаторы и коммутирующие устройства
- •Модемы и сетевые карты
- •Аналоговые модемы
- •Модемы для цифровых каналов связи
- •Сетевые карты
- •Устройства межсетевого интерфейса
- •Программное обеспечение информационно-вычислительных сетей
- •Контрольные вопросы
- •Тема 11. Локальные вычислительные сети
- •Виды локальных сетей
- •Базовые технологии локальных сетей
- •Построение локальных сетей Структуризация локальных сетей средствами канального уровня
- •Построение локальных сетей средствами сетевого уровня
- •Системное программное обеспечение вычислительных сетей
- •Контрольные вопросы
- •Тема 12. Глобальная сеть Интернет Основные понятия
- •Информационные ресурсы (службы) Интернет
- •Програмное обеспечение работы в Интернете
- •Адресация и протоколы в Интернете
- •Контрольные вопросы
- •Тема 13. Вирусы и антивирусное программное обеспечение Свойства компьютерных вирусов
- •Классификация вирусов
- •Программы обнаружения и защиты от вирусов
- •Контрольные вопросы
- •Библиографический список
Средства ускорения доступа к данным
Современным СУБД приходится оперировать огромными массивами информации, объемы которых достигают порой десятков терабайт. Выполняя запросы тысяч пользователей, они должны обеспечить небольшое, не более нескольких секунд, время отклика. СУБД не сможет эффективно работать в таких условиях, не используя методов ускорения выборки данных. Цель этих методов – избежать полного перебора строк таблиц БД при выполнении реляционных операций, например, при соединении отношений или поиске строк, удовлетворяющих условию.
В современных СУБД используются два основных метода ускорения доступа к данным: индексирование и хеширование. Эти методы обеспечивают лучшее по сравнению с остальными время поиска и модификации таблиц БД.
Метод индексирования основан на использовании индексов. Индекс отношения очень похож на предметный указатель книги. В таком указателе приведен список упорядоченных по алфавиту терминов, которые встречаются в книге. Каждому термину сопоставлена страница или страницы, где он встречается. Обычно предметный указатель занимает не более нескольких страниц. Если нам требуется найти место в книге, где термин раскрывается, мы находим его в предметном указателе, это легко сделать – указатель невелик, кроме того, все термины там упорядочены по алфавиту. Затем мы читаем номер страницы, соответствующий термину, раскрываем книгу на ней и находим нужный нам абзац. Если бы предметный указатель отсутствовал, нам пришлось бы пролистывать все страницы, чтобы найти интересующее нас место, и мы бы потратили значительно больше времени.
Индекс базы данных – не листы бумаги, это – специальная структура данных, создаваемая автоматически или по запросу пользователя. В целом работа с ним выглядит так же, как и с предметным указателем. Разница лишь в том, что СУБД все делает автоматически, пользователь может даже не знать, что она использует индекс. В книге приводится предметный указатель слов, в БД для формирования индекса может быть использован любой атрибут отношения, в том числе и составной. В индексе значения атрибута хранятся упорядоченно (по возрастанию или убыванию), каждому значению соответствует указатель на строку отношения, которое его содержит (аналог номера страницы в предметном указателе). Индекс занимает значительно меньший, чем таблица, объем, поэтому даже полный перебор значений в нем потребует меньше времени, чем считывание и поиск информации в отношении. Кроме того, значения в индексе хранятся упорядоченно, что позволяет резко ускорить поиск нужной строки. Индексы позволяют выбирать строки отношений, значения индексируемого атрибута которых принадлежит некоторому заданному интервалу.
Для одного отношения может быть создано несколько индексов. Если разные отношения содержат одинаковые атрибуты, то для них может быть сформирован мультииндекс. В нем каждому значению общего атрибута соответствует несколько ссылок, каждая из которых указывает на строку с таким значением в том или ином отношении. Мультииндексы применяются для оптимизации выполнения операции соединения отношений.
Еще один интересный подход, применяемый для повышения эффективности доступа к данным, – хеширование (hashing). Для метода хеширования, к сожалению, нет житейского аналога, поэтому объяснить его «на пальцах» вряд ли получится. Основная идея хеширования – организация ассоциативной памяти для хранения строк таблицы с определением места строки в таблице по значениям одного или нескольких ее ключевых атрибутов. Место строки вычисляется хэш-функцией, аргументы которой – значения атрибутов, а результат – целое число в диапазоне номеров строк таблицы. Идеальная хэш-функция должна давать разные значения номеров строк для разных ключевых атрибутов. Однако построить такую хэш-функцию – дело трудоемкое и не всегда возможное.
На практике используются, как правило, простые хэш-функции. Для целочисленных атрибутов в качестве хэш-функции может быть использован, например, остаток от деления на простое число:
f(k) = k mod p,
где f – хэш-функция, k – целочисленный атрибут, а р – простое число.
Если ключевой атрибут – строка символов, то для вычисления хэш-функции выбирается наиболее подходящий в конкретной ситуации метод преобразования строки в число, например, вычисление контрольной суммы.
Доступ к данным при хешировании производится так. В начале работы с БД таблица состоит из пустых строк. Когда строка с данными заносится в таблицу, вычисляется значение хэш-функции для ее атрибутов, и результат трактуется как номер строки отношения, в которую она должна быть записана. Если эта строка уже занята, то по некоторому алгоритму производится проверка следующих строк таблицы до тех пор, пока не будет обнаружено свободное место (при этом, как правило, считается, что таблица имеет кольцевую структуру). В это место и помещается записываемая строка. Для поиска данных используется аналогичный алгоритм. Сначала вычисляется значение хэш-функции для требуемого значения ключевого атрибута и проверяется строка таблицы, номер которой вычислен хэш-функцией. Если значение атрибута, по которому происходит доступ, соответствует значению ключа строки, то поиск заканчивается. В противном случае проверяются следующие строки таблицы до обнаружения кортежа с нужным значением или пустой строки. Пустая строка свидетельствует об отсутствии кортежа с нужным значением ключа в таблице – процедура занесения данных обязательно бы использовала ее, если бы требуемый кортеж существовал.
Если таблица заполнена не более чем на 60 %, то для размещения в ней новой строки необходимо проверить в среднем не более двух ячеек. Иногда для устранения конфликтов (коллизий), возникающих, если хэш-функция выдает номер занятой строки, используют не линейный просмотр, а более сложные методы. Скорость обращения к данным при этом возрастает.
Хеширование может использоваться для поиска строк по точному совпадению значения атрибута кортежа с нужным значением ключа.