inf

Глава 1

Основные понятия

1.1Понятие информации

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

Выделим три похода к определению понятия информации:

субъективный;

объективный;

синтетический.

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

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

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

развитие у учащихся навыков в определ¼нном смысле правильной интерпретации ин-

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

1.2Определение и классификация информационных систем

Следует подчеркнуть, что понятие информационной системы (так же, как и понятие информации) определяется независимо от компьютерной техники (хотя и приобретает особую актуальность именно в связи с компьютерами). Формулируя понятие информационной системы, нужно исходить из понятия системы, относящейся к информации. Система это множество взаимосвязанных элементов, рассматриваемое как единое целое. Можно сказать, что информационная система это система, основным содержанием которой является информация (данные), а целью существования реализация определ¼нных информационных процессов. В соответствии с ГОСТ Р 51583-2000 "Защита информации информаци-

онный процесс это процесс создания, сбора, обработки, накопления, хранения, поиска,

распространения и использования информации . Можно сказать, что, начиная с древно-

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

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

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

защите информации (27.06.2006), информационная система совокупность содержащейся

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

и технических средств .

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

В истории развития информатики и вычислительной техники прослеживаются два направления: технологии вычислений и технологии, связанные с хранением информации. Изначально вычислительные устройства (ЭВМ и их предшественники арифмометры) использовались только для решения вычислительных задач (в основном военного или макроэкономического характера). Но в связи с изобретением вс¼ более емких и компактных устройств для долговременного хранения информации, сфера применения ЭВМ значительно расширилась. Начиная с 1970-х годов - времени появления ж¼стких дисков - вс¼ большую актуальность стало приобретать направление информационных систем, связанное с накоплением и обработкой больших объ¼мов информации. В частности, в 1970 г. была предложена реляционная модель данных (на сегодняшний день основная в базах данных), а в конце 1970-х годов и в начале 1980-х появились известные промышленные реляционные СУБД: DB2 (IBM), Ingres II (Computer Associates International, Inc.), Informix Dynamic Server (Informix Software, Inc.), Microsoft SQL Server, Oracle 8i (Oracle) и Sybase Adaptive Server (Sybase, Inc.).

Существует множество классификаций компьютерных информационных систем по разным признакам.

Классификация по масштабу:

одиночные;

групповые;

корпоративные;

глобальные.

Одиночные информационные системы предназначены для одного или нескольких пользователей, работающих в разное время на одном компьютере. Групповые информационные системы функционируют в локальной сети и ориентированы на нескольких пользователей, обычно относящихся к одному отделу организации. Такие системы реализуются на основе клиент-серверной архитектуры (например, Microsoft SQL Server, Sybase). Корпоративные информационные системы (КИС) обслуживают крупные организации и могут функционировать в нескольких локальных сетях на основе многоуровневой архитектуры (например, Oracle, Microsoft SQL Server). Глобальные информационные системы функционируют в интернете (например, поисковые системы). Для групповых и корпоративных систем существенно повышаются требования к надежности функционирования и сохранности данных. Эти свойства обеспечиваются поддержкой целостности данных, ссылок и транзакций в серверах баз данных.

Классификация по сфере применения (предметной области):

Информационно-справочные системы:

-геоинформационные системы (2ГИС);

-поисковые системы интернета (Google, Yandex и т.д.).

Офисные информационные системы:

-cистемы автоматизации документооборота;

-cистемы автоматизации бухуч¼та (1С).

Системы поддержки принятия решений.

Экспертные системы (например, медицинские).

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

Cистемы автоматизации научных исследований.

Систем автоматизированного проектирования (AutoCAD).

Автоматизированные системы обучения, электронные учебно-методические комплексы.

Банковские системы обработки транзакций.

Классификация по степени автоматизации:

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

Автоматизированные (в работе которых участвует человек).

Автоматические (без участия человека например, поисковые системы Интернета).

1.3Aрхитектура информационных систем

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

1.конкретное описание структуры данных о некоторой предметной области;

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

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

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

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

инфологические (семантические) модели;

даталогические (или просто логические) модели;

физические модели.

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

К инфологическим моделям относят разные варианты модели "Сущность-связь"и моделей на основе языка UML. Инфологические модели используются в основном на начальной стадии проектирования ИС. Стандартная каскадная разработка означает создание ИС

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

ции. Спиральная (или итерационная) разработка включает несколько циклов, в конце каждого из которых получается очередная (вс¼ более качественная) версия ИС. Для работы с инфологическими схемами и их преобразованием в даталогические и физические схемы существуют специальные программные среды, называемые CASE-иснтрументами (англ. Computer-Aided Software Engineering).

К даталогическим моделям относятся иерархическая, сетевая, логическая, реляционная, объектно-реляционная, объектно-ориентированная модели. Из них наиболее распростран¼нной на сегодняшний день (практически единственной широко распростран¼нной) является реляционная модель.

В англоязычной литературе распространена несколько иная терминология, связанная с архитектурой ANSI-SPARC (аббревиатура от American National Standards Institute/Standards Planning And Requirements Committee). Архитектура ANSI/SPARCэто неформальный стандарт архитектуры СУБД, предложенный в 1975 году комитетом SPARC, входящим в состав ANSI. Большинство современных коммерческих СУБД соответствуют этому стандарту. Основная идея архитектуры ANSI/SPARC деление СУБД на 3 уровня: внешний (уровень конечных пользователей), концептуальный (промежуточ-

ный, логический) и внутренний (уровень идеализированной физической реализации с

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

1.4Инфологическая модель Сущность-связь

Самой распростран¼нной инфологической моделью является модель Сущность-

связь (англ. ERM, Entity-Relationship Model). Предметная область в этой модели пред-

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

Определение 1.3 Типом сущности (или объектным множеством) называется множество однородных по тому или иному критерию, но различимых объектов, называемых

экземплярами сущности.

Например, университет это тип сущности, а НГПУ экземпляр сущности. Следует от-

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

типа сущности. Например, университет является экземпляром типа сущности разновид-

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

сущностью.

Атрибут это именованная характеристика сущности, причем у каждого экземпляра сущности имеется собственное значение одноим¼нного атрибута. Например, атрибутом

сущности университет может являться адрес , причем значения адреса для НГПУ и

НГТУ различны. Имя атрибута может быть одинаковым для различных сущностей ( ад-

рес общежития ). Информация об экземпляре некоторой сущности заключена в зна-

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

адрес для ЖКХ).

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

адрес является простым ключом для сущности университет (в предположении о том,

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

Связь между двумя или более сущностями это некоторое отношение между экземплярами этих сущностей. А именно, если сущности рассматривать как множества экземпляров, то связь R между сущностями E1; : : : ; En можно представить как подмножество их декартова произведения:

RE1 En:

Âчастности, возможна связь между экземплярами одной сущности E: R E E = E2, è

несколько различных связей между одними и теми же сущностями: R1; R2 E1 En. В свою очередь, связь можно рассматривать как сущность со своими атрибутами (так

называесая сущность-связь ).

Для графического изображения инфологических моделей применяются ER-диаграммы (ERD), предложенные Питером Чэнем в 1976 г. Сущности (точнее, типы сущностей) изображаются прямоугольниками, связи ромбами (от которых проводятся линии до связываемых сущностей), атрибуты овалами. Используются разные варианты связывающих

линий для указания разновидностей связей.

В статье [Ch1997] П. Чэнь предложил некоторые соответствия между конструкциями английского и китайского языков с одной стороны, и ER-диаграммами c другой. Это показывает удобство ER-диаграмм для концептуального моделирования в силу их близости естественному языку.

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

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

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

связи между экземплярами сущности иероглиф в китайском языке (П.Чэнь, 1997):

Выделяют четыре главных вида связи (бинарных отношения) между произвольными сущностями A и B:

1.Один-к-одному 1 1: каждому экземпляру сущности A соответствует в точности один экземпляр сущности B и наоборот. Иными словами, что связь 1 1 устанавливает биективное отображение между сущностями A и B как множествами экземпляров.

2.Один-ко-многим 1 1 (или 1:M): каждому экземпляру сущности А соответствует

8 Глава 1. Основные понятия

произвольное число экземпляров сущности B (в том числе, возможно, 0 или 1); каждому экземпляру сущности B соответствует ровно один экземпляр сущности A. Связь 1 1 устанавливает отображение (функцию) B ! A.

3.Многие-к-одному 1 1 (или M:1): и B находятся в отношении 1 1, если B и A находятся в отношении 1 1, т.е. связь 1 1 устанавливает отображение (функцию)

A ! B.

4.Многие-ко-многим 1 1 (или M:N): связь без ограничений, т.е. каждому экземпляру сущности соответствует произвольное число экземпляров сущности B и каждому экземпляру сущности B соответствует произвольное число экземпляров сущности A.

На практике, связи 1:M и M:1 обычно задаются с помощью соответствия первичного и внешнего ключей. Рассмотрим самую распростран¼нную и простейшую ситуацию: пусть у сущностей A и B имеется некоторый общий атрибут X, причем в сущности A он является

первичным ключом. Тогда связь 1:M по этому атрибуту определяется следующим образом: каждому экземпляру a сущности A ставится в соответствие каждый экземпляр b сущности

B такой, что значения атрибута X для a и b совпадают. Атрибут X называется внешним ключом в сущности B. В общем случае, можно определить связь 1:M, исходя из произ-

вольного взаимнооднозначного соответствия между возможными значениями некоторого ключа в А (простого или составного) и возможными значениями набора атрибутов в B (и тогда этот набор атрибутов называется внешним ключом в B). Следует отметить, что

термин внешний ключ общепринятый, но неудачный: дело в том, что внешний ключ

совсем не обязательно является ключом. А если внешний ключ в B вс¼-же оказывается ключом в B, то тогда определенная выше связь 1:M является на самом деле связью 1:1 (в предположении о том, что каждый экземпляр A связан с некоторым экземпляром B).

Глава 2

Реляционная модель данных и реляционная алгебра

2.1Формализация понятия отношения

Алгеброй называется некоторое множество (называемое основным множеством или носителем) вместе с определ¼нными на нем операциями (операторами). Реляционная алгебаэто алгебра, носителем которой является множество отношений. Реляционная алгебра является теоретической основой для реляционной модели данных (которая относится к даталогическим моделям).

В математике существует хорошо известное понятие отношением R между множества-

ìè D1; : : : ; Dn называется подмножество их декартова произведения: R D1 Dn. Но для реляционной алгебры такое определение не подходит. Дело в том, что реляционная алгебра должна не только удовлетворять критериям математической строгости, она также должна быть как можно более приближена к практике программирования. А в программировании важную роль играют имена (идентификаторы) объектов, как элемент синтаксиса языков запросов к базам данных. По-видимому, без явного уч¼та синтаксиса построение строгой и адекватной семантики программирования вообще невозможно. Поэтому в информатике предлагается несколько более сложное, чем в математике, но при этом вполне строгое понятие отношения.

Атрибутом называется упорядоченная пара A = ha; Di, где a называется именем атрибута A, а множество D доменом этого атрибута. Заголовком (или схемой) H назов¼м

конечное множество атрибутов, в котором у разных атрибутов разные имена (но могут быть одинаковые домены):

H = fha1; D1i; : : : ; han; Dnig; 8i; j(ai = aj ! i = j):

Через N(H) обозначим множество им¼н атрибутов из заголовка H. Так как в заголовке

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

и значений соответствующего домена: fha1; v1i; : : : ; han; vnig, ãäå 8i(vi 2 Dk). Обозначим через T (H) множество кортежей, соответствующих заголовку H. Для кортежа t через a(t)

10 Глава 2. Реляционная модель данных и реляционная алгебра

обозначим значение атрибута с именем a в кортеже t, то есть ha; a(t)i 2 t. Для произвольного набора атрибутов G H или их имен G(H) N(H) через t(G) обозначим проекцию t на G: t(G) := fha; vi 2 tj a 2 Gg. В частности, t(H) = t.

Отношение это пара R = hH; Bi, где H заголовок (называемый загловком или схемой отношения R), а B произвольное множество кортежей, соответствующих заголовку H. Множество B называется телом отношения R. Говорят, что t является кортежом отношения R, обозначение t 2 R, если кортеж t принадлежит телу отношения R, т.е. t 2 B. Количество атрибутов отношения R = hH; Bi , то есть мощность множества H, называется

степенью (синонимы: местностью, арностью) отношения. Количество кортежей отношения, то есть мощность его тела, называется кардинальным числом (или мощностью) отношения.

Заголовок отношения может быть пустым, в этом случае ему соответствует только

пустой кортеж, который является пустым множеством. Вырожденными отношениями назов¼м пары h?; ?i и h?; f?gi, в языке TutorialD они соответственно обозначают-

ñÿ TABLE_DUM è TABLE_DEE1. Иными словами, TABLE_DUM это отношение без атрибутов и без кортежей, а TABLE_DEE отношение без атрибутов с одним пустым кортежем.

2.2Реляционная алгебра

2.2.1Простейшие операции реляционной алгебры

Функции, аргументами (операндами) которых служат отношения, называют реляционными операциями (или операторами). Систематический подход в определении редяционных был впервые предложен Э.Ф. Коддом в 1970 году [4]. В реляционной алгебре выделяют 6 простейших (примитивных) операций, из которых все остальные могут быть получены композицией. Из этих шести примитивных операций три являются теоретикомножественными (объединение, разность, декартово произведение), остальные три называются специальными (выбор, проекция, переименование).

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

Объединение [:

1)hH; Bi = hH1; B1i [ hH2; B2i.

2)H1 = H2.

3)H := H1, B := B1 [ B2.

Пересечение \:

1)hH; Bi = hH1; B1i \ hH2; B2i.

2)H1 = H2.

3)H := H1, B := B1 \ B2.

Декартово произведение :

1Эти названия предложены Х.Дарвеном и возможно происходят от им¼н персонажей детских стишков

и Алисы в стране чудес Tweedledum (Траляля) и Tweedledee (Труляля).