Cтраница 2
Несколько хитроумных способов использования согласования параметров было предложено Тернлундом на семинаре по логическому программированию, состоявшемуся в Имперском колледже в 1976 г. Некоторые из них основаны на искусном употреблении списка различий в представлении структур данных, применявшегося в программе присоед из разд. [16]
Поскольку наш преемник мыслится как универсальный язык программирования, он должен обладать общими структурами данных. Как следует организовать это представление структур данных. Посмотрим, что было сделано в уже имеющихся языках. [17]
Она включает описание всех сущностей и первичных ключей и предназначена для представления структуры данных и ключей, которые соответствуют предметной области. [18]
В качестве примера рассмотрим интерфейс типа данных для точек ( [ триграмма 3.1) из раздела 3.1. В этом интерфейсе янно объявляется h что точки представлены как структуры, состоящие из лари чисел с плавающей точкой, обозначаемых х и у. В сч-мон пйлст подобное применение типов данных якляетсм обычным д ба шшнх системах программного обеспечения: мы разрабатываем набор дравид относительно ТОЕХ, как должки бить предстнвлеЕШ данные а также определяем рнл снн акныч с ними оиерацнй) ъ и делаем эти правила доступными через интерфейс, чтобы ими могли пользоваться клиентские программ ыч формирующие большую систему, Тип днинык обеспечивает согласованность всех частей системы с представлением основных обше-системных структур данных. Какой Бы хорошей такая стратегии ни была, она имеет один изъян: если необходимо uiwewumb пред ста плен и t данных, то потребуется изменить и все клиентские программы. Программа 3.3 снова даст нам простой пример: одна из причин разработки этого типа данных - сделать так, чтобы клиентским программам было удобно манипулировать с точками, и ми ожидаем что b случае необходимости у клиентов будет доступ к отдельным коорйннйтзм точки, Но мы не можем перейти к другому представлению даннш ( скаж мч к молярным координатам, или эрЕХыерным координатам или даже к: другим типам лцнаэых для отдельных ко-ординаг) без изменения все KJIH HI KHK лрохрамм. [19]
Современная концепция представления базы данных заключается во введении между физическим уровнем представления данных и внешним уровнем представления данных пользователем ( логическим уровнем) еще одного промежуточного уровня - концептуальной схемы базы данных. При этом один из указанных выше способов представления структур данных на концептуальном уровне и определяет тип СУБД в целом. Концептуальный уровень характеризует обобщенное представление всех внешних моделей пользователей. [20]
В качестве примера рассмотрим интерфейс типа данных для точек ( программа 3.3) из раздела 3.1. В этом интерфейсе явно объявляется, что точки представлены как структуры, состоящие из пары чисел с плавающей точкой, обозначаемых х и у. В самом деле, подобное применение типов данных является обычным в больших системах программного обеспечения: мы разрабатываем набор правил относительно того, как должны быть представлены данные ( а также определяем ряд связанных с ними операций), и делаем эти правила доступными через интерфейс, чтобы ими могли пользоваться клиентские программы, формирующие большую систему. Тип данных обеспечивает согласованность всех частей системы с представлением основных общесистемных структур данных. Какой бы хорошей такая стратегия ни была, она имеет один изъян: если необходимо изменить представление данных, то потребуется изменить и все клиентские программы. Программа 3.3 снова дает нам простой пример: одна из причин разработки этого типа данных - сделать так, чтобы клиентским программам было удобно манипулировать с точками, и мы ожидаем, что в случае необходимости у клиентов будет доступ к отдельным координатам точки. [21]
Наиболее очевидная цель деклараций состоит в том, чтобы указать свойства структур данных, остающиеся неизменными во время выполнения программы, например такие, как размер, форма и тип элементов массива. Получив из декларации эту информацию, транслятор может оптимизировать представление структур данных в памяти и уменьшить количество вычислений, необходимых для доступа к ним. [22]
Однако, такого рода рассуждения уводят нас к свойствам языков программирования, компиляторов, компоновщиков, сред выполнения программ, что весьма далеко от алгоритмов. Поэтому, чаще всего будем придерживаться простого, общепринятого разделения программы на два файла, где АТД реализуется в виде классов C, общедоступные функции-члены составляют интерфейс, а реализация объединяется с интерфейсом в отдельном файле, который включается в программы-клиенты и компилируется каждый раз, когда компилируются клиентские программы. Первопричина связана с тем, что реализация в виде класса - это удобное и компактное средство представления структур данных и алгоритмов. Если для какого-либо отдельного приложения потребуется большая гибкость, которая может быть обеспечена одним из только что упомянутых способов, можно соответствующим образом изменить структуры классов. [23]
Диапазон возможностей внутренних ограничений весьма узок. Их наличие может привести к структуризации базы данных, не полностью согласующейся с концепцией семантического описания реального мира. Например, не все типы связи функциональны или соответствуют древовидной структуре: тем не менее иерархическая модель требует именно древовидного представления структуры данных. [24]
Обсудим преимущества предлагаемого приема. Во-первых, адресный полином заменяется более простой суммой произведений. Во-вторых, число элементов в новом уравнении возрастает линейно в соответствии с ростом размерности массива. В-четвертых, наличие обобщенной формы представления структуры данных в виде блока описания массива позволяет резервировать память динамически во время работы программы. Читатели, знакомые с Алголом, обнаружат в последнем пункте важный атрибут языка с блочной структурой, позволяющего использовать переменные значения размерностей массивов. На практике изменяемая размерность массива и динамическое резервирование места для него позволяют программисту более эффективно использовать ограниченный объем памяти небольшой вычислительной машины. [25]
Множества процедур, представляющие структурированные данные, обладают интересным и иногда полезным свойством: из них можно образовывать другие возможные представления. Так, например, из представления списка 2 логически следует представление списка 1, и первое из них можно было бы снабдить такими инструкциями, используя соответствующие управляющие директивы, которые позволили бы получить на выходе второе представление. В этом контексте представление списка 2 вело бы себя подобно обычному множеству процедур, порождающему выходные данные. Такая способность логических утверждений одновременно выполнять функции как обычных процедур, так и представлений структур данных показывает, что всякое предполагаемое различие между процедурами и данными носит в сущности прагматический характер, и касается оно лишь использования этих ресурсов, а не присущих им атрибутов. [26]
Большинство из них были рассчитаны на специальные приложения, и поэтому программиста заранее ставили в определенные ограничительные рамки. Основная цель разработки системы управления базой данных заключается в обеспечении независимости данных, которая позволит ослабить ограничения, накладываемые на систему программирования. Форма представления структур данных в ЭВМ зависит от предполагаемого использования данных; в самом деле, не существует разных структур данных, для которых все операции со структурой одинаково эффективны. Основное различие заключается в том, как адресуются элементы структуры данных в памяти - по месту или по содержимому. В первом случае указываются логические или физические адреса данных, определяющие место данных в физической памяти. Однако уже в самой организации ассоциативной памяти предполагается упорядочение ячеек памяти. [27]
Если имеется одномерный массив, то, из каких бы элементов он ни состоял, его можно рассматривать как упорядоченный по возрастанию или убыванию индекса. Если мы расположим на бумаге двумерный массив А ( / /), то / будет представлять номер строки, а / - номер столбца. Если мы попытаемся двумерный массив представить в виде одномерного, то мы должны будем определить порядок строк или порядок столбцов, в соответствии с которым и будут располагаться элементы. В случае представления структуры данных в адресном пространстве обычно вводятся вполне определенные соглашения о расположении элементов. [28]
Обработка на ЭВМ данных реального мира требует, чтобы их структура была определена и точно представлена в ЭВМ. Структуры данных определяют семантику данных, а также способы организации и управления данными. Для того чтобы человек мог задать структуру данных, необходимо иметь четкие средства описания данных. В качестве математических средств в данном случае становится необходимым применение таких понятий, как множество, отношение, а также ряда других понятий логики. В этой главе рассматриваются различные аспекты, касающиеся вопросов представления структур данных в ЭВМ. [29]
Как указывалось ранее, возникают важные преимущества, когда структура данных во время исполнения программы проявляет близкое соответствие с представляющей ее концептуальной структурой данных программы. Ориентированный граф - полезная концептуальная модель, которая верна для большинства структур данных в программах; большинство программ ( особенно системно-ориентированные программы) широко используют структуры данных типа ориентированных графов. Тем не менее лишь некоторые существующие в настоящее время архитектуры ЭВМ предоставляют существенную поддержку модели структур данных программы в виде ориентированного графа. Обычно считается, что это задача программиста - отобразить его топологически сложные структуры данных на относительно простые структуры обычных архитектур ЭВМ. Архитектура системы 1432 предоставляет пользователю аппаратную, программно-аппаратную и программную поддержку модели ориентированного графа для структур данных программы. Это достигается путем представления структур данных во время исполнения в виде набора независимых адресных пространств, называемых объектами. Соответствие между моделью данных в виде ориентированного графа и моделью во время исполнения в виде набора объектов представляется следующим образом: узел ориентированного графа соответствует объекту, а дуга ориентированного графа соответствует ссылке или указателю на объект. [30]