Многосписочные структуры на физическом уровне базы данных

Метод факторизации по значению поля. Комбинация простых представлений. Простой пример многосписочной организации (использование цепочек указателей). Алгоритмы хеширования: преобразование основания системы счисления. Факторы эффективности хеширования.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 11.12.2020
Размер файла 668,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра программного обеспечения информационных технологий

Факультет ЗВиДО

Специальность ПОИТ

Контрольная работа №1

по дисциплине «Базы данных.ч.1»

Вариант № 6

Выполнил студент: Цыбулько А.А.

группа 491051

Вопрос 1. Многосписочные структуры на физическом уровне базы данных

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

Номер зачетной книжки

ФИО

Средняя успеваемость

Название факультета

1172001

Иванов Иван Васильевич

7,1

Афтоматизации

1172008

Петров Сергей Петрович

6,9

Автоматизации

1172032

Соколов Андрей Иванович

6,9

Физических процессов

1172077

Балыгин Пётр Антонович

7,1

Физических процессов

1172079

Златникова Эльвира Вацлавовна

6,9

Физических процессов

1172147

Васильев Иван Андреевич

8,3

Химического моделирования

Рисунок 1 - Простейший пример сохраняемой таблицы

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

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

Рисунок 2 - Метод факторизации по значению поля

В данном случае у нас есть два хранимых файла: файл студентов и файл факультетов с указателями из первого во второй. Эти указатели представляют собой адреса хранимых записей. При использовании данного метода указатель занимает меньше памяти, чем название факультета, что позволит сэкономить некоторый объём памяти. Однако, данный метод не лишён недостатков.

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

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

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

Рисунок 3 - Метод индексирования по полям

Следует заметить, что файл «Факультеты» служит индексом для файла «Студенты». Он управляется СУБД, но не методом доступа. Фактически это т.н. «плотный вторичный индекс» («плотный» означает, что индекс содержит отдельную запись для каждого экземпляра хранимой записи индексируемого файла, «вторичный» означает, что индексируемое поле не является первичным ключом). В этом случае (поскольку индекс - плотный) индексируемый файл не должен содержать индексируемое поле (в этом примере файл «Студенты» не включает поле Факультеты).

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

Рисунок 4 - Комбинация простых представлений

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

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

Рисунок 5 - Простой пример многосписочной организации (использование цепочек указателей)

Здесь каждый экземпляр хранимой записи файла студентов или файла факультетов содержит только один указатель. Каждая запись файла факультетов указывает на запись первого студента на этом факультете. Эта запись студента указывает на запись второго студента того же самого факультета, которая в свою очередь указывает на запись третьего и т.д. до записи последнего, которая содержит указатель на запись факультета. Таким образом, для каждой записи факультета у нас есть цепочка записей всех студентов на этом факультете. Достоинство этого варианта представления состоит в простоте внесения изменений. Недостатком является то, что для данного факультета единственным способом доступа к n-му студенту является последовательное прохождение по цепочке от первого ко второму и т.д. до (n-1)-го студента. Если каждая операция доступа включает операцию поиска, то время доступа к n-му студенту может стать достаточно большим.

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

Рисунок 6 - Пример улучшенной многосписочной организации (использование двунаправленных цепочек указателей)

Вопрос 2. Алгоритмы хеширования: преобразование основания системы счисления

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

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

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

3. Полученные числа умножаются на константу, что позволяет разместить их строго в диапазоне значений адресов основной области. Например, пусть в результате выполнения этапа 2 мы получаем трёхзначные числа, а в основной области имеется 400 пакетов. Тогда трёхзначные числа следует умножать на 0.4, что позволит распределить получаемые адреса в интервале от 000 до 399. Этот относительный номер участка преобразуется в машинный адрес участка.

Рассмотрим такой алгоритм хеширования, как преобразование основания системы счисления.

У нас есть ключ, равный 3417. Переводим в двенадцатиричную систему счисления:

Младшие разряды: 79

Выравнивание адреса: 79*0.4 = 31

Вопрос 3.Факторы эффективности хеширования

хеширование поле метод алгоритм

На эффективность метода хеширования влияют следующие факторы.

Размер участка записей.

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

Предположим, что в рулетке находится 100 шариков, которые будут направлены колесом рулетки в гнёзда. (Шарики в данном случае эквивалентны записям, а гнёзда - первичным участкам записи.)Допустим также, что можно изменять объём гнезда (т.е. можно изменять число шариков, которое помещается в каждое гнездо).

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

Рисунок 7

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

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

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

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

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

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

Организация работы с областями переполнения.

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

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

Второй подход заключается в хранении записей переполнения в пределах основной области.

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

Цепочки участков переполнения.

Для связи основой области памяти с областью переполнения используются цепочки адресов. Т.е. пакет в основной области хранит адреспакета (записи) в области переполнения.

Метод распределенной области переполнения.

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

Если каждый 10-й пакет -- пакет переполнения, то адрес текущего N-го пакета записей будет определяться по формуле:

Адрес пакета = B0 + B(N+[N/9]) , где

B0 -- адрес первого байта;

B -- размер пакета в байтах;

N -- номер пакета, полученный на выходе алгоритма хеширования.

Метод открытой адресации (Петерсона).

Происходит рассеивание записей переполнения в основной области.

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

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

Справочник свободных пакетов.

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

Размещено на Allbest.ru

...

Подобные документы

  • Использование хеширования для поиска данных. Хеширование и хеш-таблицы. Способы разрешения конфликтов. Использование средств языка программирования в работе с хеш-таблицами. Описание разработанного приложения. Структура программы. Инструкция пользователя.

    курсовая работа [1,1 M], добавлен 19.08.2016

  • Хеширование как процесс получения уникального (чаще цифрового) идентификатора для объекта, его применение для быстрого поиска в структурах данных и криптографии, проверки на наличия ошибок. Примеры хеш-функций. Разрешение коллизий, метод цепочек.

    реферат [214,8 K], добавлен 20.10.2013

  • Индексирование в базах данных. Создание индекса, его типы, виды и структура. Индексы для последовательных файлов. Неупорядоченные и упорядоченные файлы. Типы хеширования, древовидные структуры для многомерных данных. Деревья квадрантов и их вершины.

    реферат [2,6 M], добавлен 19.06.2015

  • Перевод исходного текста и первого подключа в двоичную последовательность. Логическое сложение с исключением. Открытый и закрытый ключи в алгоритме шифрования RSA. Шифрование и расшифрование. Электронная цифровая подпись. Применение функции хеширования.

    контрольная работа [21,9 K], добавлен 28.03.2012

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

    реферат [22,7 K], добавлен 21.06.2016

  • Структура простейшей базы данных и свойства полей. Характеристика типов данных. Описание процесса создания базы данных, таблиц и связей между ними, простых и составных форм, запросов в Microsoft Access. Пример составления подчинённых отчетов и макросов.

    курсовая работа [2,9 M], добавлен 14.11.2016

  • Разработка информационной системы для регистрации постояльцев в гостинице с использованием структур данных и алгоритмов. Методы хеширования и сортировки данных. Обходы бинарных деревьев. Линейный однонаправленный список. Описание и тестирование программы.

    курсовая работа [2,3 M], добавлен 09.03.2014

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

    контрольная работа [41,2 K], добавлен 21.08.2010

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

    курсовая работа [2,9 M], добавлен 21.04.2015

  • Выбор средств разработки базы данных для информационного функционирования аэропорта. Выделение и нормализация сущностей. Логическая схема и физическая структура базы данных. Спецификация и тестирование функций, процедур, триггеров, представлений.

    курсовая работа [1,5 M], добавлен 07.06.2013

  • Методы хеширования данных и реализация хеш-таблиц. Разработка на языке программирования высокого уровня программы с функциями создания хеш-таблицы, добавления в нее элементов, их просмотра, поиска и удаления. Экспериментальный анализ хеш-функции.

    лабораторная работа [231,9 K], добавлен 18.06.2011

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

    курсовая работа [2,4 M], добавлен 16.03.2011

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

    курсовая работа [420,4 K], добавлен 22.06.2011

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

    презентация [114,0 K], добавлен 25.10.2013

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

    курсовая работа [307,6 K], добавлен 16.06.2012

  • Объектно-ориентированное программирование как новый подход к созданию приложений. Разработка Windows-приложения для поиска информации в хэш-таблице. Анализ использования хеширования для поиска данных и линейного зондирования для разрешения конфликтов.

    курсовая работа [915,5 K], добавлен 06.03.2016

  • Условия применения и технические требования для работы программно-аппаратной платформы. Система распознавания лиц VOCORD Face Control. Система распознавания текста ABBYY FineReader. Алгоритмы и методы, применяемые в программе. Алгоритм хеширования MD5.

    дипломная работа [1,8 M], добавлен 19.01.2017

  • Проектирование базы данных для автоматизированной системы "Склад". Разработка концептуальной модели (ER-диаграмма). Преобразование в реляционную модель и ее нормализация. Разработка запросов к базе данных на языке SQL. Скрипт для создания базы данных.

    курсовая работа [161,8 K], добавлен 07.10.2013

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

    лабораторная работа [142,3 K], добавлен 06.07.2009

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

    реферат [2,5 M], добавлен 25.12.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.