Структуры данных

При любом методе отображения предметной области в машин­ных базах данных в основе отображения лежит фиксация (кодиро­вание) понятий и отношений между понятиями.

Абстрактное по­нятие структуры ближе всего к так называемой концептуальной модели предметной области.

Это понятие используется на всех уровнях отображения предметной области и реализуется как:

1. структура информации - схематичная форма представле­ния сложных композиционных объектов и связей реальной предметной области, выделяемых как актуально необходи­мые для решения прикладных задач;

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

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

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

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

Для представления объектов предметной области используются три понятия структур:

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

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

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

Эффективность в этом случае связывается с процессом по­строения программы («решателя» прикладной задачи) и, в ка­ком-то смысле - с эффективностью работы программиста.

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

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

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

Классификация структур данных должна проводиться с двух точек зрения.

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

2. По характеру информации, представляемой структурой - на однородные структуры, где все элементы находятся на одном понятийном уровне и имеют один тип данных, и неодно­родные (композиционные), где элементы относятся к несколь­ким понятийным уровням или имеют разную природу.