Водовозов В.М, Водовозов A.M. Введение в вычислительную технику и компьютерные технологии: Учебное пособие.-
Подождите немного. Документ загружается.
71
содержимое ячейки. Всякое изменение данных ведет к автоматическому изменению
значений в других ячейках, зависящих от редактируемой. Строка состояния в
нижней области интерфейса содержит информацию о текущем состоянии
программы, а главное меню в верхней части экрана отражает функциональные
возможности табличного процессора. После обращения к любому из пунктов
главного меню раскрывается ниспадающее меню, которое, в свою очередь, может
быть дополнено диалоговым окном или вызывает конкретную команду.
Чрезвычайно простой язык программирования табличных процессоров
реализует традиционные математические и логические операции, вычислительные
и строковые фу нкции. В качестве аргументов функций и операндов в формулах
выступают числа и ссылки на адреса ячеек. Благодаря этому, каждая электронная
таблица обычно формируется пользователем в зависимости от его потребностей, а
не программируется профессиональным программистом заранее. Ей можно придать
упорядоченную структуру с четким разделением полей и записей. В то же время, ее
можно использовать и как рабочую тетрадь с разбросанными в случайном порядке
формулами, текстами, примерами расчетов, графиками, рисунками. Важной
особенностью табличного процессора является отсутствие в его базовом языке
управляющих структур, организующих циклические процессы. Поэтому все
вычисления выполняются как бы фронтально, наглядно, и все промежуточные
результаты доступны пользователю.
Способность электронной таблицы немедленно проводить большой объем
вычислений при изменении исходных данных во многом определяет успех этого
вида программного обеспечения. Она позволяет оценить влияние самых разных
факторов на ход и результаты вычислительного процесса и особенно полезна для
организации табло и расписаний, выполнения многовариантных расчетов, решения
многокритериальных задач, проведения многофакторного эксперимента, анализа
чувстви-тельности параметров. Табличные процессоры используются в
исследовании линейных, квадратичных, полиномиальных функций, в анализе
матриц и решении систем уравнений, в алгоритмах численного интегрирования и в
ходе статистической обработки информации.
Исходные данные вводятся в формулы не только с клавиатуры, но также с
использованием механизма указателей. Этот способ позволяет задавать в качестве
операндов адреса ячеек, выбирая их указателем мыши. Жесткий синтаксический и
семантический контроль исключает всякое нарушение работоспособности системы
при вводе ошибочных данных, хотя интерфейс табличного процессора и не
препятствует заданию любой, даже недостоверной и нереальной информации.
Пользователь полностью освобожден от контроля типов данных, а их размер
отражается только на форме представления информации на экране, но не на
результатах обработки. Поэтому расчеты выполняются всегда по реальным
формулам, и каждая ошибка в расчетах имеет ясное происхождение и четкий
источник. Ввод больших объемов информации невозможен без использования
операций копирования и переноса. При переносе формулы все ссылки на ячейки
72
сохраняются. Иначе обстоит дело с копированием, в ходе которого ссылки в
формулах смещаются в направлении копирования. Правда, этого можно избежать,
используя абсолютную адресацию.
Впервые электронная таблица - программа VisiCalc – была разработана Д.
Бриклином и Б. Фрэнкстоном в 1979 г. для компьютера Apple 2 и впоследствии
перенесена на IBM PC. А сегодня наибольшей популярностью среди табличных
процессоров пользуются пакеты Excel компании Microsoft, 1-2-3 фирмы Lotus,
Quattro Pro корпорации Borland. Для программ этого поколения характерно:
o совмещение с деловой графикой для подготовки профессиональных
печатных объектов с иллюстрациями и слайдов;
o наличие многих функций текстовых процессоров, сопровождаемых в
режиме WYSIWYG;
o графический пользовательский интерфейс в стандарте CUA;
o наличие средств управления большими электронными книгами (до 65536
строк, 256 столбцов и 256 листов);
o импорт из баз данных; возможность создания многомерных моделей и
связи таблиц, обилие типов файлов для сохранения результатов;
o наличие средств решения систем уравнения, задач линейного
программирования и статистической обработки данных.
4.2. Базы данных
4.2.1. Организация данных
Открылась бездна, звезд полна.
Звездам числа нет, бездне – дна.
М. Ломоносов
Множества
Первичными в любой теории являются понятия
множества
и его
элементов
. Если элемент
a
принадлежит множеству
A
, то пишут
a
∈
A
. Если
A
содержит
n
элементов, то пишут
A = { a
1
, a
2
, …, a
n
}
, где
a
1
, a
2
, …, a
n
-
все элементы
множества
A
и
a
i
≠
a
j
для
i
≠
j
. В свою очередь, элементу
a
ничего не принадлежит.
Множество
A1
называют подмножеством
A
и обозначают
A1
⊂
A,
если каждый
элемент
A1
принадлежит
A
.
Два множества
A
и
B
считаются равными, если
A
⊂
B,
где
B
⊂
A
.
Как известно, информатика рассматривает любые множества описываемые
языком преобразования данных. Простым примером информационного множества
может быть такой:
WORLDINFO = { IBM, 1911, Герстнер, Motorola, 1928, Фишер, Intel, 1967,
Гроув, Microsoft, 1975, Балмер, Apple, 1975, Джобс }
73
Если
{a
1
, a
2
} = {a
2
, a
1
}
, то множество считается не упорядоченным, в
противном случае
{a
1
, a
2
}
называют упорядоченным множеством и обозначают
парой
(a
1
, a
2
)
. Множество, содержащее все возможные пары
(a, b)
элементов
a
∈
A
и
b
∈
B,
называется декартовым произведением
A
×
B
. Пусть, например, на
множестве
WORLDINFO
определены входящие в него подмножества:
A = { Microsoft, 1975, Балмер }, B = { Apple, 1975, Джобс }.
Тогда
A
×
B = {(Microsoft, Apple), ( Microsoft, 1975), ( Microsoft, Джобс),
(1975, Apple), (1975, 1975,), (1975, Джобс), (Балмер, Apple),
(Балмер, 1975), (Балмер, Джобс)}
Относительно элементов
a, b,…,
входящих во множества
A, B,...
можно
сформулировать некоторые
утверждения
, или высказывания. Обычно утверждения
касаются отношений между элементами множеств.
Отношением
R
из
A
в
B
называют любое подмножество из
A
×
B
и обозначают
(a, b)
∈
R
или
aRb
. В
утверждениях, выраженных в отношениях, символ
R
называют
оператором
,
множество элементов, входящих в
A,
именуют
операндами
,
A
-
областью
определения
отношения, а
B
–
областью значений
. Операцию с одним операндом
считают унарной операцией (
aR, Rb
)
,
с двумя – бинарной, с
n
– n-арной или n-
местной (
aRb
1
Rb
2
…).
Операции на множествах
С точки зрения отношений данные могут быть по-разному организованы.
Элементарные отношения между элементами множеств описываются
операциями на множествах
. К таким операциям относятся объединение (
!
),
пересечение (
"
), дополнение (
~
), разность (
-
). Объединением
A
!
B
называется
множество, содержащее все элементы из
A
вместе со всеми элементами из
B.
Пересечением
A
"
B
называется множество, содержащее только элементы,
принадлежащие обоим множествам. Дополнением
~ A
называется множество тех
элементов
B,
которые не содержатся в
A.
Разностью
A
-
B
называется множество тех
элементов
A,
которые не содержатся в
B.
Такие операции обычно иллюстрируются
диаграммами Д. Венна. Так, операции на определенных выше множествах
A
и
B
в
WORLDINFO
дают следующие результаты:
A
!
B = { Microsoft, 1975, Балмер, Apple, Джобс },
A
"
B = { 1975 },
~A = { IBM, 1911, Герстнер, Motorola, 1928, Фишер, Intel, 1967, Гроув, Apple,
Джобс },
A - B = { Microsoft, Балмер }
и иллюстрируются следующими диаграммами:
74
Операции объединения и пересечения множеств относятся к классу
ассоциативных отношений
. Множества, на которых определены такие операции,
именуются
группами,
тогда как множества, элементы которых не вступают в
ассоциативные отношения, называют
объектами
. Каждый объект автономен в том
смысле, что он не делит своих элементов с другими объектами и не использует
элементы других объектов.
Типы и классы
Различные объекты могут содержать элементы одинаковых типов. Тип - это
именованный разряд сходных элементов, подобных по состоянию и поведению. В
информатике говорят о
типе данных
, подразумевая под ним общий физический
признак элементов множества, существенный с точки зрения их представления в
памяти компьютера в виде данных. Цель описания типа и отнесения данных к
определенному типу состоит в том, чтобы зафиксировать размер выделяемой
памяти, способ представление данных в памяти и средства их обработки, и тем
самым связать множество с реальным компьютером. Тип
фиксирует область
определения, область допустимых значений элементов множества и область
применимых к ним отношений. Примеры типов данных:
1911, 1975
-
целые числа
(размер памяти 2 байта);
Apple, Microsoft
-
текст
(размер 5 - 9 байт).
75
Наличие общих типов элементов способствует образованию
систем,
то есть
организованных множеств
, которые характеризуются состояниями, переходами и
взаимодействием элементов
.
Всякая информационная система представляет собой
организованное множество. Упорядоченное множество называют организованным,
если:
o оно состоит из объектов, имеющих идентичные порядки и характеры
взаимодействия элементов определенных типов;
o оно может без ограничений дополняться объектами с той же организацией
элементов;
o из него могут удаляться объекты вплоть до полного опустошения
множества.
Подобно тому, как элементы объекта принадлежат к ограниченному числу
типов, объекты организованного множества оформляются в ограниченное число
классов.
Класс
- это именованный разряд сходных объектов, подобных с точки
зрения их организации. Класс можно отождествить с составным типом данных, с
шаблоном или каркасом объектов, описывающим их
компоненты
, то есть строение
и поведение безотносительно к содержанию.
Состав класса характеризуется его структурой.
Структура -
это статическая
схема класса, представляющая порядок элементов в его объектах перечнем
полей
-
однотипных, неделимых именованных разделов класса. Взаимодействие элементов
класса внутри объектов характеризуется методами.
Методы
представляют
динамическую модель класса, описывая взаимное поведение элементов и их
реакции на внешние по отношению к классу
события
. Пример класса:
Поле Тип данных
Фирма Текст
Год основания Целое число
Президент Текст
Имя:
WORLDINFO
.
Структура : (см. таблицу)
Методы: Создание компьютеров.
Логические отношения
Утверждения относительно элементов множества, рассматриваемые в
контексте их содержания (семантики, смысла) как истинные (1,
Да, True
) или
ложные (0,
Нет, False
), образуют категорию
отношений двоичной логики
. Примеры
истинных высказываний:
Microsoft - фирма, Балмер - президент,
примеры ложных:
IBM
-
президент
,
Фишер
-
фирма
.
76
Двоичная логика оперирует элементарными отношениями с операторами
логического умножения, или
конъюнкции
(
И, And,
•
), логического сложения, или
дизъюнкции
(
ИЛИ, Or, +
),
отрицания
(
НЕ, Not, ~
),
исключающего ИЛИ (Xor,
⊗
),
эквивалентности
(
Eqv,
≡
),
импликации
(
Imp,
→
). Самые простые отношения
определяются аксиомами двоичной логики:
x y x And y x Or y Not x x Xor y x Eqv y x Imp y
1 1 1 1 0 0 1 1
1 0 0 1 0 1 0 0
0 1 0 1 1 1 0 1
0 0 0 0 1 0 1 1
Наивысший приоритет имеет отрицание, за ним следуют конъюнкция,
дизъюнкция, импликация, эквивалентность.
Импликативное выражение “
x Imp y
” часто заменяют терминами “
Not x Or
y
”, “
x влечет y
”
, “если x то y
”, “
x только тогда, когда y
”, “
x – достаточное условие
для y
”, “
y – необходимое условие для x
”.
Приоритет
, или предшествование,
отношений определяет порядок их выполнения.
Математическая логика не ограничивается двоичными отношениями.
Широко распространены так называемые многозначные или гибкие логики,
оперирующие высказываниями типа «ни истинно, ни ложно», «истинно и ложно»
или «неопределенно». В любой математической логике утверждения, содержащие
переменные и принимающие в зависимости от них значения истины или лжи,
называются
предикатами
. Отношение
R
, которое выражает предикат, может быть
присуще всем переменным
a
множества
A
или только некоторым из них.
Принадлежность всем переменным обозначается квантором всеобщности ∀, а
принадлежность некоторым переменным – квантором существования ∃:
∀(
a
i
) (
R1
),
a
i
∈
A
∃(
a
j
) (
R2
),
a
j
∈
A1, A1
⊂
A
Важный класс логических отношений образуют
отношения
эквивалентности
, которые бывают рефлексивными, если
aRa
для всех
a
из
A
;
симметричными, если
aRb
влечет
bRa
для
a
и
b
из
A
; транзитивными, если
aRb
и
bRc
влекут
aRc
для
a, b, c
из
A
.
Функциональное исчисление
К особой категории отношений относятся
отображения
. Отображением,
или
функцией
, называют отношение зависимости элементов множеств. Если
обратиться к множествам
A
и
B
, в которых каждому элементу
a
∈
A
соответствует
элемент
b
∈
B
, то функцию обозначают
(a, b)
"
f
или
f: A
→
B
. Функциональное
отношение элементов множеств строится по правилам функционального
77
исчисления. Однозначное соответствие элементов обозначается
b = f(a)
. Множество
A
, инициализирующее функцию
f
, именуется областью определения функции. Оно
состоит из
аргументов,
или
параметров.
Множество
B
называется областью
значений функции
f
. Если область определения ограничена логическими
константами {1,0}, то соответствующий предикат имену ют
логической функцией
с
областью определения
n
и областью значений 2
n
, где
n
- число аргументов.
Логические функции являются предметом рассмотрения предложенной Г.
Лейбницем и Д. Булем
алгебры логики
, то есть математической системы,
использующей переменные, принимающие значения 0 и 1. В основе ее лежат
четырех аксиомы, называемые законами двоичной логики:
o Закон тождества:
x = x
(любое выражение эквивалентно самому себе).
o Закон дво йного отрицания:
x = Not Not x
(утверждение эквивалентно его
двойному отрицанию).
o Закон исключенного третьего:
x Or Not x
(любое высказывание либо
истинно, либо ложно).
o Закон противоречия:
Not (x And Not x)
(высказывание не может быть
одновременно и истинным, и ложным).
На первичных аксиомах логики строятся другие ее законы:
o Ассоциативный закон: (x Or y) Or z = x Or (y Or z) = x Or y Or z;
o (x And y) And z = x And (y And z) = x And y And z.
o Коммутативный закон: x Or y = y Or x, x And y = y And x.
o Дистрибутивный закон: (x And y) Or z = (x And z) Or (y Or z);
o x And (y Or z) = (x Or y) And (x And z).
o x And 0 = 0; x Or 0 = x.
o x Or Not x = 1, x And Not x = 0.
Из законов выводятся теоремы алгебры логики:
o Not 0 = 1; Not 1 = 0.
o x Or 0 = x; x And 1 = x; x Or 1 = 1.
o Теорема идемпотентности: x Or x = x, x And x = x.
o Теорема поглощения: x Or (x And y) = x, x And (x Or y) = x.
o Теорема де Моргана: Not(x Or y) = Not x And y, Not(x And y) = Not x Or
Not y.
Пример булева выражения, составленного с помощью логических
переменных:
F(x, y, z) = (x Or Not y) And (x Or z) And Not(y And z).
Обычно логические функции задаются таблицами истинности. В частности,
в предложенной функции
F
три аргумента (
n = 3),
поэтому для построения таблицы
следует вычислить значения восьми выражений:
78
x y z x Or Not y x Or z Not (y And z) F(x, y, z)
0 0 0 1 0 1 0
0 0 1 1 1 1 1
0 1 0 0 0 1 0
0 1 1 0 1 0 0
1 0 0 1 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 0 1 1 0 0
В свою очередь, от заданной таблицы истинности можно вернуться к булеву
выражению. Для этого элементы строк таблицы, имеющих единичное значение
функции, соединяются конъюнкцией, причем нулевые переменные инвертируются
и результаты конъюнкции соединяются дизъюнкцией:
F(x, y, z) = (Not x And Not y And z) Or (x And Not y And Not z) Or
(x And Not y And z) Or (x And y And Not z)
Затем производится упрощение полученных выражений на основании
аксиом и теорем алгебры логики. В ходе преобразования логические утверждения
считаются эквивалентными, если они имеют одинаковые таблицы истинности. Как
правило, целью преобразований является приведение логических утверждений к
упрощенному или удобному в реализации виду с использованием полного
множества логических операторов. В свою очередь, множество операторов
считается полным, если любому логическому утверждению можно подобрать
эквивалентное утверждение, содержащее только операторы из этого множества.
Полными являются множества
{And, Not}, {Or, Not}.
Примеры преобразований:
F = Not x And Not y Or x And Not y Or x And y Or x And z = x Or Not y Or z,
F = x And y Or y And z Or Not x And z = x And y Or Not x And z.
4.2.2. Реляционная модель данных
Работа высшего, что есть в человеке –
рассудка – сводится к непрерывному
ограничению бесконечности, к раздроблению
бесконечности на удобные, легко
перевариваемые порции.
Е. Замятин. «Мы»
Модели данных
В ходе развития информационных систем были сформулированы принципы
организации больших массивов данных:
o принцип интеграции данных, в соответствии с которым для хранения
информации целесообразно образовывать централизованную динамически
обновляемую модель предметной области,
79
o принцип независимости прикладных программ от данных, т.е. отделения
логической модели данных от средств управления ими.
Удовлетворение этим принципам связано с выделением единого для всех
задач блока данных, называемого
базой данных
и разработкой единой управляющей
программы для манипулирования данными, называемой
системой управления
базами данных - СУБД
.
Информация базы данных организуется и обрабатывается в накопителях в
соответствии с определенными правилами хранения и доступа. Логическая, а часто
и физическая автономность данных является первым существенным отличием баз
данных от прочего программного обеспечения. Строго оговоренная
принадлежность данных к определенным классам и их безусловная типизация
отличает базу данных от текстовых и табличных процессоров, а широкая гамма
допустимых операций над множествами является важным преимуществом ее перед
пакетами прикладных программ и системами программирования. Выделение базы
данных как особой части программного обеспечения способствует:
o эффективной структуризации информации;
o сведению к минимум у повторяющихся данных;
o ускорению обработки информации прямо на носителе;
o удобству обновления документов;
o обеспечению целостности данных;
o регулированию прав доступа к информации;
o облегчению автоматизации обработки данных и ведения отчетности.
Объекты предметной области базы данных называют
сущностями
и
оформляют в базах данных объектами определенной структуры. Отношения между
элементами записей характеризуются связями, которые могут быть парными и
многомерными. Характер связи определяет
модель данных
, описывающую
предметную область средствами языка, математической и логической символики.
Различают иерархическую, сетевую и реляционную модели данных.
Иерархическая модель отражает структуру связей между сущностями в виде
дерева с
узлами
, в которых хранятся данные, и
ветвями
, связывающими их между
собой. Узел, в который не входит ни одна ветвь, называется
корнем
. В свою
очередь, любой узел дерева - это в то же время и корень поддерева. Число таких
поддеревьев именуется степенью узла. Концевой узел, имеющий нулевую степень,
называется
листом
. Таким образом, объекты, описываемые иерархической
моделью, должны удовлетворять определенным ограничениям.
Если же эти ограничения убрать, получится
сетевая модель,
объектами
которой являются и записи, и связи между ними. Сетевая модель представлена
обширным множеством систем, среди которых наиболее развитой считается
стандарт на архитектуру и языковый интерфейс CODASYL (CODaSyL - Conference
On Data System Languages). Согласно этому стандарту, между объектами базы
данных устанавливаются отношения наследования типа «родитель-потомок»,
80
причем любой компонент может оказаться потомком нескольких «родителей» и
наоборот. Связи в базе данных сетевого типа реализуются с использованием
системы указателей. Поскольку каждый компонент данных должен содержать
ссылки на другие компоненты, такая модель требует значительных ресурсов памяти
и высокого быстродействия компьютера. В настоящее время ведутся исследования
в области создания объектно-ориентированных сетевых баз данных,
финансируемые такими компаниями, как IBM в США, Франгоферовский институт
программного обеспечения и системотехники в ФРГ и др. Примером коммерческой
сетевой базы данных для персональных компьютеров является DB-Vista (Century
Software), а для больших ЭВМ - IDMS.
Реляционная модель
Идея автоматизированной реляционной, или табличной, организации
данных принадлежит польскому математику З.Я.Слонимскому, в 1845 г.
удостоенному Демидовской премии Петербургской академии наук за изобретение
математической машины, использующей таблицы с определенными правилами
считывания. До него многочисленные таблицы - арифметические,
тригонометрические, логарифмические - были широко распространены в Европе
еще в 17-18 веках и применялись в навигации, астрономии, банковском деле,
архитектуре. Эти таблицы постоянно дополнялись, перепроверялись, и каждое
переиздание их требовало труда множества специалистов и содержало ошибки,
неизбежные при ручных расчетах и переписывании. Концепция реляционной
модели была разработана Э.Ф. Коддом в 70-х годах нашего века.
Таблица представляет собой множество, состоящее из объектов одного
класса. Сведения о каждом объекте представляется в таблице в виде отдельной
записи,
каждый элемент которой размещен в своем поле. Запись, состоящую из
элементов одного типа, называют
массивом
данных, или вектором, кортежем.
Символьный массив принято именовать
строкой
. В свою очередь, таблица
однотипных записей представляет собой двухмерный массив, а числовая таблица -
матрицу
. Число полей в таблице характеризует ее степень, число записей -
мощность, а их произведение -
размер
таблицы, то есть общее число ее элементов.
В приведенном здесь примере степень таблицы равна трем, мощность двум, а
размер шести.
Фирма Год Президент
Microsoft 1975 Балмер
Apple 1975 Джобс
Сравнительная простота инструментальных средств поддержки
реляционной модели является ее достоинством. Но поведение объектов
реляционная таблица не описывает, поэтому методы обработки данных относятся к
компетенции СУБД, а не базы данных. Отсутствующие функций обработки данных,
их анализа и синтеза перекладываются на такие инструменты, как табличные
процессоры, графические программы и специализированные пакеты прикладных