Тема 26. Структурирование информации в базах данных

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

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

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

Требования к базам данных

Итак, хорошо спроектированная база данных:

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

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

3.Обеспечивает естественное, легкое для восприятия структурирование информации. Качественное построение базы позволяет делать запросы к базе более “прозрачными” и легкими для понимания; следовательно, снижается вероятность внесения некорректных данных и улучшается качество сопровождения базы.

4.Удовлетворяет требованиям пользователей к производительности базы данных. При больших объемах информации вопросы сохранения производительности начинают играть главную роль, сразу “высвечивая” все недочеты этапа проектирования.

Следующие пункты представляют основные шаги проектирования базы данных:

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

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

3.Поставить в соответствие сущностям и характеристикам – таблицы и столбцы (поля) в нотации выбранной Вами СУБД (Paradox, dBase, FoxPro, Access, Clipper, InterBase, Sybase, Informix, Oracle и т.д.).

4.Определить атрибуты, которые уникальным образом идентифицируют каждый объект.

5.Выработать правила, которые будут устанавливать и поддерживать целостность данных.

6.Установить связи между объектами (таблицами и столбцами), провести нормализацию таблиц.

7.Спланировать вопросы надежности данных и, при необходимости, сохранения секретности информации.

Основные понятия, используемые в реляционных БД

В реляционной теории одним из главных является понятие отношения. Математически отношение определяется следующим образом. Пусть даны n множеств D1,D2,...,Dn. Тогда R есть отношение над этими множествами, если R есть множество упорядоченных наборов вида, где d1 - элемент из D1, d2 - элемент из D2, ..., dn - элемент из Dn. При этом наборы вида называются кортежами, а множества D1,D2,...,Dn - доменами. Каждый кортеж состоит из элементов, выбираемых из своих доменов. Эти элементы называются атрибутами, а их значения - значениями атрибутов. рис. a представляет нам графическое изображение отношения с разных точек зрения.

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

· отношение, таблица, файл (для локальных баз данных);

· кортеж, строка, запись;

· атрибут, столбец, поле.

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

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

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

Для поддержания ссылочной целостности данных во многих СУБД имеется механизм так называемых внешних ключей. Смысл этого механизма состоит в том, что некоему атрибуту (или группе атрибутов) одного отношения назначается ссылка на первичный ключ другого отношения; тем самым закрепляются связи подчиненности между этими отношениями. При этом отношение, на первичный ключ которого ссылается внешний ключ другого отношения, называется master-отношением, или главным отношением; а отношение, от которого исходит ссылка, называется detail-отношением, или подчиненным отношением. После назначения такой ссылки СУБД имеет возможность автоматически отслеживать вопросы “ненарушения“ связей между отношениями, а именно:

· если Вы попытаетесь вставить в подчиненную таблицу запись, для внешнего ключа которой не существует соответствия в главной таблице (например, там нет еще записи с таким первичным ключом), СУБД сгенерирует ошибку;

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

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

Замечание. Существует два подхода к удалению и изменению записей из главной таблицы:

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

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

· если в главной таблице удалена запись, то в подчиненной таблице должны быть удалены все записи, ссылающиеся на удаляемую;

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

Операции реляционной алгебры

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

2.Объединение R=R1И R2;

3.Пересечение R=R1З R2

4.Вычитание R=R1–R2;

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

7.В результате получается отношение R, содержащее все попарные комбинации строк двух перемножаемых отношений R1 и R2. При этом если отношение R1 обладает арностью k1 и количеством строк s1, а отношение R2 – арностью k2 и количеством строк s2, то результирующее отношение R имеет арность k=k1+k2 и содержит в себе s=s1*s2 строк.

8.Проецирование на атрибуты R = ПРA1,…,An R1.

9.Здесь A1,…,An – атрибуты на которые происходит проецирование. В результате этой операции получается отношение, содержащее только указанные атрибуты исходного отношения. Количество строк в отношении при этом остается прежним.

10.Операция выборки R = ПРУСЛОВИЕ R1.

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

12.Операция соединения отношений по определенному условию.

Почему БД может быть плохой?

Приведем пример плохой БД. Пусть проектируется база “Питание”. Эту базу можно представить в виде одного отношения, представленного на рисунке.

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

1. Избыточность. Данные практически всех столбцов многократно повторяются. Повторяются и некоторые наборы данных (Блюдо-Вид-Рецепт, Продукт-Калорийность, Поставщик-Город-Страна). Нежелательно повторение рецептов, некоторые из которых намного больше рецепта «Лобио». И уж совсем плохо, что все данные о блюде (включая рецепт) повторяются каждый раз, когда это блюдо включается в меню.

2. Потенциальная противоречивость (аномалии обновления). Вследствие избыточности можно обновить адрес поставщика в одной строке, оставляя его неизменным в других. Если поставщик кофе сообщил о своем переезде в Харбин и была обновлена строка с продуктом кофе, то у поставщика «Хуанхэ» появляется два адреса, один из которых не актуален. Следовательно, при обновлениях необходимо просматривать всю таблицу для нахождения и изменения всех подходящих строк.

3. Аномалии включения. В БД не может быть записан новый поставщик («Няринга», Вильнюс, Литва), если поставляемый им продукт (Огурцы) не используется ни в одном блюде. Можно, конечно, поместить неопределенные значения в столбцы Блюдо, Вид, Порций и Вес (г) для этого поставщика. Но если появится блюдо, в котором используется этот продукт, не забудем ли мы удалить строку с неопределенными значениями?

По аналогичным причинам нельзя ввести и новый продукт (например, Баклажаны), который предлагает существующий поставщик (например, "Полесье"). А как ввести новое блюдо, если в нем используется новый продукт (Крабы)?

4. Аномалии удаления . Обратная проблема возникает при необходимости удаления всех продуктов, поставляемых данным поставщиком или всех блюд, использующих эти продукты. При таких удалениях будут утрачены сведения о таком поставщике.

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

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

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

Нормализация таблиц

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

Процесс нормализации заключается в приведении таблиц в так называемые нормальные формы. Существует несколько видов нормальных форм: первая нормальная форма (1НФ), вторая нормальная форма (2НФ), третья нормальная форма (3НФ), нормальная форма Бойса-Кодда (НФБК), четвертая нормальная форма (4НФ), пятая нормальная форма (5НФ). С практической точки зрения, достаточно трех первых форм – следует учитывать время, необходимое системе для “соединения” таблиц при отображении их на экране. Поэтому мы ограничимся изучением процесса приведения отношений к первым трем формам.

Этот процесс включает:

· устранение повторяющихся групп (приведение к 1НФ);

· удаление частично зависимых атрибутов (приведение к 2НФ);

· удаление транзитивно зависимых атрибутов (приведение к 3НФ).

Приведение к первой нормальной форме

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

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

Приведение ко второй нормальной форме

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

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

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

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

Приведение к третьей нормальной форме

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

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

Классификации структур данных

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

Определение 1

Структурой данных называется множество элементов данных и внутренних связей между ними.

Существуют простые и интегрированные структуры данных. Простые структуры данных сводятся к битам и организуются непосредственно из битов. К простым структурам относятся:

  • числовые;
  • битовые;
  • символьные;
  • логические;
  • указатели.

Интегрированные структуры данных организуются из простых и других интегрированных структур.

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

Определение 2

Изменчивостью структуры называется изменение числа элементов и связей между ними.

В соответсвии с признаком изменчивости структуры делятся на

  • Статические (векотр, массив, множество, запись, таблица);
  • Динамические (стек, очередь, строка, линейные связанные списки, разветвленные связанные списки, графы, деревья.).

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

  • Нелинейные(многосвязный список, граф, дерево);
  • Линейные с последовательным распределением (вектор, строка, массив, стек, очередь);
  • Линейные с произвольным связным распределением (односвязный, и двусвязный список).

Простые структуры и типы данных

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

Целый тип используется для представления количества дискретных объектов. Целые числа могут быть беззнаковыми или отрицательными. Внутреннее представление целого числа может занимать 1, 2 или 4 байта.

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

В случае двоичной системы счисления B=2.

Десятичный тип поддерживают не все языки программирования. Число такого типа представляется в виде m десятичных цифр из которых d цифр находятся справа от десятичной точки.

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

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

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

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

Примеры статических структур

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

Пример 1

Пусть дан массив с именем A.

Тогда элемент А равен 30.

Пример 2

Двумерный массив – это массив, каждый элемент которого сам является одномерным массивом.

В двумерном массиве у каждого элемента есть два индекса.

Определение 4

Записи (хеш-массивы, ассоциативные массивы) – это массивы, которые индексируются не натуральными числами, а строками.

Индекс элемента в таком массиве называется ключом. Для обращения к элементу используется имя массива и индекс.

Пример 3

Пусть дан хеш-массив с именем B.

Тогда элемент массива B[‘овощ’] равен ‘огурец’.

Примеры динамических структур

Для динамических структур память отводится «на ходу» в процессе выполнения программы. Для работы с динамическими типами данных в разных языках программирования широко используются указатели. Сами указатели имеют статический тип.

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

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

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

Что такое структура данных?

Я всегда считал, что «структура данных » — это термин, придуманный специально, чтобы сбить нас с толку. В конце концов, мне удалось выяснить, что такое структура данных, просто переставив местами слова в термине «структура данных » — с «data structure » на «structure of data «. В таком контексте акцент внимания смещается с данных (вещи ) на структуру (организацию ). Другими словами, мы акцентируем внимание не на вещах, а на процессе организации вещей.

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

Различные типы структур данных

Книги, подобно данным, могут быть организованы по-разному. Давайте представим, что у нас есть 20 книг. Как мы их структурируем?

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

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

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

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

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

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

Наша цель

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

Поскольку структур данных слишком много, чтобы их можно было полностью описать в этой серии статей, мы рассмотрим лишь некоторые из них, но самые распространенные:

  • Стек и Очередь;
  • Односвязные и двусвязные списки;
  • Дерево.

Заключение

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

Перевод статьи «Data Structures With JavaScript: What’s a Data Structure? » был подготовлен дружной командой проекта .

Хорошо Плохо

    Дерево - одна из наиболее часто используемых в веб-разработке структур данных. Каждый веб-разработчик, который писал HTML-код и загружал его в браузер, создавал…

  • Перевод

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

Очередь

Итак, поздоровайтесь с Лупи!

Лупи обожает играть в хоккей со своей семьей. И под “игрой”, я подразумеваю:

Когда черепашки залетают в ворота, их выбрасывает на верх стопки. Заметьте, первая черепашка, добавленная в стопку - первой ее покидает. Это называется Очередь . Так же, как и в тех очередях, что мы видим в повседневной жизни, первый добавленный в список элемент - первым его покидает. Еще эту структуру называют FIFO (First In First Out).

Как насчет операций вставки и удаления?

Q = def insert(elem): q.append(elem) #добавляем элемент в конец очереди print q def delete(): q.pop(0) #удаляем нулевой элемент из очереди print q

Стек

После такой веселой игры в хоккей, Лупи делает для всех блинчики. Она кладет их в одну стопку.

Когда все блинчики готовы, Лупи подает их всей семье, один за одним.

Заметьте, что первый сделанный ею блинчик - будет подан последним. Это называется Стек . Последний элемент, добавленный в список - покинет его первым. Также эту структуру данных называют LIFO (Last In First Out).

Добавление и удаление элементов?

S = def push(elem): #Добавление элемента в стек - Пуш s.append(elem) print s def customPop(): #удаление элемента из стека - Поп s.pop(len(s)-1) print s

Куча

Вы когда-нибудь видели башню плотности?

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

Он займет место, в зависимости от своей плотности.

Примерно так работает Куча .

Куча - двоичное дерево. А это значит, что каждый родительский элемент имеет два дочерних. И хотя мы называем эту структуру данных кучей, но выражается она через обычный массив.
Также куча всегда имеет высоту logn, где n - количество элементов

На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского.

Несколько простых функций для работы с кучами:

Global heap global currSize def parent(i): #Получить индекс родителя для i-того элемента return i/2 def left(i): #Получить левый дочерний элемент от i-того return 2*i def right(i): #Получить правый дочерний элемент от i-того return (2*i + 1)

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

Алгоритм:

  1. Добавляем элемент в самый низ кучи.
  2. Сравниваем добавленный элемент с родительским; если порядок верный - останавливаемся.
  3. Если нет - меняем элементы местами, и возвращаемся к предыдущему пункту.
Код:

Def swap(a, b): #меняем элемент с индексом a на элемент с индексом b temp = heap[a] heap[a] = heap[b] heap[b] = temp def insert(elem): global currSize index = len(heap) heap.append(elem) currSize += 1 par = parent(index) flag = 0 while flag != 1: if index == 1: #Дошли до корневого элемента flag = 1 elif heap > elem: #Если индекс корневого элемента больше индекса нашего элемента - наш элемент на своем месте flag = 1 else: #Меняем местами родительский элемент с нашим swap(par, index) index = par par = parent(index) print heap
Максимальное количество проходов цикла while равно высоте дерева, или logn, следовательно, трудоемкость алгоритма - O(logn).

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

MaxHeapify().

Алгоритм:

  1. Заменить корневой элемент самым нижним.
  2. Сравнить новый корневой элемент с дочерними. Если они в правильном порядке - остановиться.
  3. Если нет - заменить корневой элемент на одного из дочерних (меньший для min-heap, больший для max-heap), и повторить шаг 2.

Def extractMax(): global currSize if currSize != 0: maxElem = heap heap = heap #Заменяем корневой элемент - последним heap.pop(currSize) #Удаляем последний элемент currSize -= 1 #Уменьшаем размер кучи maxHeapify(1) return maxElem def maxHeapify(index): global currSize lar = index l = left(index) r = right(index) #Вычисляем, какой из дочерних элементов больше; если он больше родительского - меняем местами if l <= currSize and heap[l] > heap: lar = l if r <= currSize and heap[r] > heap: lar = r if lar != index: swap(index, lar) maxHeapify(lar)
И вновь максимальное количество вызовов функции maxHeapify равно высоте дерева, или logn, а значит трудоемкость алгоритма - O(logn).

Делаем кучу из любого рандомного массива
Окей, есть два пути сделать это. Первый - поочередно вставлять каждый элемент в кучу. Это просто, но совершенно неэффективно. Трудоемкость алгоритма в этом случае будет O(nlogn), т.к. функция O(logn) будет выполняться n раз.

Более эффективный способ - применить функцию maxHeapify для ‘под-кучи ’, от (currSize/2) до первого элемента.

Сложность получится O(n), и доказательство этого утверждения, к сожалению, выходит за рамки данной статьи. Просто поймите, что элементы, находящиеся в части кучи от currSize/2 до currSize, не имеют потомков, и большинство образованных таким образом ‘под-куч’ будут высотой меньше, чем logn.

Def buildHeap(): global currSize for i in range(currSize/2, 0, -1): #третий агрумент в range() - шаг перебора, в данном случае определяет направление. print heap maxHeapify(i) currSize = len(heap)-1

Действительно, зачем это все?

Кучи нужны для реализации особого типа сортировки, называемого, как ни странно, “сортировка кучей ”. В отличие от менее эффективных “сортировки вставками” и “сортировки пузырьком”, с их ужасной сложностью в O(n 2), “сортировка кучей” имеет сложность O(nlogn).

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

Def heapSort(): for i in range(1, len(heap)): print heap heap.insert(len(heap)-i, extractMax()) #вставляем максимальный элемент в конец массива currSize = len(heap)-1
Чтобы обобщить все вышесказанное, я написала несколько строчек кода, содержащего функции для работы с кучей, а для фанатов ООП оформила все в виде класса .

Легко, не правда ли? А вот и празднующая Лупи!

Хеш

Лупи хочет научить своих детишек различать фигуры и цвета. Для этого она принесла домой огромное количество разноцветных фигур.

Через некоторое время черепашки окончательно запутались

Поэтому она достала еще одну игрушку, чтобы немного упростить процесс

Стало намного легче, ведь черепашки уже знали, что фигуры рассортированы по форме. А что, если мы пометим каждый столб?

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

Допустим, номер столба вычисляется следующим образом:

Фио летовый тре угольник
ф+и+о+т+р+е = 22+10+16+20+18+6 = Столб 92

Кра сный пря моугольник
к+р+а+п+р+я = 12+18+1+17+18+33 = Столб 99

Мы знаем, что 6*33 = 198 возможных комбинаций, значит нам нужно 198 столбов.

Назовем эту формулу для вычисления номера столба - Хеш-функцией .

Код:
def hashFunc(piece): words = piece.split(" ") #разбиваем строку на слова colour = words shape = words poleNum = 0 for i in range(0, 3): poleNum += ord(colour[i]) - 96 poleNum += ord(shape[i]) - 96 return poleNum
(с кириллицей немного сложнее, но я оставил так для простоты . - прим.пер. )

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

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

Ладно, но допустим мы ищем “кар амельный пря моугольник” (если, конечно, цвет “карамельный” существует).

HashFunc("карамельный прямоугольник")
вернет нам 99, что совпадает с номером для красного прямоугольника. Это называется “Коллизия ”. Для разрешения коллизии мы используем “Метод цепочек ”, подразумевающий, что каждый столб хранит список, в котором мы ищем нужную нам запись.

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

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

Еще раз, поиск, не зависящий от количества элементов! Мы можем использовать хеш-таблицы для всего, что имеет гигантские размеры.

Хеш-таблицы также используются для поиска строк и подстрок в больших кусках текста, используя алгоритм Рабина-Карпа или алгоритм Кнута-Морриса-Пратта , что полезно, например, для определения плагиата в научных работах.

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

Переведено для Хабра запертым на

| Представление о базах данных

Уроки 35 - 37
Представление о базах данных

Изучив эту тему, вы узнаете:

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

Роль информационной системы

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

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

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

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

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

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

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

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

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

Как же организована подобная информационная система и каким образом можно организовать хранение и представление информации в ней?

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

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

Если в качестве примера рассмотреть предметную область Школа, то в этой области можно выделить следующие классы объектов: ученики, учителя, обслуживающий персонал, учебные предметы, помещения и т. д. Между этими объектами существуют определенные отношения и связи.

Рассмотрим другой пример. В предметной области Поликлиника можно выделить следующие классы объектов: врачи, пациенты, диагнозы, специальности врачей и пр. Связи между объектами выделенной предметной области отображены на рис. 4.1.

Рис. 4.1. Пример взаимосвязи классов объектов предметной области Поликлиника

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

Возникает вопрос: как следует представить информацию об этих объектах?

Можно было бы привести такое описание: песня «Spice up your life» в исполнении группы из Англии «Spice Girls», написанная в стиле «Hip-hop» в 1997 году, или, например, песня 1996 года российской группы «Иванушки International» под названием «Тучи» в стиле «Рор».

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

Представить такую информацию можно разными способами, например в виде списка:

1. «Spice up your life», «Spice Girls», Hip-hop, 1997, Англия;
2. «Тучи», «Иванушки International», Pop, 1996, Россия;
3. «Моряк», «Агата Кристи», Rock, 1997, Россия.

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

Таблица 4.1. Сведения о песнях


Таким образом, мы перешли к структурированной форме представления данных, в которой данные и их смысловая интерпретация отделены друг от друга и представлены в некоторой форме. Этот процесс получил название «структурирование данных».

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

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

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

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

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

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

Поле - это простейший объект базы данных, предназначенный для хранения значений одного параметра описываемого реального объекта.

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

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

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

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

Запись - это совокупность значений параметров конкретного объекта.

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

Контрольные вопросы и задания

1. Какова роль информационной системы при работе с информацией?

2. В чем состоит цель создания информационной системы?

3. Что такое предметная область?

4. Приведите примеры, когда возникает необходимость отбора нужной информации? Как вы это делаете? Важно ли при этом понятие «предметная область»?

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

6. Что такое структурирование данных?

7. Что такое база данных?

8. Что такое поле?

9. Что такое структура записи?

10. Что такое запись?

11. Представьте параметры объектов конкретной предметной области в виде таблицы. Укажите в таблице поля, записи, структуру записи.