База данных. Структуры данных
 Скачать 31.59 Kb.
|
|
Структуры данных. Структура данных – форма хранения и предоставления информации. (Делится на: Физическую структуру (отражает способ физического представления данных в памяти машины) и логическую структуру) Статистическая структура данных – совокупность фиксированного количества переменных постоянной размерности с неизменным характером связи между ними. Динамическая структура данных – совокупность переменных, количество, размерность или характер взаимосвязей между которыми меняется во время программ Структуры данных: Простые базовые структуры(числовые, символьные, логические) Статические(вектор, массивы, таблицы) Полу статические(стеки, очереди, строки) Динамические(графы, деревья, линейные/ разветвлённые связные списки) Файловые структуры(последовательные, прямого/ комбинированного доступа) Связный список – динамическая структура данных, состоящая из узлов, каждый из которых содержит ссылки как на собственные данные, так и на другие узлы стека. Стек – динамическая линейная структура данных, для которой определены всего две операции изменения набора элементов: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует принцип LIFO (Last in, First out) – последний пришел и первый ушел. Очередь – очень похожая на стек, динамическая структура данных, с той лишь разницей, что она реализует принцип FIFO (first in, first out) – первым пришел и первым ушел. В программировании, например, с помощью очередей обрабатывают события пользовательского интерфейса, обращение клиентов к веб-сервисам и прочие информационные запросы. Иерархическая структура данных. Элемент в иерархической структуре данных характеризуется ссылкой на вышестоящий в иерархии элемент и порядковым номером в линейной последовательности своего уровня. Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Сетевые структуры данных. Элемент в сетевой структуре данных характеризуется набором связей с другими соседними элементами. В таких структурах данных начальный и корневой элементы явно не выделены Граф – динамическая сетевая структура данных, представленная набором вершин и ребер – связей между вершинами. Каждая вершина может быть связана с любым числом других вершин или с самим собой. Полу статические структуры данных. Характеристика: 1) Имеет переменную длину и простые процедуры ее изменения 2) Изменение длины структуры происходит в определенных пределах, не превышая какого-нибудь предельного значения. На логическом уровне является последовательностью данных, связанная отношениями линейного списка. Доступ к элементу осуществляется по его порядковому номеру. На физическом уровне – последовательность ячеек в памяти, где каждый следующий элемент расположен в памяти в следующем слоте. Пример: стеки, очереди, деки, строки. Дек (deq – double ended queue – очередь с двумя концами) – особый вид очереди в виде последовательного списка, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Операции над структурированными данными: создание, уничтожение, выбор (доступ), обновление. Динамическая структура данных – совокупность переменных у которых меняются связи в ходе работы программы. Бинарные деревья. Дерево – структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. UPD. Связный граф без циклов называется деревом. Бинарное дерево – упорядоченное дерево, в котором каждая вершина имеет не более двух «сыновей». Неполное дерево – дерево, узел которого содержит не более одного потомка. Базовые свойства деревьев: 1) Дерево не содержит циклов 2) Каждая вершина дерева соединяется с его корнем единственным путем. Корень – начальный узел дерева. Лист – узел, из которого не выходит ни одной дуги. Основные понятия: Глубина / уровень вершины – длина пути от корня до этой вершины. UPD. Глубина корня равна 0 Высота вершины – длина максимальной вершины от этой вершины до листа. Высота дерева – длина максимального пути от корня до листа. «Родитель» - вершина, которая находится непосредственно над другой вершиной. «Потомок» - вершина, которая расположена непосредственно под другой вершиной. Число потомков вершины –называется ее степенью. Реляционная модель данных -модель хранения данных, построенная на взаимоотношении составляющих ее частей. В противном случае представляет собой двухмерную таблицу, а при создании сложных информационных моделей составит совокупность взаимосвязанных таблиц. Цели создания реляционной модели: 1) Обеспечение высокой степени независимости от данных 2) Нормализация отношений, т.е. создание отношений без повторяющихся групп 3) Расширение языков управления данными засчет включения операций над множествами. Термины описания структуры данных: Отношение – таблица; кортеж – строка или запись; кардинальность – количество строк; атрибут – столбец или поле; степень – количество столбцов; первичный ключ – идентификатор; домен – множество дополнительных значений. Реляционные ключи. Ключ – минимальный набор атрибутов, по значениям которых можно однозначно выбрать требуемый экземпляр сущности. Первичный ключ – потенциальный ключ, который выбран для уникальной идентификации кортежей внутри отношения. Простой ключ – ключ, состоящий из нескольких атрибутов. Альтернативные ключи – потенциальные ключи, которые не были выбраны в качестве первичного ключа. Внешний ключ – атрибут или множество атрибутов внутри отношения, которое соответствует потенциальному ключу некоторого отношения. Целостность БД соответствие, имеющиеся в БД информации ее внутренней логики, структуре и явно заданным правилам. Ограничение целостности – каждое правило, налагающее некоторое ограничение на возможности БД. Обеспечение целостности БД – выполнение ряда ограничений, соблюдение которых необходимо для поддержания непротиворечивости хранимых данных. Ограничение целостности : Ограничение диапазонов значений(Контроль значений атрибутов отношений) Структурное ограничение(Фиксирует 2 требования целостности, которые должны поддерживаться реляционными СУБД: целостность сущностей и целостность ссылок) Реляционная алгебра – теоретический язык запросов, наглядно описывающий выполняемые над отношениями действия. Основные операции РА: объединение; селекция; вычитание; проекция; декартово произведение. UPD. И три вспомогательные операции РА, которые могут быть выражены через основные: пересечение; соединение; деление. ER модель / модель «сущность-связь» - одна из методик моделирования предметной области. Одна из наиболее известных методик базируется на использовании графических диаграмм, включающих наибольшее число разнородных компонентов ERD ER-модель должна определять связь между объектами. Сущность – реальный или представляемый объект, информация о котором должна сохраняться и быть доступна. UPD. Каждая сущность в модели изображается в виде прямоугольника, содержащего имя сущности. Экземпляр сущности – конкретный представитель данной сущности. Атрибут сущности – поименованная характеристика сущности. Связь – некоторая ассоциация между двумя сущностями. Одна сущность может быть связана с другой или сама с собой. Связи позволяют по одной сущности находить другие сущности, связанные с нею. Табличные структуры данных. Элемент в табличной структуре данных характеризуется двумерным индексом строки и индексом столбца, на пересечении которого он находится. Пример – двумерный массив и таблицы реляционной базы данных. Excel. Электронные таблицы позволяют обрабатывать большие массивы числовых данных. В отличии от таблиц на бумаге, электронные таблицы обеспечивают проведение динамических вычислений, т.е. пересчет по формулам при введении новых чисел. Электронные таблицы – приложение, работающее в диалоговом режиме, хранящее и обрабатывающее данные прямоугольных таблицах. При перемещении или копировании формулы из активной ячейки относительные ссылки автоматически изменяются в зависимости от положения ячейки, в которую скопирована или перемещена формула. Абсолютные ссылки используются для указания фиксированного адреса ячейки. При перемещении или копировании формулы, абсолютные ссылки не изменяются. В абсолютных ссылках перед номер столбца и именем строки ставится знак $. 13.Объекты БД. 1) Таблица (основной объект БД. Все остальные объекты БД создаются на основе существующих таблиц) 2) Запросы (служат для извлечения данных из таблиц и представления их пользователю в удобном виде) 3) Формы (с их помощью можно добавлять новые данные, редактировать или удалять существующие. Позволяют отображать данные из таблиц и запросов в более удобном виде) 4) Отчеты (предназначены для печати данных, содержащихся в таблицах и запросах, в красиво оформленном виде) 5) Макросы (набор специальных макрокоманд, которые запускаются простым нажатием нескольких клавиш и могут выполнять такие действия, как открывание таблиц и форм, управление окнами и т.д.) 6) Модули (специальная программа, написанная на языке VBA, служащая для автоматизации работы с БД) 7) Страницы (содержит компоненты, через которые осуществляется связь переданной web-страницы с базой данных, остающейся на сервере) 14.Фильтр – набор условий, применяемый для отбора подмножества записей. В MS Access существуют фильтры 4 типов: 1) фильтр по выделенному 2) обычный фильтр (фильтр по форме) 3) расширенный фильтр 4) фильтр по вводу 15.Запросы – объект БД, который служит для извлечения который служит для извлечения данных из таблиц и представления их в удобном виде. Особенность запросов – черпают данные из базовых таблиц и создают на их основе временную таблицу. QBE - запросы (Query by example) – запросы, строящиеся с помощью конструктора запросов, представляющего собой графический инструмент для создания запросов по образцу. SQL – запросы (Structured Query Language) – запросы, строящиеся при помощи унифицированного набора инструкций SQL. 16.Отчет – особая форма представления данных, предназначенная для вывода на печать в удобной для чтения и анализа формы с группировкой записей по нескольким уровням, сортировкой значений, вычислением итогов и средних значений, включением графических объектов (диаграмм, графиков и т.д.) 17.SQL – формальный непроцедурный язык программирования, применяемый для создания, модификации и управления данными в произвольной реляционной БД, управляемой соответствующей системой управления БД. SQL описывается на исчислении кортежей. 18.Основные понятия Бд База данных – именованная совокупность структурированных данных, отражающая состояние объектов и их отношение в рассматриваемой предметной области. Система Управление Баз Данных (СУБД) – совокупность языковых и программных средств, предназначенных для создания, ведения и использования БД многими пользователями. Основные возможности СУБД: 1) Высокая надежность хранения информации 2) Обновление, расширение, пополнение баз данных 3) Вывод полной и достоверной информации на запросы 4) Обеспечение защиты информации Основные функции СУБД: 1) Создание структуры СУБД 2) Заполнение БД информацией 3) Изменение (редактирование) структуры и содержания СУБД 4) Поиск информации в БД 5) Сортировка данных 6) Защита данных 7) Проверка целостности БД Целостность данных в БД – их соответствие схеме БД, а также другим правилам и условиям, гарантирующим непротиворечивость данных и их согласованность с предметной областью Ограничение целостности – условия, которым должны отвечать корректные данные Банк данных – система специальным образом организованных данных – БД, программных, технических, языковых, организационно-методических средств, предназначенных для обеспечения централизованного накопления и коллективного многоцелевого использования данных. Предметная область – часть реальной среды, которая описывается и отражается в БД. Это информационная сторона функционирования автоматизированной системы, отражающая множество объектов и связей между ними.    Классификация БДПо характеру хранимой информации: По структуре организации данных: По структуре хранения данных: 1)Фактографические БД 1)Централизованные 1)Реляционные 2)Документальные БД 2)Распределенные 2)Иерархические 3)Сетевые |