Базы данных. Сортировка данных. Запросы в базах данных - Технологии поиска и хранения информации

Конспект

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

Отличительные признаки БД:

1) БД хранится и обрабатывается в вычислительной системе (т.е. некомпьютерные хранилища информации — архивы, картотеки и прочее — не считаются базами данных);

2) данные в БД логически структурированы (систематизированы) для обеспечения возможности их эффективного поиска и обработки в вычислительной системе;

3) БД включает в себя схему (метаданные), описывающие логическую структуру БД в формальном виде.

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

Нельзя путать понятия базы данных и системы управления базами данных!

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

Классификацию БД обычно проводят по типам используемых в них моделей данных:

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

2) сетевая модель данных состоит из набора записей и набора связей между этими записями; она в чём-то аналогична иерархической модели, но в сетевой БД связи являются направленными и могут соединять объекты разных ветвей дерева.

Пример:

3) реляционная БД состоит из нескольких взаимосвязанных таблиц:

Рассматривая таблицы, связанные по значениям поля ID, можно определить, что, например, Петров Пётр Петрович (ID = 2 — таблица 1) заказал сканер, № заказа = 111/12 (таблица 2), а также узнать его адрес и телефон (таблица 3).

Связи (“реляции”) между двумя какими-либо таблицами осуществляются через общее для них по смыслу (но не обязательно одинаковое по названию) поле. При этом возможны связи:

• “один к одному” — одной записи первой таблицы соответствует одна, и только одна запись второй таблицы, и наоборот (пример: в ОС MS-DOS полному имени файла однозначно соответствует запись номера начального кластера);

• “один ко многим” — одной записи первой таблицы может соответствовать много записей второй таблицы (пример: один и тот же учитель может вести уроки в нескольких классах);

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

• “многие ко многим” — много записей в первой таблице могут быть связаны с многими записями второй таблицы (пример: одного и того же ученика могут учить разные учителя, а один и тот же учитель может учить множество учеников). Подобный тип связей в реляционных БД не допускается и при необходимости реализуется как две связи “один ко многим” через промежуточную таблицу (в приведённом только что примере учитель связывается с учеником через номер класса и предмет). Показатель количеств связываемых объектов называют кардинальностью связи:

Тип связи	Кардинальность
“один к одному”	1:1
“один ко многим”	1:N
“многие к одному”	N:1
“многие ко многим”	N:N

Поиск данных в реляционной БД требует перехода от одной БД к другой в соответствии с имеющимися связями (в том числе многократно).

Основой реляционной БД является таблица.

Поля БД — это характеристики объектов (сущностей), информация о которых хранится в БД. Поля БД соответствуют столбцам таблицы.

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

Поля: Записи:	Поле 1	Поле 2	...	Поле n
Запись 1	Данное	Данное	...	Данное
Запись 2	Данное	Данное	...	Данное
...	...	...	...	...
Запись т	Данное	Данное	...	Данное

Характеристики, отражённые в виде полей БД, являются едиными (общими) для всех объектов. Объекты в БД должны различаться хотя бы одним значением какой-либо характеристики.

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

Выборка данных из БД — операция отбора записей БД (строк таблицы), соответствующих заданному условию (запросу на выборку).

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

Распределённая БД — совокупность логически взаимосвязанных БД, размещённых на различных узлах компьютерной сети.

Практические приёмы работы с БД

1. Поиск (выборка) информации в однотабличной БД

Запрос на поиск задаётся в виде структуры, аналогичной структуре записи БД, где отдельные поля могут быть пусты (пропущены в запросе), содержат константное значение или условие, накладываемое на значение данного поля.

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

Ручной поиск в БД:

• записи БД просматриваются поочерёдно;

• если значение первого по счёту (слева направо) непустого поля запроса совпадает с константой, заданной в том же поле в запросе, либо удовлетворяет условию, заданному в том же поле в запросе, то помечается эта запись БД;

• проверяются в этой записи БД остальные поля (слева направо) на соответствие константам либо условиям в тех же полях запроса;

• если все эти поля записи БД удовлетворяют значениям/условиям в таких же полях запроса, то эта запись БД включается в выборку; если хотя бы одно поле записи не удовлетворяет значению/ условию в таком же поле запроса, то эта запись БД пропускается (не включается в выборку).

2. Сортировка записей БД

Для выполнения сортировки записей БД задаются:

• одно или несколько названий полей, по содержимому которых нужно выполнить сортировку (порядок перечисления полей в запросе на сортировку важен и не обязательно соответствует порядку следования этих полей слева направо в структуре записи БД);

• для каждого такого поля — условие сортировки (для чисел — по возрастанию или по убыванию, для текста — по алфавиту или в порядке, обратном алфавитному).

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

Ручная сортировка в БД

Пусть нужно отсортировать записи БД — адресной книги по полям “Фамилия” (по алфавиту), “Имя” (по алфавиту) и “Отчество” (по алфавиту):

Фамилия	Имя	Отчество
Иванов	Дмитрий	Николаевич
Бунин	Андрей	Карлович
...
Львов	Илья	Андреевич
Иванов	Устин	Сергеевич
Александров	Николай	Иванович
...
Иванов	Дмитрий	Алексеевич

Тогда сначала выполняется такая перестановка записей БД, что в поле “Фамилия” значения (сверху вниз) следуют по алфавиту либо повторяются, например:

Фамилия	Имя	Отчество
Александров	Николай	Иванович
Бунин	Андрей	Карлович
...
Иванов	Устин	Сергеевич
Иванов	Дмитрий	Николаевич
Иванов	Дмитрий	Алексеевич
...
Львов	Илья	Андреевич

Записи БД переставляются (меняются местами) только целиком (целыми строками таблицы). Нельзя менять местами только значения в сортируемом поле, оставляя на прежних местах значения остальных полей!

В таблице присутствует группа записей с одинаковым значением первого сортируемого поля (“Фамилия” — “Иванов”). В пределах этой группы (и только в ней!) выполняется сортировка записей по значениям второго заданного поля “Имя”:

Фамилия	Имя	Отчество
Александров	Николай	Иванович
Бунин	Андрей	Карлович
...
Иванов	Дмитрий	Николаевич
Иванов	Дмитрий	Алексеевич
Иванов	Устин	Сергеевич
...
Яхин	Роман	Константинович

Выделяется подгруппа записей с одинаковым значением второго сортируемого поля (“Имя” — “Дмитрий”). В пределах этой подгруппы (и только в ней!) выполняется сортировка записей по значениям третьего заданного поля “Отчество”:

Фамилия	Имя	Отчество
Александров	Николай	Иванович
Бунин	Андрей	Карлович
...
Иванов	Дмитрий	Алексеевич
Иванов	Дмитрий	Николаевич
Иванов	Устин	Сергеевич
...
Яхин	Роман	Константинович

База данных отсортирована.

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

3. Поиск в многотабличной БД

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

Ручной поиск объекта в многотабличной БД

Пусть задана реляционная БД, состоящая из двух таблиц (под “ID” подразумевается уникальный индивидуальный номер человека, выступающий в качестве ключевого поля):

1) “ФИО”-“ID”-“пол”;

2) “ID родителя”-“ID сына/дочери”.

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

Процесс поиска:

1) в таблице 1 ищется ФИО заданного человека и определяется его ID;

2) переход в таблицу 2;

3) племянник — сын брата/сестры; брат/сестра — сын/дочь того же самого родителя; поэтому в таблице 2 для ID исходного человека, найденного в поле “ID сына/дочери”, ищутся все ГО его родителей;

4) для этих ID родителей, найденных в поле “ID родителя”, ищутся все ID детей; при этом ID исходного человека из поиска исключается как уже рассмотренный;

5) для этих ID братьев/сестёр, найденных в поле “ID родителя”, ищутся все ID их детей;

6) возврат в таблицу 1;

7) для найденных ID детей (это племянники и племянницы исходного человека) в таблице 1 ищутся их ФИО; среди них выбираются те, которые соответствуют людям мужского пола (определяется по полю “пол”).

Примеры такого поиска рассмотрены при разборе решений типовых задач.

Разбор типовых задач

Задача 1. В фрагменте базы данных представлены сведения о родственных отношениях. Определите на основании приведённых данных фамилию бабушки Ивановой A.И.

Решение

Первое, на что следует обратить внимание: каждому человеку, чьи ФИО и пол отражены в базе данных в таблице 1, присвоен конкретный индивидуальный номер.

Вторая особенность: таблица 2 определяет родственные связи между людьми (закодированными их индивидуальными номерами) по принципу “родитель — ребёнок”.

Исходное лицо: Иванова A.И.

1) Ищется запись о ней в табл. 1 (проверяя, что значение поля “Пол” для неё должно быть равно “Ж”) и определяется её индивидуальный номер: 23.

2) По таблице 2 определяется, кто является родителем человека с найденным индивидуальным номером 23. Для этого ищутся в таблице 2 все строки с номером 23 в поле “ID_Ребёнка” и определяется, какие индивидуальные номера соответствуют в найденных записях полю “ID_Родителя”. Это номера 13 и 85: очевидно, мать и отец Ивановой А.И. (Вернувшись к таблице 1, по найденным номерам можно определить по значению поля “Пол”, кто есть кто, хотя для решения данной задачи это не требуется.)

3) Родители Ивановой А.И. определены. Но по условию задачи требуется найти, кто является её бабушкой. Бабушка — это (в контексте рассматриваемого задания) мать одного из родителей Ивановой А.И., поэтому вышеописанную операцию поиска ID родителей по ID детей надо повторить для найденных на предыдущем шаге матери и отца Ивановой А.И.

• В таблице 2 в поле “ID_Ребёнка” ищется индивидуальный номер 85. Поскольку такое значение в указанном поле отсутствует, поиск по данной ветви генеалогического древа можно прекратить.

• В таблице 2 в поле “ID_Ребёнка” ищется индивидуальный номер 13 и определяются все значения индивидуальных номеров в поле “ID_Родителя”, соответствующих указанному значению поля “Ш Ребёнка”. Это номера82 и 95 (мать и отец матери Ивановой А.И., т.е. её дед и искомая бабушка).

4) Найдя ID деда и бабушки, в таблице 1 по этим номерам и значениям поля “Пол” определяется, кто из них кто.

Очевидно, что бабушкой Ивановой Л.И. является Цейс Т.Н.

Ответ: Цейс.

Задача 2. В фрагменте базы данных представлены сведения о родственных отношениях. Определите на основании приведённых данных ID племянника Черных Н.И.

Примечание: племянник — сын сестры или брата.

Решение

Исходное лицо: Черных НМ.

1) По таблице 1 определяется уникальный идентификационный номер Черных Н.И. Он равен 10.

2) В таблице 2 отражены родственные связи только типа “родитель — ребёнок”, а по условию задачи необходимо выявить родственную связь “сын сестры / брата”.

Сестра или брат являются детьми тех же самых родителей, что и интересующего лица. Поэтому, зная ID исходного человека (10), в таблице 2 определяются все строки, для которых в поле “ID_Ребёнка” записан код 10. Такая запись в таблице 2 одна и содержит в поле “ID_Родителя” идентификационный номер 85. (Вернувшись к таблицу 1, можно по этому идентификатору определить, что речь идёт об отце Черных Н.И. — Гуревиче И.Т.)

3) Теперь (по таблице 2) определяются для найденного ID родителя идентификационные номера всех его детей. Для этого в таблице 2 пишутся все записи (строки), где в поле “ID_Родителя” записан код 85. Соответствующие ID детей равны: 13, 82 и 10.

4) По таблице 1 для найденных идентификаторов определяется информация о людях (ФИО и пол):

код 13 — Цейс И.И. (пол “Ж”);

код 82 — Гуревич А.И. (пол “М”);

код 10 — Черных Н.И. (пол “М”).

Из группы найденных людей Черных Н.И. — исходное лицо. Оно исключается из рассмотрения.

5) Брат и сестра Черных Н.И. определены. Теперь нужно найти племянника Черных Н.И., зная, что это сын его брата или сестры. Для этого в таблице 2 ищутся записи (строки), где в поле “ID_Родителя” записано значение 13 или 82. (Записи для кода 82 в таблице отсутствуют, что облегчает задачу поиска.) Таких записей две, в них в поле “ID_Ребёнка” записаны значения кодов 42 и 23.

6) Вернувшись к таблице 1, для найденных кодов определяются ФИО и пол соответствующих лиц:

• код 42 — Цейс А.Т. (пол “Ж”);

• код 23 — Петров А.Т. (пол “М”).

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

Ответ: 23.

Примечание. Для наглядности можно изобразить “генеалогическое древо” всех рассмотренных в задаче лиц с указанием стрелками пути поиска племянника.

Задача 3. В фрагменте базы данных представлены сведения о родственных связях. На основании этих данных определите ID дяди Кусто М.И.

Решение

Дядя — это родной брат отца или матери. Но братьев и сестёр данная БД тоже “напрямую” искать не позволяет. Поэтому выстраиваем следующую цепь рассуждений:

• для заданного человека ищутся отец и мать;

• для них, в свою очередь, также ищутся родители (т.е. бабушка и дедушка заданного персонажа);

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

Теперь решение можно коротко записать так:

1) Кусто М.И. ID = 103 (из левой таблицы);

2) родители ID 103 → ID = 101 и 109 (по правой таблице);

3) родители ID 109 → ID = 105 и 107 (по правой таблице; для ID 101 в ней сведений о родителях нет);

4) дети ID 105 и 107 ID = 108, 109, 110 (также по правой таблице);

5) ID 109 — это уже ранее рассмотренный один из родителей Кусто М.И., поэтому данный номер из рассмотрения мы исключаем;

6) ID 110 — это Туринец И.И., женского пола (см. левую таблицу), значит, это тетя Кусто М.И., которая в данном случае нас не интересует;

7) ID 108 — это Туринец К.И., мужского пола (см. левую таблицу). Следовательно, это и есть искомый дядя Кусто М.И.

Задача решена.

Ответ: 108.

Примечание. “Генеалогическое древо” для данной задачи:

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

Задача 4. В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько прямых потомков (то есть детей и внуков) Кривич Л.П. упомянуты в таблице.

Решение

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

1) В таблице 1 ищем Кривич Л.П. и определяем её ID: 2146.

2) В правой таблице ищем все пары ID, в которых первое число (в левой колонке) равно 2146. Для них в правой колонке записаны ID 2302 и 3002. Это — дети Кривич Л.П.

3) В правой таблице ищем все пары ID, в которых первое число (в левой колонке) равно 2302 или 3002. Это — внуки Кривич Л.П.

4) Подсчитываем количество найденных в таблице 2 строк: 7 (двое детей и пятеро внуков).

Ответ: 7.