Как сделать нормализацию базы данных access

Добавил пользователь Владимир З.
Обновлено: 04.10.2024

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

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

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

Цели нормализации за пределами 1NF (первая нормальная форма) были сформулированы Коддом следующим образом:

1. Освободить коллекцию отношений от нежелательных зависимостей вставки, обновления и удаления.
2. Уменьшить необходимость реструктуризации сбора отношений, так как вводятся новые типы данных, и таким образом увеличить срок службы прикладных программ.
3. Сделать реляционную модель более информативной для пользователей.
4. Сделать набор отношений нейтральным по отношению к статистике запросов, где эти статистические данные могут изменяться с течением времени.

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

Аномалия обновления. Одна и та же информация может быть выражена в нескольких строках; поэтому обновления отношения могут привести к логическим несоответствиям. Например, каждая запись в отношении "Employees' Skills" может содержать идентификатор сотрудника, адрес сотрудника и навык; таким образом, изменение адреса для конкретного сотрудника может потребоваться применить к нескольким записям (по одной для каждого навыка). Если обновление выполнено только частично - адрес сотрудника обновляется в некоторых записях, но не в других - тогда отношение остается в несогласованном состоянии. В частности, отношение дает противоречивые ответы на вопрос, каков адрес этого конкретного сотрудника. Это явление известно как аномалия обновления.

Аномалия обновления. Employee 519 показан как имеющий разные адреса в разных записях.

Аномалия вставки. Существуют обстоятельства, при которых определенные факты не могут быть записаны вообще. Например, каждая запись в отношении "Faculty and Their Courses" может содержать идентификатор факультета, название факультета, дату приема на работу и код курса. Поэтому мы можем записать данные любого преподавателя, который преподает хотя бы один курс, но мы не можем записать вновь нанятого преподавателя, которому еще не было назначено преподавать какие-либо курсы, кроме как путем установки кода курса на ноль. Это явление известно как аномалия вставки.

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

Аномалия удаления. При определенных обстоятельствах удаление данных, представляющих определенные факты, требует удаления данных, представляющих совершенно разные факты. Отношение "Faculty and Their Courses", описанное в предыдущем примере, страдает этим типом аномалии, поскольку если преподаватель временно прекращает назначаться на какие-либо курсы, мы должны эффективно удалить последнюю из записей, на которых этот преподаватель появляется также удаляя преподавателя, если мы не установили код курса на ноль. Это явление известно как аномалия удаления.

Аномалия удаления. Вся информация о Dr. Giddens теряется, если он или она временно перестает назначаться на какие-либо курсы.

Минимизировать редизайн при расширении структуры базы данных

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

Нормализованные отношения и отношения между одним нормализованным отношением отражают концепции реального мира и их взаимосвязи.

Пример

Запрос и манипулирование данными в ненастроенной структуре данных, такой как следующее представление транзакций по кредитным картам клиентов, не относящихся к 1NF, включает в себя большую сложность, чем это действительно необходимо:

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

• Распаковка групп транзакций одного или нескольких клиентов, позволяющая исследовать отдельные транзакции в группе
• Вывод результата запроса на основе результатов первого этапа

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

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

В измененной структуре ключом является в первом отношении, во втором отношении.

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

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

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

Плюсы

Нормализация не является обязательной, но приносит следующие преимущества: — упрощается процесс выборки. Речь идет об упрощении работы по составлению запросов, то есть пользователь сможет получать нужную информацию относительно простыми запросами; — обеспечивается целостность данных. Можно говорить о минимизации искажения информации и снижении вероятности потери данных; — улучшается масштабируемость. При соблюдении правил нормализации формируются благоприятные предпосылки к росту БД; — отсутствует избыточность (data redundancy). Избыточность — известная проблема непродуктивного использования свободного места на жестком диске, затрудняющая обслуживание БД. В отдельных случаях эту проблему усугубляет и то, что в случае необходимости изменения записей однотипных данных, хранимых в нескольких местах (таблицах), пользователю придется вносить требуемые изменения везде, что весьма трудоемкое занятие. Гораздо проще сделать так, чтобы, к примеру, данные о городах хранились только в таблице Cities и нигде больше. Если подытожить вышесказанное, избыточность предполагает дублирование данных, а это не только усложняет работу с БД, но и увеличивает ее размер; — отсутствие несогласованных зависимостей. Несогласованные зависимости затрудняют доступ к данным, ведь путь к такой информации может быть неправилен и нелогичен. В той же таблице Cities логично искать города, количество жителей и т. п., но не адреса и имена жителей — для этой информации уже нужна другая таблица — Citizens.

Как выполнить нормализацию?

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

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

Таких форм (уровней) — семь, однако на практике для большей части приложений вполне достаточно нормализовать БД до третьей нормальной формы (строго говоря, БД и будет считаться нормализованной, когда к ней применяется 3НФ и выше).

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

Правила нормализации на примерах

Первая нормальная форма (1НФ)

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

Для примера возьмем таблицу с автомобилями:

Обратите внимание на нарушение нормализации в моделях BMW — в одной ячейке находится перечень из трех элементов: M5, X5M, M1, то есть можно говорить об отсутствии атомарности. После преобразования в 1НФ таблица меняет вид:

Вторая нормальная форма (2НФ)

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

Рассмотрим очередную таблицу:

Третья нормальная форма (3НФ)

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

В результате можно говорить о наличии в связях следующих функциональных зависимостей:

Разделив исходное отношение, можно получить 2 отношения, и они уже будут находиться в 3НФ:

P. S. Очень надеемся, что теперь у вас сложилось представление о том, что такое нормализация базы данных. Если же вы хотите освоить работу с БД на профессиональном уровне, добро пожаловать на курсы OTUS!

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

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

1. Удаляется запись в родительской таблице , но не удаляются соответствующие связанные записи в дочерней таблице .
2. Изменяется запись в родительской таблице , но не изменяются соответствующие ключи в дочерней таблице .
3. Изменяется ключ в дочерней таблице , но не изменяется значение связанного поля родительской таблицы.

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

Нормализация базы данных

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

Процесс нормализации данных заключается в устранении избыточности данных в таблицах.

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

Первая нормальная форма ( 1НФ ) требует, чтобы каждое поле таблицы БД было неделимым (атомарным) и не содержало повторяющихся групп.

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

Под понятием повторяющиеся группы подразумевают поля, содержащие одинаковые по смыслу значения. Взгляните на рисунок:

Верно, такую таблицу можно сделать, однако она нарушает правило первой нормальной формы. Поля "Студент 1", "Студент 2" и "Студент 3" содержат одинаковые по смыслу объекты, их требуется поместить в одно поле "Студент", как в рисунке 1.4. Ведь в группе не бывает по три студента, правда? Представляете, как будет выглядеть таблица , содержащая данные на тридцать студентов? Это тридцать одинаковых полей ! В приведенном выше рисунке поля описывают студентов в формате "Фамилия И.О.". Однако если оператор будет вводить эти описания в формате "Фамилия Имя Отчество", то нарушается также правило неделимости. В этом случае каждое такое поле следует разбить на три отдельных поля, так как поиск может вестись не только по фамилии, но и по имени или по отчеству.

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

В чем здесь нарушение? Ключом этой таблицы служат поля "№ студента" - "Секция". Однако данная таблица также содержит отношение "Секция" - " Плата ". Если мы удалим запись студента № 110, то потеряем данные о стоимости секции по скейтборду. А после этого мы не сможем ввести информацию об этой секции, пока в нее не запишется хотя бы один студент. Говорят, что такое отношение подвержено как аномалии удаления , так и аномалии вставки.

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

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

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

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

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

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

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

Студентов ГБПОУ РО "ГСТ" для специальности 09.02.07 Информационные системы и программирование

1. Обеспечение непротиворечивости и целостности данных в базе

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

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

1. Каждая строка таблицы должна отличаться от остальных ее строк значением хотя бы одного столбца.

1. Внешний ключ не может быть указателем на несуществую­щую строку той таблицы, на которую он ссылается. Это ограниче­ние называется ограничением целостности по ссылкам.

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

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

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

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

Информационный объект (или сущность) находится в первой нормальной форме (1НФ), когда все его атрибуты имеют единствен­ное значение. Если в каком-либо атрибуте есть повторяющиеся зна­чения, объект (сущность) не находится в 1НФ, и упущен еще по крайней мере один информационный объект (еще одна сущность).

не находится в 1НФ, так как атрибут Преподаватели подразумевает возможность присутствия нескольких фамилий преподавателей в записи, относящейся к какому-то конкретному предмету, что соот­ветствует участию нескольких преподавателей в ведении одной дис­циплины. Переведем атрибут с повторяющимися значениями в но­вую сущность, назначим ей первичный ключ (Код преподавателя) и свяжем с исходной сущностью ссылкой на первичный ключ послед­ней (Код предмета). В результате получим две сущности, причем во вторую сущность ПРЕПОДАВАТЕЛЬ мы добавляем характеризую­щие ее атрибуты:

ПРЕДМЕТ (Код предмета, Название. Цикл, Объем часов);

ПРЕПОДАВАТЕЛЬ (Код преподавателя, Фамилия И.О., Должность, Оклад, Адрес, Код предмета).

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

ПРЕДМЕТ (Код предмета, Название, Цикл, Объем часов);

ПРЕПОДАВАТЕЛЬ (Код преподавателя, Фамилия И.О., Должность, Оклад, Адрес);

ИЗУЧЕНИЕ (Код предмета, Код преподавателя).

Информационный объект находится во второй нормальной фор­ме (2НФ), если он уже находится в первой нормальной форме, и ка­ждый неидентифицирующий (описательный) атрибут зависит от всего уникального идентификатора информационного объекта. Если некий атрибут не зависит полностью от уникального иденти­фикатора сущности, значит, он внесен ошибочно и должен быть удален. Нормализация в этом случае производится путем нахожде­ния существующего информационного объекта, к которому данный атрибут относится, или созданием нового информационного объек­та, в который атрибут должен быть помещен.

Возвращаясь к предыдущему примеру, замечаем что атрибут Цикл в сущности ПРЕДМЕТ, характеризующий принадлежность предмета к циклу гуманитарных, естественно-научных, общепро­фессиональных или специальных дисциплин, не полностью зависит от уникального идентификатора Код предмета, так как разные пред­меты могут иметь одно и то же значение атрибута Цикл. Перенесем атрибут в новую сущность ЦИКЛ и получим четыре взаимосвязан­ные сущности:

ПРЕДМЕТ (Код предмета, Название, Объем часов. Код цикла);

ЦИКЛ (Код цикла, Название цикла);

ПРЕПОДАВАТЕЛЬ (Код преподавателя, Фамилия И.О., Должность, Оклад, Адрес):

ИЗУЧЕНИЕ (Код предмета, Код преподавателя).

Информационный объект (или сущность) находится в третьей нормальной форме (ЗНФ), если он уже находится во второй нор­мальной форме и ни один описательный атрибут не зависит от ка­ких-либо других описательных атрибутов. Атрибуты, зависящие от других неидентифицирующих атрибутов, нормализуются путем пе­ремещения зависимого атрибута и атрибута, от которого он зависит, в новый информационный объект.

В нашем примере неключевые атрибуты Должность и Оклад на­ходятся в транзитивной зависимости. В чем опасность такой зави­симости? Во-первых, несколько человек могут работать в одной и той же должности. При изменении должностного оклада в этом слу­чае нужно будет менять данные в каждой записи, содержащей эту должность. В рассмотренной ситуации нужно создать новую сущ­ность ДОЛЖНОСТЬ с находящимися в транзитивной зависимости атрибутами — Название должности и Оклад и сделать ссылку от сущности ПРЕПОДАВАТЕЛЬ на сущность ДОЛЖНОСТЬ:

ПРЕДМЕТ (Код предмета, Название, Объем часов, Код цикла);

ЦИКЛ (Код цикла, Название цикла);

ПРЕПОДАВАТЕЛЬ (Код преподавателя, Фамилия И.О., Код должности, Адрес);

ДОЛЖНОСТЬ (Код должности, Название должности, Оклад);

ИЗУЧЕНИЕ (Код предмета, Код преподавателя).

1. Средства ускоренного доступа к данным

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

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

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

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

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

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

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

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

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

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

Хеширование используют для поиска строк по точному совпаде­нию значения ключевого атрибута кортежа с нужным значением ключа.

Читайте также:

  
• Как сделать таблицу в канве
  
• Как сделать каллы из овощей
  
• Как сделать откосы пруда
  
• Как сделать опил квадратной формы
  
• Как сделать кв трудная поездка