Система управления базами данных

 

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВОСТОЧНО-СИБИРСКИЙ ИНСТИТУТ ЭКОНОМИКИ И ПРАВА


 

Факультет инновационных технологий обучения

 

 

 

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

 

по дисциплине

СИСТЕМА УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

 

 

 

 

 

 

 

 

Выполнил студент

группы М-Т-12-3

                    Хаврицына Клара Геннадьевна .    

подпись    


 

 

 

 

 

 

 

 

 

 

 

 

Иркутск

2014

 

СОДЕРЖАНИЕ

 

 

 

1. КОНЦЕПЦИЯ БАЗ ДАННЫХ. АРХИТЕКТУРА СУБД

 

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

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

Основные черты концепции БД:

  • появляются стандартизированные данные о фактографических данных – метаданные, управляемые СУБД; метаданные описывают информационные параметры и взаимосвязи фактографических данных о ПО;

СУБД совместно с метаданными представляет собой стандартизированное инструментальное средство для моделирования ПО различной природы;

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

Принято считать, что использование концепции баз данных позволяет:

  1. повысить надежность, целостность и сохранность данных;
  2. сохранить затраты интеллектуального труда;
  3. обеспечить простоту и легкость использования данных;
  4. обеспечить независимость прикладных программ от данных (изменений их описаний и способов хранения);
  5. обеспечить достоверность данных;
  6. обеспечить требуемую скорость доступа к данным;
  7. стандартизовать данные в пределах одной предметной области;
  8. автоматизировать реорганизацию данных;
  9. обеспечить защиту от искажения и уничтожения данных;
  10. сократить дублирование информации за счет структурирования данных;
  11. обеспечить обработку незапланированных запросов к хранимой информации;
  12. создать предпосылки для создания распределенной обработки дaнныx.

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

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

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

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

Понятие СУБД:

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

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

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

 

2. ОСНОВНЫЕ ПОНЯТИЯ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ. ПОНЯТИЕ КОРТЕЖА ДАННЫХ И ОТНОШЕНИЯ

 

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

 Для начала покажем смысл  этих понятий на примере отношения  СОТРУДНИКИ, содержащего информацию о сотрудниках некоторой организации:

Тип данных:

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

Домен:

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

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

Следует отметить также семантическую нагрузку понятия домена: данные считаются сравнимыми только в том случае, когда они относятся к одному домену. В нашем примере значения доменов "Номера пропусков" и "Номера групп" относятся к типу целых чисел, но не являются сравнимыми. Заметим, что в большинстве реляционных СУБД понятие домена не используется, хотя в Oracle V.7 оно уже поддерживается.

Схема отношения, схема базы данных:

Схема отношения - это именованное множество пар {имя атрибута, имя домена (или типа, если понятие домена не поддерживается)}. Степень или "арность" схемы отношения - мощность этого множества. Степень отношения СОТРУДНИКИ равна четырем, то есть оно является 4-арным. Если все атрибуты одного отношения определены на разных доменах, осмысленно использовать для именования атрибутов имена соответствующих доменов (не забывая, конечно, о том, что это является всего лишь удобным способом именования и не устраняет различия между понятиями домена и атрибута).

 Схема БД (в структурном смысле) - это набор именованных схем  отношений.

Кортеж, отношение:

Кортеж, соответствующий данной схеме отношения, - это множество пар {имя атрибута, значение}, которое содержит одно вхождение каждого имени атрибута, принадлежащего схеме отношения. "Значение" является допустимым значением домена данного атрибута (или типа данных, если понятие домена не поддерживается). Тем самым, степень или "арность" кортежа, т.е. число элементов в нем, совпадает с "арностью" соответствующей схемы отношения. Попросту говоря, кортеж - это набор именованных значений заданного типа.

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

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

Обычным житейским представлением отношения является таблица, заголовком которой является схема отношения, а строками - кортежи отношения-экземпляра; в этом случае имена атрибутов именуют столбцы этой таблицы. Поэтому иногда говорят "столбец таблицы", имея в виду "атрибут отношения". Когда мы перейдем к рассмотрению практических вопросов организации реляционных баз данных и средств управления, мы будем использовать эту житейскую терминологию. Этой терминологии придерживаются в большинстве коммерческих реляционных СУБД.

Реляционная база данных - это набор отношений, имена которых совпадают с именами схем отношений в схеме БД.

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

3. ЦЕЛОСТНОСТЬ РЕЛЯЦИОНЫХ БАЗ ДАННЫХ

 

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

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

     В РМД существует два вида внутренних ограничений целостности.

1. Целостность по существованию  – потенциальный ключ отношения  не может иметь пустого значения (NULL).

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

 

 

 

 

 

 

 

 

4. НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ РЕЛЯЦИЛННЫХ БАЗ ДАННЫХ. ВТОРАЯ НОРМАЛЬНАЯ ФОРМА (2NF)

 

Рассмотрим следующий пример схемы отношения:

СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Первичный ключ:

СОТР_НОМЕР, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР (r) СОТР_ЗАРП

СОТР_НОМЕР (r) ОТД_НОМЕР

ОТД_НОМЕР (r) СОТР_ЗАРП

СОТР_НОМЕР, ПРО_НОМЕР (r) СОТР_ЗАДАН

Как видно, хотя первичным ключом является составной атрибут СОТР_НОМЕР, ПРО_НОМЕР, атрибуты СОТР_ЗАРП и ОТД_НОМЕР функционально зависят от части первичного ключа, атрибута СОТР_НОМЕР. В результате мы не сможем вставить в отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ кортеж, описывающий сотрудника, который еще не выполняет никакого проекта (первичный ключ не может содержать неопределенное значение). При удалении кортежа мы не только разрушаем связь данного сотрудника с данным проектом, но утрачиваем информацию о том, что он работает в некотором отделе. При переводе сотрудника в другой отдел мы будем вынуждены модифицировать все кортежи, описывающие этого сотрудника, или получим несогласованный результат. Такие неприятные явления называются аномалиями схемы отношения. Они устраняются путем нормализации.

Вторая нормальная форма (в этом определении предполагается, что единственным ключом отношения является первичный ключ).

Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда находится в 1NF, и каждый неключевой атрибут полностью зависит от первичного ключа.

Можно произвести следующую декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ в два отношения СОТРУДНИКИ-ОТДЕЛЫ и СОТРУДНИКИ-ПРОЕКТЫ:

СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, СОТР_ЗАРП, ОТД_НОМЕР)

Первичный ключ: СОТР_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР (r) СОТР_ЗАРП

СОТР_НОМЕР (r) ОТД_НОМЕР

ОТД_НОМЕР (r) СОТР_ЗАРП

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Первичный ключ: СОТР_НОМЕР, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР, ПРО_НОМЕР (r) CОТР_ЗАДАН

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

Если допустить наличие нескольких ключей, то определение 6 примет следующий вид:

Отношение R находится во второй нормальной форме (2NF) в том и только в том случае, когда оно находится в 1NF, и каждый неключевой атрибут полностью зависит от каждого ключа R. Здесь и далее мы не будем приводить примеры для отношений с несколькими ключами. Они слишком громоздки и относятся к ситуациям, редко встречающимся на практике.

 

5. НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ. ТРЕТЬЯ НОРМАЛЬНАЯ ФОРМА. (3NF). НОРМАЛЬЯНАЯ ФОРМА БОЙСА-КОДДА

 

          Рассмотрим еще раз отношение СОТРУДНИКИ-ОТДЕЛЫ, находящееся в 2NF. Заметим, что функциональная зависимость СОТР_НОМЕР (r) СОТР_ЗАРП является транзитивной; она является следствием функциональных зависимостей СОТР_НОМЕР (r) ОТД_НОМЕР и ОТД_НОМЕР (r) СОТР_ЗАРП. Другими словами, заработная плата сотрудника на самом деле является характеристикой не сотрудника, а отдела, в котором он работает (это не очень естественное предположение, но достаточное для примера).

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

         Третья нормальная форма. (Снова определение дается в предположении существования единственного ключа.)

          Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 2NF и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.

           Можно произвести декомпозицию отношения СОТРУДНИКИ-ОТДЕЛЫ в два отношения СОТРУДНИКИ и ОТДЕЛЫ:

СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР)

Первичный ключ: СОТР_НОМЕР

Функциональные зависимости: СОТР_НОМЕР (r) ОТД_НОМЕР

ОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП)

Первичный ключ: ОТД_НОМЕР.

Функциональные зависимости: ОТД_НОМЕР (r) СОТР_ЗАРП.

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

Отношение R находится в третьей нормальной форме (3NF) в том и только в том случае, если находится в 1NF, и каждый неключевой атрибут не является транзитивно зависимым от какого-либо ключа R.

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

Нормальная форма Бойса-Кодда:

Рассмотрим следующий пример схемы отношения:

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, СОТР_ИМЯ, ПРО_НОМЕР, СОТР_ЗАДАН)

Возможные ключи: СОТР_НОМЕР, ПРО_НОМЕР СОТР_ИМЯ, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР (r) CОТР_ИМЯ

СОТР_НОМЕР (r) ПРО_НОМЕР

СОТР_ИМЯ (r) CОТР_НОМЕР

СОТР_ИМЯ (r) ПРО_НОМЕР

СОТР_НОМЕР, ПРО_НОМЕР (r) CОТР_ЗАДАН

СОТР_ИМЯ, ПРО_НОМЕР (r) CОТР_ЗАДАН

           В этом примере предполагается, что личность сотрудника полностью определяется как его номером, так и именем (это снова не очень жизненное предположение, но достаточное для примера).

         В соответствии с определением 7~ отношение СОТРУДНИКИ-ПРОЕКТЫ находится в 3NF. Однако тот факт, что имеются функциональные зависимости атрибутов отношения от атрибута, являющегося частью первичного ключа, приводит к аномалиям. Например, для того, чтобы изменить имя сотрудника с данным номером согласованным образом, нам потребуется модифицировать все кортежи, включающие его номер.

        Детерминант - любой атрибут, от которого полностью функционально зависит некоторый другой атрибут.

      Нормальная форма Бойса-Кодда:

Отношение R находится в нормальной форме Бойса-Кодда (BCNF) в том и только в том случае, если каждый детерминант является возможным ключом.

Очевидно, что это требование не выполнено для отношения СОТРУДНИКИ-ПРОЕКТЫ. Можно произвести его декомпозицию к отношениям СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ:

СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ)

Возможные ключи: СОТР_НОМЕР, СОТР_ИМЯ

Функциональные зависимости:

СОТР_НОМЕР (r) CОТР_ИМЯ

СОТР_ИМЯ (r) СОТР_НОМЕР

СОТРУДНИКИ-ПРОЕКТЫ (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН)

Возможный ключ: СОТР_НОМЕР, ПРО_НОМЕР

Функциональные зависимости:

СОТР_НОМЕР, ПРО_НОМЕР (r) CОТР_ЗАДАН

Возможна альтернативная декомпозиция, если выбрать за основу СОТР_ИМЯ. Получаемые отношения СОТРУДНИКИ и СОТРУДНИКИ-ПРОЕКТЫ находятся в BCNF, и им не свойственны отмеченные аномалии.

 

 

6. ОПРЕДЕЛЕНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ МОДЕЛИ. ВЫДЕЛЕНИЕ СУЩНОСТЕЙ

 

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

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

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

Совокупность реалий (объектов) внешнего мира - объектов, о которых можно задавать вопросы, - образует объектное ядро предметной области, которое имеет онтологический статус. Нельзя получить в ИС ответ на вопрос о том, что ей неизвестно. Термин объект является первичным, неопределяемым понятием. Синонимами термина "объект" являются "реалия, сущность, вещь". Однако термин сущность понимается нами несколько уже, как компонент модели предметной области, т.е. как уже выделенный на концептуальном уровне объект для базы данных. Таким образом, выделяемые в предметной области объекты превращаются аналитиками (а не проектировщиками базы данных) в сущности. Сущность предметной области является результатом абстрагирования реального объекта путем выделения и фиксации набора его свойств. Сущность является результатом абстрагирования реального объекта, т.е. в нашем контексте имеет гносеологический статус. Хотя далее в контексте сущность нередко отождествляется с объектом.

 

 

 

 

 

 

 

 

 

 

 

 

7. ОРГАНИЗАЦИЯ ДОСЬУПА К ДАННЫМ. СРЕДСТВА УСКОРЕННОГО ДОСТУПА К ДАННЫМ

 

Наиболее эффективны методы индексирования и хеширования значений ключей отношения.

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

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

Хеширование (hashing) — использование хэш-функций, которые вычисляют вес строки таблицы по значению ее ключевых атрибутов. Результат вычисления хэш-функции — целое число в диапазоне физических номеров строк таблицы.

Идеальная хэш-функция должна давать разные значения веса для разных ключевых атрибутов. Но это не всегда возможно. На практике обычно используют простые хэш-функции, например f(k)=к mod p, где к — целое число, первичный ключ отношения; р — простое целое число; mod — операция, вычисляющая остаток при целочисленном делении. Если ключевой атрибут — строка символов, то для вычисления f(k) выбирается один из методов преобразования строки в число, например вычисление контрольной суммы.

Для организации доступа к данным при хешировании создается таблица с пустыми строками, которая заполняется следующим образом:

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

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

  • если после вычисления f(k) на месте в таблице, которое соответствует вычисленному значению, оказывается пустая строка, значит, искомой строки просто нет;
  • если значение ключа совпало с искомым, поиск заканчивается;
  • если же значение ключа не совпало с искомым, проверяются следующие строки таблицы до обнаружения строки с нужным ключом (в этом случае искомая строка найдена) или пустой строки (в этом случае искомая строка отсутствует).

Если таблица заполнена не более чем на 60 %, то для размещения новой или поиска существующей строки необходимо проверить в среднем не более двух ячеек. Хеширование используют для поиска строк по точному совпадению значения ключевого атрибута кортежа с нужным значением ключа.

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

  1. Дейт К. Руководство по реляционной СУБД DB2. - М.: Финансы и статистика, 2008. - 320 с.
  2. Кириллов В.В. Основы проектирования реляционных баз данных .Учебное пособие. - СПб.: ИТМО, 2008. - 90 с.
  3. Мейер М. Теория реляционных баз данных. -М.: Мир, 2007. - 608 с.
  4. Ульман Дж. Базы данных на Паскале. -М.: Машиностроение,2010.- 386с.
  5. Агибалов А. В., Горюхина Е.Ю. Автоматизированные системы обработки экономической информации. Учебное пособие - 3-е изд., доп.: Воронеж.: ВГАУ, 2008.
  6. Диго С.М. Базы данных: проектирование и использование. Учебное пособие для вузов. - Москва.: Финансы и статистика, 2005.
  7. Информатика. Базовый курс /Симонович С.В. и др. - СПб: Издательство "Питер", 2006.
  8. Компьютерный практикум. Программирование в среде Турбо-Паскаль и СУБД типа Fox. Методические указания к выполнению курсового проекта. /Сост.: О.Н. Леонова, И.А. Несмеянов; ГАУ, М., 2008.
  9. Лемашко Е. В., Романчуков В.Г. Программирование в системе команд СУБД семейства Fox: учебное пособие/ ГАУ, М., 2008.
  10. http://www.citforum.ru/database/sql_kg/index.shtml « Основы проектирования реляционных баз данных»
  11. Гончаров А. «MicrosoftAccess ХР». – СПб: Питер, 2003
  12. Горев А., Макашарипов С, Ахаян Р. Эффективная работа с СУБД. СПб, «Питер», 2002
  13. Джексон Г. Проектирование реляционнных баз данных для использования с ЭВМ: Перевод с английского. М.: Мир, 1991,
  14. Кирий В.Г. Информатика. Учебное пособие – Иркутск: ИрГТУ, 1998
  15. Ковалевская Е.В., Волосков Н.И., Григоренко Г.П., Желнинский Г.С., Технология реализации на ЭВМ регламентных задач АСУ - М.: 1983
  16. Ломтадзе В.В., Шишкина Л.П. Информатика. Учебное пособие. Иркутск: ИрГТУ, 1999
  17. Подольский В.И., Григоренко Г.П., Щербакова Н.С., Дик В.В. Обработка учетной информации на ПЭВМ - М.: МЭСИ, 1993