Индексно-последовательные файлы

Билет №6

Часть 1.

1. Какое предложение объединяет записи с одинаковыми зна­чениями в указанном списке полей в одну запись?
1. НАVING
2. GROUP BY
3. WHERE
2. Какие типы индекса существуют?
1. Кластерный индекс
2. Уникальный индекс
3. Повторяющийся индекс
4. Индекс первичного ключа
5. Полнотекстовый индекс
3. Какие программные средства относят к категории CASE- средств?
1. Все программные средства автоматизирующее один или несколько процессов жизненного цикла ПО и обладающее определенными характерными особенностями
2. Только те, которые полностью автоматизируют жизненный цикл ПО и обладают определенными характерными особенностями
3. Только те, которые автоматизируют лишь некоторые процессы жизненного цикла ПО и обладают определенными характерными особенностями
4. Сколько частей входит в состав индексного файла?
1. Одна
2. Две
3. Три
5. Какие файлы относятся к индексным файлам?
1. Файлы с плотным индексом.
2. Файлы с неплотным индексом.
3. В-деревья.
4. Прямого доступа.

6. Для чего предназначены запросы:

a. для хранения данных базы;

1. для отбора и обработки данных базы;
2. для ввода данных базы и их просмотра;
3. для автоматического выполнения группы команд;
4. для выполнения сложных программных действий;
5. для вывода обработанных данных базы на принтер?

Какие бывают ключи?

A. Простые

B. Составные

C. Сложные

D. справочные

1. В СУБД Access основное свойство Значение по умолчанию (Default Value) определяет:
1. как должно отображаться содержимое поля;
2. текст, который будет отображаться рядом с полем в форме или в отчете;
3. определяет значение, которое вводится в поле автоматически при добавлении новых записей (значение, которое наиболее часто встречается в данном поле);
4. область или диапазон значений данных, допустимых в поле;
5. текст сообщения, которое появляется в строке состояния при попытке ввести в поле недопустимое значение.
2. Укажите тип межтабличной связи - одна запись в таблице А может быть связана со многими записями таблицы Б.
1. один-к-одному;
2. один-ко-многим;
3. многие-к-одному;
4. многие-ко-многим;
5. нет верного ответа.
3. Поля реляционной базы данных:
1. именуются пользователем произвольно с определенными ограничениями;
2. автоматически нумеруются;
3. именуются по правилам, специфичным для каждой конкретной СУБД;
4. нумеруются по правилам, специфичным для каждой конкретной СУБД;
5. нумеруются пользователем произвольно с определенными ограничениями.
   
   

Часть 2.

1. Постреляционные модели данных: объектно-ориентированная.

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

 

Стандартизированная объектно-ориентированная модель описана в рекомендациях стандарта ODMG -93 (Object Database Management Group – группа управления объектно-ориентированными базами данных).

 

Рассмотрим упрощенную модель объектно-ориентированной БД. Структура объектно-ориентированной БД графически представима в виде дерева, узлами которого являются объекты. Свойства объектов описываются некоторым стандартным типом или типом, конструируемым пользователем (определяется как class). Значение свойства типа class есть объект, являющийся экземпляром соответствующего класса. Каждый объект-экземпляр класса считается потомком объекта, в котором он определен как свойство. Объект-экземпляр класса принадлежит своему классу и имеет одного родителя. Родовые отношения в БД образуют связн ую ие рархию объектов. Пример логической структуры объектно-ориентированной БД библиотечного дела приведен на рис. 2.9. Здесь объект типа Библиотека является родительским для объектов-экземпляров классов Абонент, Каталог и Выдача. Различные объекты типа Книг а могут иметь одного или разных родителей. Объекты типа Книга, имеющие одного и того же родителя, должны различаться, по крайней мере, инвентарным номером (уникален для каждого экземпляра книги), но имеют одинаковые значения свойств isb n, удк, названи е и автор.

 

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

 

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

 

Инкапсуляция ограничивает область видимости имени свойства пределами того объекта, в котором оно определено. Так, если в объект типа Каталог добавить свойство, задающее телефон автора книги и имеющее название телефон, то мы получим одноименные свойства у объектов Абонент и Каталог. Смысл такого свойства будет определяться тем объектом, в который оно инкапсулировано.

 

Наследование, наоборот, распространяет область видимости свойства на всех потомков объекта. Так, всем объектам типа Книга, являющимся потомками объекта типа Каталог, можно приписать свойства объекта-родителя: isbn, удк, название и автор. Если необходимо расширить действие механизма наследования на объекты, не являющиеся непосредственными родственниками (например, между двумя потомками одного родителя), то в их общем предке определяется абстрактное свойство типа abs. Так, определение абстрактных свойств билет и номер в объекте Библиотека приводит к наследованию этих свой ств вс еми дочерними объектами Абонент, Книга и Выдач а. Не случайно, поэтому значения свойства билет классов Абонент и Выдача, показанных на рис. 2.9, являются одинаковыми – 00015.

 

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

 

Поиск в объектно-ориентированной БД состоит в выяснении сходства между объектом, задаваемым пользователем, и объектами, хранящимися в БД.

 

Рис. 2.9. Логическая структура БД библиотечного дела

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

 

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

 

К объектно-ориентированным СУБД относятся POET, Jasmine, Versant, O 2, ODB - Jupiter, Iris, Orion, Postgres.

1. Файлы с плотным индексом

Файлы с плотным индексом, или индексно-прямые файлы

 

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

 

Значение ключа

Номер записи

 

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

 

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

 

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

 

Тn = log2N,

 

где N — число элементов.

 

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

 

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

 

1. Создать базу данных по описанию предметной области

 

Билет №7

Часть 1.

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

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

1. Что называется ключами поиска в СУБД?
1. диапазон записей файла БД, в котором осуществляется поиск;
2. логические выражения, определяющие условия поиска;
3. поля, по значению которых осуществляется поиск;
4. номера записей, удовлетворяющих условиям поиска;
5. номер первой по порядку записи, удовлетворяющей условиям поиска.
2. Предположим, что некоторая база данных описывается следующим перечнем записей:
   1 Иванов, 1986, 2400;
   2 Сидоров, 1987, 5300;
   3 Петров, 1986, 3600;
   4 Козлов, 1982, 1200;
   Какие из записей поменяются местами при сортировке по возрастанию этой БД, если она будет осуществляться по первому полю:
1. 1 и 4;
2. 1 и 3;
3. 2 и 4;
4. 2 и 3;
5. 1 и 2.
3. Операция объединения в реляционной алгебре:
1. Позволяет получить множество кортежей, принадлежащих первому отношению.
2. Позволяет получить множество кортежей, принадлежащих либо первому, либо второму, либо обоим отношениям.
3. Позволяет получить множество кортежей, не принадлежащих либо первому, либо второму, либо обоим отношениям.
4. Кортежем в реляционной модели данных называется:
1. Поле данного отношения.
2. Строки отношения.
3. Атрибуты отношения.
5. Иерархическая модель поддерживает следующие виды связей (выберите все правильные ответы):
1. Один к одному.
2. Один ко многим.
3. Многие ко многим.
4. Бесконечность к одному.
5. Бесконечность к бесконечности.
6. Система управления базами данных (СУБД) —это:
1. программная система, поддерживающая наполнение и манипулирование данными в файлах баз данных;
2. набор программ, обеспечивающий работу всех аппаратных устройств компьютера и доступ пользователя к ним;
3. прикладная программа для обработки текстов и различных документов;
4. оболочка операционной системы, позволяющая более комфортно работать с файлами.
7. Информационная система - это?
1. система, в которой хранится информация о состоянии сети INTERNET
2. комплекс аппаратно-программных средств, предназначенный для хранения и поиска информации;
3. совокупность базы данных и всего комплекса аппаратно-программных средств для ее хранения, изменения и поиска информации, для взаимодействия с пользователем;
4. система, которая предоставляет пользователю требуемую им информацию.
8. Основными показателями качества информации являются:
1. Оперативность, достоверность, объективность.
2. Доступность для любых пользователей.
3. Объем, доступность.
9. Данные – это:
1. Обработанная информация;
2. Исходные данные для получения информации;
3. Набор сведений о чем-то, ком-то.

Часть 2.

1. Постреляционные модели данных. Объектно-ориентированная модель данных.(см. 6 билет)
2. Индексно-последовательные файлы.

Индексно-последовательные файлы

 

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

первичная область хранения;

отдельный индекс или несколько индексов;

область переполнения.

 

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

1. Создать базу данных по описанию предметной области

«Бюро занятости»

1. Сведения: ФИО безработного, профессия, образование, возраст, пол, стаж, о семейном положении безработного (ФИО родственника, вид родства (заполняется из справочника родственных связей), дата рождения).

2. Создать таблицу с помощью запроса: вывести фамилии всех женщин со стажем более 10 лет.

3. Создать следующие запросы:

a) вывести фамилии всех учителей со стажем более 2 лет;

b) вывести профессии безработных с высшим образованием.