Лекция 5 C труктурирование данных и их физическая организация

информационных отношений. Простейшие структуры данных.
Модели данных, особенности их организации

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

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

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

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

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

отношению между словами, понятиями или предметами («класс – подкласс» или

«целое – часть»).; причинно-следственное (пространственное, временное) – любое устойчивое отношение между предметами, которое целесообразно учитывать при информационном поиске.
Структурирование данных задают прежде всего с помощью различного рода отношений порядка (упорядоченности). Простейший вид упорядоченности задают обычной нумерацией данных с помощью последовательности чисел.
Например, Xi, где i пробегает целые числа от m до n, идентифицирует упорядоченный набор данных, называемый обычно одномерным массивом.

образом массивах возникают отношения следования. Так, следующим по индексу j

для элемента Xij будет элемент Xi,j+1, а предыдущим – Xi,j-1. Если индекс j пробегает значения от m до n, то для m не существует предыдущего, а для n – следующего значения индекса.
Если значения индексов задаются константами, то это прямоугольный массив. Если задано соотношение m<=i<=j<=n, то массив треугольный.
Массивы, состоящие из элементов одного и того же типа, называются однородными. Одномерные однородные массивы называются векторами, двумерные - матрицами.

понятий и правил для описания структуры, называются моделями данных.
Распространены графовые

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

5.2. Модели данных, особенности их организации и поиска в них данных

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

исходными, в которые входят дуги с высшего уровня – порожденными. Вершины нижнего уровня, не имеющие порожденных узлов, называются листьями. Характерно отношение 1:М (один ко многим).

иметь более одного исходного, т.е. Один тип записи является членом

более чем одного типа набора. Для сетей характерны отношения М:1 и М:М.

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

процессу приведения их к двумерной табличной форме. К такой же форме могут быть приведены и иерархические и сетевые отношения.
В таблице каждая строка которых соответствует значениям свойств (атрибутов), которыми обладает объект данного типа; каждый из столбцов соответствует множеству значений, которые принимает некоторый атрибут этого типа.
Отношение есть множество векторов из n элементов – кортежей (X1….Xn), где n – (число столбцов) называемое степенью отношения. Совокупность значений одного атрибута (соответствующая столбцу таблицы) называется доменом.

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

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

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

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

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

5.3. Структура СУБД

Clipper, FoxBASE, R:BASE, Paradox, FoxPro? Oracle и т.д. Во всех

этих СУБД записи и поля имеют ограничение на число записей (128…10024) и длину (обычно 4000…5000 байт). Исключение составляет поле Memo, в котором хранят текстовую информацию большого объема.
Длина поля зависит от его типа. (Поля могут быть целыми, вещественными, строчными, логическими, типа «дата» и т.д.) В любое поле можно вписать только информацию именно этого типа.
Задание типа поля определяет множество объектов, множество операций над ними и множество правил, указывающих допустимое сочетание или применимость операций к тому или иному объекту данных.

размещение и связь в среде хранения, т.е. на машинных носителях.
Основными

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

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

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

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

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

указателями.

информация о связях между записями в файлах данных.

связей обозначается единицей, а отсутствие – нулем.

них снимается ограничение на наличие у порожденной записи не более

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

полезно рассматривать развитие системы БД во времени, называют жизненным циклом.

Жизненный цикл БД делят на 2 фазы: 1) анализ и проектирование; 2) реализация и функционирование.
В течение первой фазы осуществляется сбор требований пользователей и проектирование БД, в течение второй – компьютерная реализация и использование БД для решения прикладных задач.
Основная цель проектирования БД – обеспечение пользователей точными данными за приемлемое время.

трехуровневой схемы: внешнее представление, уровень ре6кализации, внутреннее представление (физический уровень).

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

описывающие сущности); связи (отношения между атрибутами).
На уровне реализации выбирают подход

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

Проектирование реализации
4. Физическое проектирование
Требования реализации
Общие информационные требования
Спецификации требований
Информационная модель
Характеристики СУБД
Логическая

СУБД-ориентированная схема

Характеристики ОС и ТС

Физическая структура БД

разработку прикладных программ, а также загрузку БД. Загрузка связана с

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