12. Фундаментальные понятия теории бд и субд.

База данных — это информационные структуры, содержащие взаимосвязанные данные о реальных объектах. Особенностями такой совокупности данных являются: достаточно большие объемы информации; максимально возможная компактность хранения данных; возможность извлечения из базы данных разнообразной информации в определенной предметной области; удобные для пользователя вид и форма извлекаемой информации; высокая скорость доступа к данным; надежность хранения информации и возможность предоставления санкционированного доступа к данным для отдельных пользователей; удобство и простота конструирования пользователем запросов, форм и отчетов для выборки данных. Создание базы данных, ее поддержка и обеспечение доступа пользователей к ней осуществляется с помощью специального программного инструмента — системы управления базами данных. Система управления базами данных (СУБД) — это программное обеспечение для создания и редактирования баз данных, просмотра и поиска информации в них. Функции СУБД: 1) Определение данных – определить, какая именно инфо будет храниться в базе данных, задать свойства данных, их тип (например, число цифр или символов), а также указать, как эти данные связаны между собой. В некоторых случаях есть возможность задавать форматы и критерии проверки данных. 2) Обработка данных – данные могут обрабатываться самыми различными способами. Можно выбирать любые поля, фильтровать и сортировать данные. Можно объединять данные с другой, связанной с ними, инфо и вычислять итоговые значения. 3) Управление данными – можно указать, кому разрешено знакомиться с данными, корректировать их или добавлять новую инфо. Можно также определять правила коллективного доступа. Состав СУБД. Архитектурно СУБД состоит из двух основных компонентов: языка описания данных (ЯОД), позволяющего создать схему описания данных в базе, и языка манипулирования данными (ЯМД), выполняющего операции с базой данных (наполнение, обновление, удаление, выборку информации). Данные языки могут быть реализованы в виде тренажеров или интерпретаторов. Помимо ЯОД и ЯМД к СУБД следует отнести средства (или языки) подготовки отчетов (СПО), позволяющие подготовить сводки (отчеты) на основе информации, найденной в базе данных, по заданным формам. Язык описания данных (ЯОД) – это язык высокого уровня декларативного (непроцедурного) типа, предназначенный для формализованного описания типов данных, их структур и взаимосвязей. По технологии обработки базы данных делятся на централизованные и распределенные. Централизованная база данных хранится в памяти одной машины. Распределенная база данных состоит из нескольких частей, хранимых на нескольких машинах вычислительной сети. Работа с такой базой осуществляется с помощью системы управления распределенной базой данных – СУРБД. Централизованные базы данных по способу доступа делятся на: базы данных с локальным доступом (данные и процедуры их обработки хранятся на одной машине); базы данных с удаленным (сетевым) доступом. СУБД с удаленным доступом могут быть построены с использованием архитектур файл-сервер и клиент-сервер. Архитектура файл-сервер. Принцип организации: одна машина выделена в качестве центральной (сервер файлов), на ней хранится централизованная БД. Остальные машины сети выполняют функции рабочих станций. Архитектура клиент-сервер. Принцип организации: центральная машина (сервер базы данных) хранит централизованную БД и процедуры обработки. Клиент посылает запрос, он обрабатывается сервером, и данные, полученные по запросу, передаются клиенту. Основой базы данных является модель данных. Базы данных также могут быть иерархическими, сетевыми и реляционными. Иерархическая (древовидная) модель данных представляет собой иерархию элементов, называемых узлами. Узел — это совокупность атрибутов данных, описывающих информационный объект. На самом верхнем уровне имеется только один узел — корень. Сетевая модель также основывается на понятиях узел, уровень, связь. Сетевая модель данных — это модель, в которой порожденный узел может иметь более одного исходного узла. В сетевой структуре любой элемент любого уровня может быть связан с любым другим элементом. Реляционная модель базы данных состоит из одного или нескольких файлов, каждый из которых соответствует одной таблице. Основная цель проектирования базы данных — это сокращение избыточности хранимых данных, а следовательно, экономия объема используемой памяти, уменьшение затрат на многократные операции обновления избыточных копий и устранение возможности возникновения противоречий из-за хранения в разных местах сведений об одном и том же объекте.

Жизненный цикл базы данных.

Процесс проектирования, реализации и поддержания системы базы данных называется жизненным циклом базы данных (ЖЦБД). Процедура создания системы называется жизненным циклом системы (ЖЦС).

ЖЦБД состоит из следующих этапов:

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

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

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

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

5.Реализация – процесс превращения концептуальной модели в функциональную БД.

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

Типология БД Гипертекстовые БД

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

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

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

-информационных единиц (ИЕ), или «узлов», содержащих инфо, потенциально интересную для пользователей;

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

•функциональный аспект. Создание гипертекста и навигации в гиперпространстве являются нелинейной (непоследовательной) деятельностью.

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

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

Навигация является центральным понятием концепции гипертекста и означает управление процессом перемещения в гиперпростанстве из произвольного узла отправления в узел прибытия.

В настоящее время круг применения гипертекстовых систем достаточно широк. Перечислим некоторые сферы их применения:

• энциклопедии, словари, каталоги, справочники, оперативные руководства и инструкции, интерактивные системы технической документации; • Всемирная паутина (World Wide Web);

• системы обучения, интерактивные киоски (для музеев и выставок); • электронные справочники, электронные книги;

• учебные пособия, учебные задания, автоматизированное обучение и др.

Так же Базы данных бывают фактографическими и документальными. В фактографических БД содержатся краткие сведения об описываемых объектах, представленные в строго определенном формате. Фактографическая база данных — база, представленная поисковым образом документа и текстом в его полном или частичном объёмах, т. е. полнотекстовая или фрагментарная база. При этом содержание вводимых в ЭВМ фрагментов текстов определяется в соответствии с потенциальными информационными потребностями, характеристиками технических средств, возможностями программы и т.д. Для фактографической базы характерны соответствия «элемент = файл». То есть на каждого адресата заводится свой компьютерный файл.

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

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

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

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

Документальные системы предназначены для работы с документами на естественном языке: книги, тезисы, статьи... Наиболее распространенным видом ДС является информационно-поисковые системы (ИПС), которые предназначены для накопления и поиска по различным критериям документов.

16. Алгоритмы и алгоритмизация вычислительных задач. В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования — чем меньше детализация, тем выше уровень языка. По этому критерию можно выделить следующие уровни языков программирования: 1) машинные; 2) машинно-оpиентиpованные (ассемблеpы); 3) машинно-независимые (языки высокого уровня). Машинные языки и машинно-ориентированные языки — это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека. Языки высокого уровня делятся на: 1) алгоритмические (Basic, Pascal, C и др.), которые предназначены для однозначного описания алгоритмов; 2) логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания; 3) объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур. Основные преимущества алгоритмических языков перед машинными: 1) алфавит алгоритмического языка значительно шире алфавита машинного языка, что существенно повышает наглядность текста программы; 2) набор операций, допустимых для использования, не зависит от набора машинных операций, а выбирается из соображений удобства формулирования алгоритмов решения задач определенного класса; 3) формат предложений достаточно гибок и удобен для использования, что позволяет с помощью одного предложения задать достаточно содержательный этап обработки данных; 4) требуемые операции задаются с помощью общепринятых математических обозначений; 5) данным в алгоритмических языках присваиваются индивидуальные имена, выбираемые программистом; 6) в языке может быть предусмотрен значительно более широкий набор типов данных по сравнению с набором машинных типов данных. Таким образом, алгоритмические языки в значительной мере являются машинно-независимыми. Они облегчают работу программиста и повышают надежность создаваемых программ. Алгоритмом называется точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. В теории алгоритмов используется идея построения конкретных алгоритмических моделей, каждая из которых содержит конкретный набор элементарных шагов. С теоретической точки зрения наибольший интерес представляют модели, которые были бы одновременно универсальными и простыми, содержащими минимум необходимых средств. Поиск теоретических моделей алгоритма происходит в 3 направлениях, которые и определили 3 основных класса таких моделей. Первое направление основано на арифметизации алгоритма. Ясно, что любые данные можно закодировать в числах, и тогда всякое их преобразование станет арифметически вычислимым. Всякий алгоритм в таких моделях вычисляет значения некоторых числовых функций, а его элементарные шаги – это арифметические операции. Последовательности шагов определяются с помощью 2 основных способов. 1 способ: Суперпозиция, т.е. подстановка функций в функцию, порождающая математические формулы, в которых порядок действия определяется расстановкой скобок. Например: a*b+c/d, a*b=x, c/d=y, получаем х+у. 2 способ: Менее известен, хотя встречается в элементарной математике – это рекурсия, т.е. определение очередного значения функции через ранее вычисленные значения этой же функции. Пример: n!=1*2*3…*n. С помощью суперпозиции факториал через арифметические операции определить нельзя. Дело в том, что обычные суперпозиционные формулы содержат фиксированное число операций для любых значений элементов, а при вычислении факториала число усложнений растёт с ростом n. 0!=1;(n+1)!=1*2*3…*n*(n+1): n!=(n+1)!/n=1. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиции и рекурсивных определений, называются рекурсивными функциями. Они являлись исторически первым уточнением понятия алгоритма, т.е. первой универсальной алгоритмической моделью. Второе направление основано на простейшей идее: для того, чтобы алгоритм определялся однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и её действия, тем убедительней выглядит утверждение, что её работа и есть выполнение некоторого алгоритма, при этом структура машины должна быть универсальной, такой чтобы на ней можно было выполнять любой алгоритм. Эта идея привела к концепции абстрактной машины, как универсальной алгоритмической модели. Она была выдвинута А. Тьюрингом и В. Постом. Третье направление связано с уточнением понятия алгоритм, близко ко 2-му. Если рассмотреть механические формальные преобразования данных, не употребляя машинные терминологии, здесь применяется следующее: память, понятие машин, считывание, – то описание действующей машины превращается в систему подстановок, которые указывают, какие замены символов надо произвести и в каком порядке использовать сами подстановки. Наиболее известная алгоритмическая модель этого типа: «Нормальные алгоритмы Маркова». Появление точного понятия алгоритма позволило сформировать понятие алгоритмически неразрешимой проблемы, т.е. задачи, для решения которой не возможно построить алгоритмы. Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции) или алгоритма Маркова, которые её решили бы. Выделяют 3 крупных класса алгоритмов. Вычислительные алгоритмы, работающие со сравнительно простыми видами данных (числа, матрицы и т.п.), хотя сам процесс может быть долгим и сложным. Информационные – набор сравнительно простых процедур, работающих с большим объемом информации (алгоритмы баз данных). Управляющие – генерируют различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми они управляют. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные. Основными свойствами алгоритма являются: 1) детерминированность (определенность). Предполагает получение однозначного результата вычислительного процесса при заданных исходных данных. 2) результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат; 3) массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа; 4) дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений. Наибольшее распространение благодаря своей наглядности получил графический (блок-схемный) способ записи алгоритмов. Блок-схема – графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками. При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов: линейный; ветвящийся; циклический. Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов. Ветвящимся называется такой вычислительный процесс, в котором выбор направления обработки информации зависит от исходных или промежуточных данных (от результатов проверки выполнения какого-либо логического условия). Циклом называется многократно повторяемый участок вычислений. Вычислительный процесс, содержащий один или несколько циклов, называется циклическим. Этапы подготовки и решения вычислительных задач. 1) Постановка задачи: сбор информации; формулировка условия задачи; определение конечных целей; определение формы выдачи результатов; описание данных (их типов, диапазонов величин, структуры и т.п.). 2) Анализ и исследование задачи, модели: анализ существующих аналогов; анализ технических и программных средств; разработка математической модели; разработка структурных данных. 3) Разработка алгоритма: выбор метода проектирования алгоритма; выбор формы записи алгоритма (блок-схемы, псевдокод и др.); выбор тестов и метода тестирования; проектирование алгоритма. 4) Программирование: выбор языка программирования; уточнение способа организации данных; запись алгоритма на выбранном языке программирования. 5) Тестирование и отладка: синтаксическая отладка; отладка семантической и логической структуры; тестовые расчеты и анализ результатов тестирования; совершенствование программы. 6) Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5. 7) Сопровождение программы: доработка программы для решения конкретных задач; составление документации к решенной задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию.