Средства для описания данных

Символы

Для дальнейшего понимания излагаемого материала введем некоторые правила обозначения категорий хранимых данных. Таблица 1

Уровень категорий	Представления реального мира	Абстрактные представления	Практическая реализация
		данные	символ	Хранимые данные	символ
Наибольший	Предметная область	Библиотека		База данных
	Подмножество приложений	Файл	a	Список	А
	Объект	Запись	аi	Ячейка	Ai
	Имя атрибута	Имя поля	aij	Элемент	Aij
Наименьший	Значение атрибута	Значение поля

Отношения положения

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

Содержимое ячейки. Ячейка содержит запись. Чтобы показать, какая именно запись находит­ся в определенной ячейке, используют скобки, которые эквива­лентны операции извлечения записи из ячейки. Например, запи­шем, что запись а содержится в ячейке А:

(А)=а. (4.1.1)

Местоположение записи. Обратная процедура: для данной записи найти содержащую ее ячейку. Эта операция запи­сывается с помощью квадратных скобок. Например, покажем, что запись а содержится в ячейке А:

[а]==А. (4.1.2)

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

b->D. (4.1.3)

Пересылка записи, находящейся в ячейке Е, в ячейку F пред­ставляется как

(E)->F. • (4.1.4)

Чтобы показать, что запись g заменит запись h в ячейке, кото­рую в данный момент занимает запись h, запишем:

g->[h]. (4.1.5)

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

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

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

Обозначим ключевое поле для записи либо для элемента в ячейке, где располагается данная запись, индексом К, Например, а_ik является значением ключевого поля для записи a_i. Оно нахо­дится в ячейке А = [a_i] в позиции А_ik == [а_ik].

Отношение порядка

Одним из наиболее важных свойств файла или списка являет­ся порядок, определяемый с использованием ключа каждой записи. Чтобы исследовать это свойство, разобьем значение ключа на образующие его литеры. Для этих литер, которые служат элемен­тарными единицами представления, определим отношение поряд­ка (или, как иногда говорят, последовательность упорядочений). То же отношение порядка должно сохраняться в коде представ­ления информации в ЭВМ.

Например, мы можем установить следующие неравенства меж­ду литерами алфавита:

0<1< А<В<С<... <Z... и т. д. (4.1.6)

Чтобы ЭВМ выполняла требуемые нам операции, мы должны код для литеры А выбрать меньшим кода для литеры В и т. д. Эти соотношения в ЭВМ представлены комбинациями двоичных чисел коды таблицы ASCII. Двоичное число, представляющее А, меньше числа, пред­ставляющего В, т. е.

Аº065₍₁₀₎ =0100001₍₂₎, Вº066₍₁₀₎= 0100010₍₂₎ 0100001₍₂₎ < 0100010₍₂₎, (4.1.4)

где знак º эквивалентен слову представляет.

Условие (4.1.6) удовлетворяется, если коды для десятичных цифр меньше кодов для букв. В результате 1 представляется шестнадцатеричной комбинацией 00011001, а Zº01011000₍₂₎. Таким образом,

Z=01011000₍₂₎, l=00011001₍₂₎, 00011001₍₂₎ <01011000₍₂₎. (4.1.8)

Ключевое поле образуется из нескольких литер. Оно может включать пробел, код которого равен 32₍₁₀₎.

Ранг записи

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

а_i < а_j º (а_{i k})< (а_jk) (4.1.10)

ОТНОШЕНИЯ

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

Отношение существует между двумя объектами. Обозначим эти объекты строчными буквами, например, а и b, а само отно­шение — буквой R. Тогда мы можем записать, что между а и b существует отношение R:

а R b. (4.2.1)

Например, R может выражать отношение “больше чем”. В этом случае формула (4.2.1) означает, что “а больше, чем b ”. Мы также можем ввести другие отношения, например “равно”, “предшествует”, “старше чем”.

Классификация отношений

Отношения можно разбить на: рефлексивные, симметричные и транзитивные.

Рефлексивные отношения. Говорят, что отношение рефлексивное, если оно устанавливается между одним и тем же объектом. Например,

a R a. (4.2.2)

Лишь немногие отношения являются рефлексивными. Так, отношение “равно” — рефлексивное, а отношение “старше чем” — нерефлексивное.

Симметричные отношения. Отношение считается симметричным, если оно применимо к элементам а и b при их рас­смотрении как в данном порядке, так и в обратном:

a R b & b R а. (4.2.3)

Отметим, что для большинства отношений (но не для симмет­ричных) важен порядок расположения элементов. Отношение “отличается от” является симметричным, так как два объекта отличаются друг от друга независимо от того, какой из них рас­полагается первым. Вместе с тем это нерефлексивное отношение, так как нельзя сказать о каком-либо объекте, что он отличается сам от себя.

Многие отношения являются несимметричными (асимметрич­ными). Простым примером может служить отношение “стар­ше чем”.

Транзитивные отношения. Представим транзитив­ное отношение в символической форме:

a R b & b R cÞ a R c. (4.2.4)

Отсюда следует, что отношение R является транзитивным, если оно, существуя между а и b и одновременно между b и с, сущест­вует между а и с. Так, если Катя старше Гали, а Галя стар­ше Изабеллы, то Катя старше Изабеллы.

На первый взгляд может показаться, что все отношения должны быть транзитивными. Однако это не так и примером тому может слу­жить отношение “не равно”. Подставьте в таком отношении вместо а - 6, вместо b 5, а вместо с – 6 и вы увидите, что отноше­ние “не равно” не является транзитивным (оно нетранзитивное), иначе вам придется признать, что 6 не равно 6.

Графы

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

Рис 4.1. Граф

Граф дает наглядное изображение, как объектов, так и отно­шений между ними. Более того, он позволяет рассматривать их в любой последовательности. Таким образом, граф обеспечивает способ представления без последовательного (во времени) про­смотра, присущего тексту,

Граф состоит из ряда вершин и ребер. Он должен содержать, по крайней мере, одну вершину. Ребро является отрезком прямой, вершина —точкой. Для каждого ребра также должна существо­вать вершина, которая его завершает. Пример графа показан на рис. 4.1.

Вершины графа представляют объекты, а ребра — отношения между этими объектами. Так как отношение существует между двумя объектами, естественно, что в графе каждое ребро имеет две терми­нальные вершины.

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

Направление

Выше уже обсуждались симмет­ричные отношения, такие, как “ра­вен”, “следующий”, “родной брат”. Эти отношения не опреде­ляют направления; они устанавливаются между элементами без указания на то, какой из них задается первым. Симметричные отношения легко представить с помощью рассмотренного только что графа. В данном случае ребро отображает симметричное от­ношение, а вершины — объекты, к которым это отношение приме­няется.

Асимметрия

Отношение называется асимметричным, если между а и b оно существует, а между b и а - нет. В качестве примера можно при­вести отношения “больше чем”, “отец”, “дядя”. Направление определяет, какой объект служит под­лежащим, а какой дополнением по от­ношению к глаголу, выражающему отношение. Здесь важно определить объект, который устанавливается пер­вым. Так, мы говорим, что Максим — отец Валеры, но обратное утвержде­ние неверно: Валера не отец Максима. Ребро графа не показывает, какой из объектов упоминается первым.

Орграф

Для указания подлежащего и дополнения ребру придается ориентация. Такое ребро в дальнейшем мы будем называть ду­гой. Дуга изображается в виде стрелки, направленной от подле­жащего к дополнению. Граф, в котором задана ориентация, на­зывается ориентированным графом или орграфом. В орграфе дуги по-прежнему связывают вершины (рис. 4.2),