Односвязный список (однонаправленный связный список)

Разновидность связного списка — односвязный список, содержащий 3 элемента

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список». К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и основных операций:

· Операция, проверяющая список на пустоту.

· Три операции добавления объекта в список (в начало, конец или внутрь после любого (n-ого) элемента списка);

· Операция, вычисляющая первый (головной) элемент списка;

· Операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Характеристики

· Длина списка. Количество элементов в списке.

· Списки могут быть типизированными или нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Обычно списки типизированы.

· Список может быть сортированным или несортированным.

· В зависимости от реализации может быть возможен произвольный доступ к элементам списка.

Двусвязный список (двунаправленный связный список

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

Кольцевой связный список

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

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

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

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

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

Такие списки принято называть иерархическими.

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

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

Ассоциативные списки.

Часто одни и те же объекты представляют интерес с различных точек зрения. И возникает потребность включать информацию об этих объектах в различные списки.

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

Каждое звено имеет для каждого ассоциативного списка свою ссылку.

 

 

Вопрос № 2. Информационные технологии, применяемые органами прокуратуры.

Билет №18

Вопрос № 1. Понятие предметной области хранилищ данных информационных систем, модель сущность-связь.

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

 

Как любая модель, модель «сущность—связь» имеет несколько базовых понятий, которые образуют исходные кирпичики, из которых строятся уже более сложные объекты по заранее определенным правилам.

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

В основе ER-модели лежат следующие базовые понятия:

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

 

Вопрос № 2. Современные технические достижения, применяемые в органах внутренних дел.

Билет №19

Вопрос № 1. Функции, классификация и структура систем управления базами данных. Функции администратора базы данных.

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

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

 

СУБД организует хранение информации таким образом, чтобы ее было удобно:

 

просматривать,

пополнять,

изменять,

искать нужные сведения,

делать любые выборки,

осуществлять сортировку в любом порядке.

Классификация баз данных:

 

По характеру хранимой информации:

— Фактографические (картотеки),

— Документальные (архивы)

По способу хранения данных:

— Централизованные (хранятся на одном компьютере),

— Распределенные (используются в локальных и глобальных компьютерных сетях).

По структуре организации данных:

— Табличные (реляционные),

— Иерархические,

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

 

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

 

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

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

 

В реляционной БД используются четыре основных типов полей:

 

Числовой,

Символьный (слова, тексты, коды и т.д.),

Дата (календарные даты в форме «день/месяц/год»),

Логический (принимает два значения: «да» - «нет» или «истина» - «ложь»).

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

 

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

 

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

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

Популярные СУБД - FoxPro, Access for Windows, Paradox. Для менее сложных применений вместо СУБД используются информационно-поисковые системы (ИПС), которые выполняют следующие функции:

 

хранение большого объема информации;

быстрый поиск требуемой информации;

добавление, удаление и изменение хранимой информации;

вывод ее в удобном для человека виде.

 

Администратор базы данных — лицо, отвечающее за выработку требований к базе данных, её проектирование, реализацию, эффективное использование и сопровождение[1], включая управление учётными записями пользователей БД и защиту от несанкционированного доступа. Не менее важной функцией администратора БД является поддержка целостности базы данных.

Проектирование базы данных.

Оптимизация производительности базы данных.

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

Резервное копирование и Восстановление базы данных.

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

Обеспечение перехода на новую версию СУБД.

 

Вопрос № 2. Таблицы, ключи, реализация таблиц в виде цепочек. Алгоритмы поиска по таблице. Дихотомический поиск. Битовые деревья.

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

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

 

Ключи можно разделить по признаку общности как:

 

· Простой[1] – сформирован из значений единственного поля, которые однозначно определяют каждую запись

 

· Составной – сформирован из значений нескольких полей, применяется

 

По способу возникновения:

 

· Естественный – основан на уже существующем поле. Например поле фамилия.

 

+Меньший обьем данных

- Изменяемый

- Не гарантируется уникальность

· Суррогатный – основан на добавленном искусственным путем отдельном поле для однозначной идентификации.

+ Неизменность

 

+ Гарантированная уникальность

 

+ Эффективность – намного эффективнее проводить выборку по 8-байтовым числам, чем по громоздким записям.

 

- Дополнительное поле => увеличение общего объема

 

· Интеллектуальный ключ – основан на естественном ключе путем добавления дополнительного поля. Например:

Ключ

Фамилия

Имя

Отчество

ТИА

Тихонов

Игорь

Алексеевич

Примеряется крайне редко и лишь для при необходимости добавления сокращенных кодов(напр. ТИА-0701)

 

По ограничению целостности данных:

 

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

 

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

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

 

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

 

Фильтры и запросы позволяют отбирать записи, которые удовлетворяют условиям поиска. Условия поиска записей создаются с использованием операторов сравнения (=, >, < и т. д.).

 

Для числовых данных существуют следующие операции сравнения: = (равно), > (больше), < (меньше), >= (больше или равно), <= (меньше или равно) и <> (не равно).

 

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

- равно (сравниваются все символы);

- начинается с и не начинается с (сравниваются первые символы);

- заканчивается на и не заканчивается на (сравниваются последние символы);

- содержит и не содержит (сравниваются последовательности символов).

 

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

 

Дихотомический поиск - Метод быстрого поиска, при котором упорядоченный набор данных (список) разделяется на две части и операция сравнения всегда выполняется для среднего элемента списка: после сравнения одна половина списка отбрасывается и операция выполняется для оставшейся половины и т.д.

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

Рис. 1 Бинарное дерево

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

 

Билет №20

Вопрос № 1. Иерархическая и сетевая модели организации данных.

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

 

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

 

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

 

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

 

2.1. Иерархическая модель

 

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

 

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

 

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

 

 

Рис. 2. Древовидный граф

 

Реальный пример иерархической модели данных представлен на рис. 3 и 4.

 

 

Рис. 3. Пример иерархической модели данных

 

 

Рис. 4. Пример иерархической модели данных

 

Над иерархически организованными данными определенны следующие операции:

 

· Добавить в базу данных новую запись.

 

· Изменить значение данных предварительно извлеченной записи.

 

· Удалить некоторую запись и все подчиненные ей записи.

 

· Извлечь запись; в этой операции допускается задание условий выборки, например, извлечь сотрудников с окладом более 200 тысяч руб.

 

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

 

Первые системы управления базами данных, появившиеся в середине 60-х годов, позволяли работать с иерархической базой данных. Наиболее известной была иерархическая система IMS фирмы IBM. Известны также другие системы: PC/Focus, Team-Up, Data Edge и наши: Ока, ИНЭС, МИРИС.

 

2.2. Сетевая модель

 

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

 

 

Рис. 5. Представление связей в сетевой модели данных

 

 

Рис. 6. Пример сетевой модели данных

 

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

 

Над данными в сетевой базе могут выполняться следующие операции:

 

· Добавить – внести запись в базу данных.

 

· Извлечь – извлечь запись из базы данных.

 

· Обновить – изменить значение элементов предварительно извлеченной записи.

 

· Удалить – убрать запись из базы данных.

 

· Включить в групповое отношение – связать существующую подчиненную запись с записью-владельцем.

 

· Исключить из группового отношения – разорвать связь между записью-владельцем и записью-членом.

 

· Переключить – связать существующую подчиненную запись с другой записью-владельцем в том же групповом отношении.

 

Первоначально сетевая модель замышлялась как инструмент для программистов. В качестве базового языка программирования был выбран Cobol. Одна из первых сетевых моделей данных, разработанная группой CODASYL, была предложена в 1969 г. и развивалась до 80-х годов. К известным сетевым системам управления базами данных относятся: DBMS, IDMS, TOTAL, VISTA, СЕТЬ, СЕТОР, КОМПАС и др.

 

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

 

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

 

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

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

Вопрос № 2. Информационная система ГИБДД.

1. Описание предметной области

У ГИБДД есть три наиболее важные функциональные задачи:

· регистрация автотранспортных средств при совершении сделки купли-продажи;

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

· борьба с угоном автотранспортных средств, оперативный поиск угнанных машин и задержание преступников.

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

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

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

2. Виды запросов в информационной системе

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

2. Получить сведения о владельце автотранспортного средства по государственному номеру автомашины.

3. Получить "досье" на автомобиль по государственному номеру - номера двигателя, кузова и шасси, участвовал ли в ДТП, прошел ли техосмотр.

4. Получить перечень и общее число владельцев машин не прошедших вовремя техосмотр.

5. Получить статистику по любому типу ДТП за указанный период.

6. Получить результаты анализа ДТП: самые опасные места в городе, самая частая причина ДТП.

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

8. Получить список машин, отданных в розыск, будь то скрывшиеся с места ДТП или угнанные.

9. Получить данные об эффективности розыскной работы: количество найденных машин в процентном отношении.

10. Получить перечень и общее число угонов за указанный период.

11. Получить статистику по угонам: самые угоняемые марки машин, самые надежные сигнализации и т.п.

 

Билет №21

Вопрос № 1. Реляционная модель организации данных. Свойство атомарности. Нормализация.

Вопрос № 2. Информационное обеспечение судов.

Практическое задание.

В стартовом окне «Консультант Плюс» выберите раздел «Законодательство». Найдите Федеральный закон от 15.11.1997 № 143-ФЗ при помощи полей «Дата» и «Номер».

Вопрос № 1.

Реляционная модель данных (РМД) — логическая модель данных, прикладная теория построения баз данных, которая является приложением к задачам обработки данных таких разделов математики, как теория множеств и логика первого порядка.

На реляционной модели данных строятся реляционные базы данных.

Реляционная модель данных включает следующие компоненты:

Структурный аспект (составляющая) — данные в базе данных представляют собой набор отношений.

Аспект (составляющая) целостности — отношения (таблицы) отвечают определенным условиям целостности. РМД поддерживает декларативные ограничения целостности уровня домена (типа данных), уровня отношения и уровня базы данных.

Аспект (составляющая) обработки (манипулирования) — РМД поддерживает операторы манипулирования отношениями (реляционная алгебра, реляционное исчисление).

Термин «реляционный» означает, что теория основана на математическом понятии отношение (relation). В качестве неформального синонима термину «отношение» часто встречается слово таблица. Необходимо помнить, что «таблица» есть понятие нестрогое и неформальное и часто означает не «отношение» как абстрактное понятие, а визуальное представление отношения на бумаге или экране. Некорректное и нестрогое использование термина «таблица» вместо термина «отношение» нередко приводит к недопониманию. Наиболее частая ошибка состоит в рассуждениях о том, что РМД имеет дело с «плоскими», или «двумерными» таблицами, тогда как таковыми могут быть только визуальные представления таблиц. Отношения же являются абстракциями и не могут быть ни «плоскими», ни «неплоскими».

Для лучшего понимания РМД следует отметить три важных обстоятельства:

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

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

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

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

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

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

В рамках реляционной модели данных Э.Ф. Коддом были разработаны принципы нормализации отношений и предложен механизм, позволяющий любое отношение преобразовать к третьей нормальной форме.

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

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

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

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

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

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

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

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

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

Третья нормальная форма (3НФ) связана с понятием транзитивной зависимости. Пусть A, B, C - атрибуты некоторого отношения. При этом A B и B C, но обратное соответствие отсутствует, т.е. C не зависит от B или B не зависит от A. Тогда говорят,