Файл: Тема Введение в теорию баз данных Вопрос Основные понятия.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.02.2024
Просмотров: 170
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
надежных программ обработки.
Пользователь, используя ограниченное множество формальных, но достаточно знакомых понятий, выделяя сущности и связи, описывает объекты и связи предметной области;
Программист (или система автоматизации проектирования БД), используя такие типовые абстрактные понятия (как например числа, множества,
последовательности, агрегаты), определяет соответствующие информационные структуры.
Система управления данными, используя двоичные формы представления типизированных данных, обеспечивает эффективные процедуры хранения и обработки данных.
Именно введение промежуточногоуровня абстракции позволяет иметь раздельное описание логического и физического представления, освобождает конечного пользователя от необходимости беспокоиться о деталях внутримашинного представления и обработки, поскольку он может быть уверен, что программистом выбрана наиболее эффективная форма для данной ситуации. Однако эффективность здесь имеет определенные пределы. Чем ближе система абстракций к особенностям вычислительной среды, тем выше эффективность выполнения программы, но вынужденная «специализация»
абстракций увеличивает вероятность того, что они станут неподходящими для некоторых других применений.
Модель данных должна, так или иначе, дать основу для описания данных и манипулирования данными, а также дать средства анализа и синтеза структур данных.
Необходимо отметить, что предметные среды с точки зрения описания целесообразно условно разделить на два полярных случая:
1.
Предметная среда характеризуется сравнительно небольшим количеством типов отношений, но каждое отношение само есть большое множество.
Эти отношения сравнительно устойчивы, а изменений в пределах каждого множества существенно меньше мощности самого отношения. Например,
отношение «вхождения» элементов изделий, содержащееся в конструкторских спецификациях, для среднего предприятия содержит сотни тысяч записей. В
этом случае, задав схемы отношений и ориентировочные значения их мощностей, можно достаточно полно представить структуру и масштаб предметной среды.
2.
Для предметной среды характерно большое число типов отношений между объектами, но каждое отношение есть множество сравнительно малой мощности.
При этом мощность потока изменений для отношений сравнима с мощностью самих отношений.
Первый случай характерен для отображения процессов на уровне автоматизированных систем управления предприятиями. Современные системы управления базами данных наиболее эффективны именно в подобном случае, при отображении статических в указанном смысле предметных сред. Обычно при этом речь идет о целых классах объектов, например, о деталях данного типа и обычно не отображается состояние каждой конкретной детали.
Второй случай характерен для описания производственного технологического процесса, с учетом временных и пространственных факторов нахождения конкретных объектов.
Если в первом случае говорят о реляционной, иерархической или сетевой моделях данных, то во втором - о семантических сетях и фреймах.
Основное отличие этих методов заключается в том, что первые задают четкую схему (так называемую схему базы данных), в рамках которой и отображается предметная область.
Подобное построение по сути своей является довольно статичным, требует априорного знания типов отношений, в которых может находиться объект,
однако зафиксированная схема базы данных позволяет довольно эффективно организовать поиск необходимой информации.
Во втором случае предметная среда отображается (по крайней мере, на уровне модели) в виде однородной сети, любые изменения которой, как по вводу новых классов объектов, так и новых типов отношений, не связаны с какими-либо структурными преобразованиями сети.
В силу большого количества типов отношений манипулирование подобной «элементарной» информацией достаточно затруднено, поэтому для данного случая характерно введение большого количества общих понятий (и соответствующих им отношений), что упрощает работу с таким представлением.
В контексте машинного представления модель данных может быть использована следующим образом:
·
как средство спецификации типов данных и их организации, разрешенных в конкретной БД;
·
как основа разработки общей методологии построения баз данных;
·
как основа минимизации влияния эволюции баз данных на уже существующие прикладные программы и работу конечных пользователей;
·
как основа разработки семейства языков запросов и языков манипулирования данных;
·
как основа архитектуры СУБД;
·
как основа изучения динамических свойств различных организаций данных.
Таким образом, модель данных - это базовый инструментарий, обеспечивающий на формальном абстрактном уровне конкретные способы представления объектов и связей.
Модель базы данных охватывает более широкий спектр понятий.
Основное назначение модели базы данных состоит в том, чтобы:
·
определить ясную границу между логическим и физическим аспектами управления базой данных (независимость данных);
·
обеспечить конечным пользователям и программистам, создающим БД, возможность и средства общего понимания смысла данных
(коммуникабельность);
·
определить языковые понятия высокого уровня, обеспечивающие возможность выполнения однотипных операций над большими совокупностями записей (в общем случае разнотипных данных) как единую операцию (обработка множеств).
Вопрос 5. Структуры данных (линейные, нелинейные, сетевые).
[9]
Абстрактное понятие структурыближе всего находится к так называемой концептуальной модели предметной среды и часто лежит в основе последней.
Понятие структуры используется на всех уровнях представления предметной области и реализуется как:
·
структура информации - схематичная форма представления сложных композиционных объектов и связей реальной ПрО, выделяемых как актуально необходимые для решения прикладных задач;
·
структура данных - атрибутивная форма представления свойств и связей ПрО, ориентированная на выражение описания данных средствами формальных языков (т.е. учитывающая возможности и ограничения конкретных средств с целью сведения описаний к стандартным типам и регулярным связям);
·
структура записей - целесообразная (учитывающая особенности физической среды) реализация способов хранения данных и организации доступа к ним как на уровне отдельных записей, так и их элементов (с целью определения основных и вспомогательных функциональных массивов, а также совокупности унифицированных процедур манипулирования данными).
Структура является общепринятым и удобным инструментом, одинаково эффективно используемым как на уровне сознания человека при работе с абстрактными понятиями, так и на уровне логики машинных алгоритмов.
Структура позволяет простыми способами свести многомерность содержательного описания к линейной последовательности записей. Именно это позволяет формализовать на общей понятийной основе взаимосвязь представлений информации в разных средах: обеспечить контролируемое сведение бесконечного разнообразия объектов и видов взаимосвязей реального мира к жестко детерминированному описанию - совокупности двоичных данных и машинно-ориентированных алгоритмов их обработки.
Выделение трех видов структур, относящихся к представлению объектов ПрО, имеет, в некотором смысле, принципиальный характер.
Структура информации - это неотъемлемое свойство информации (сведений, сигналов, воспринимаемых субъектом) о некоторой совокупности объектов предметной области, в контексте практической задачи (решаемой субъектом), в общем случае без учета того, будут ли для ее решения использованы средства программирования и вычислительные машины.
Структурирование информации осуществляется системным аналитиком и сводится к выделению операционных объектов и определению их характеристических свойств и взаимосвязей.
Структура данных - это определение информационных массивов (состава и взаимосвязей данных на логическом уровне, соответствующих характеру информации и видам соответствующих преобразований).
При определении структур данных необходимо:
·
установить состав массива,
·
определить оптимальную их взаимосвязь (и, соответственно, определить критерии и методы оценки эффективности),
Пример, выделение групп или агрегатов, имеющих иерархическую идентификацию. Эффективность в этом случае связывается с процессом построения программы («решателя» прикладной задачи) и, в каком-то смысле - с эффективностью работы программиста.
Пример, при функциональной обработке массива необходимо обращаться к отдельным элементам, в то время как в операциях присваивания или при записи массива в файл поэлементное обращении приведет к увеличению размера текста программы, а в ряде случаев - к увеличению времени выполнения.
Структура записей - это определение структуры физической памяти:
·
выделение,
·
освобождение,
·
защита областей физического носителя,
·
способы адресации и пересылки.
Эффективность в этом случае связывается с процессами обмена между устройствами оперативной и внешней памяти, искусственно вводимой для обеспечения функциональной эффективности отдельных операций (например, поиска по ключам) избыточностью данных,
Рассмотрим разновидности и типологию «компьютерных» логических структур данных с точки зрения особенности их организации.
Заметим, что мы не будем рассматривать простейшие типы, к которым относятся стандартные типы – целые и вещественные числа, логические переменные, символы. Их состав и структура определяется в основном набором встроенныхбазовых типов данных и операций, свойственных конкретному типу ЭВМ.
Итак, структура в первую очередь определяет алгоритм выборки отдельных элементов данных, но в то же время необходимо отметить, что она отражает и особенности «технологии» организации и обработки информации, свойственные человеку в его повседневной деятельности.
Физически понятию структура соответствует запись данных.
Запись - это упорядоченная в соответствии с характером взаимосвязей совокупность полей (элементов) данных, размещаемых в памяти в соответствии с их типом.
Память, отводимая для хранения значения элемента данных (поле данных), должна выбираться в соответствии с диапазоном значений, которые может иметь этот элемент. Поскольку для выполнения операции присвоения значения элементу данных (установление соответствующих битов в «0» или «1»)
необходимо сначала выделить память, для чего используются две схемы– статическая и динамическая. Для первой характерно выделение памяти до того,
как реально появляются значения (обычно на этапе трансляции программы); для второй – в тот момент, когда программа во время исполнения получает конкретное значение. Кроме того, характер данных (тип данных) определяет способ представления и, соответственно, некоторое множество стандартных операций (примитивов). Поле представляет собой минимальную адресуемую (идентифицируемую) часть памяти - единицу данных, на которую можно ссылаться при обращении к данным.
Итак, структура данных - это способ отображения значений в памяти:
·
размер области
·
порядок ее выделения (который и определит характер процедуры адресации/выборки).
Зачастую именно успешность структурирования данных определяет сложность процедур их обработки.
Классификация структур данных должна проводиться с двух точек зрения.
1)
с точки зрения порядка их размещения/выборки:
по характеру взаимосвязи элементов структуры виды структур можно разделить на
·
линейные
Пользователь, используя ограниченное множество формальных, но достаточно знакомых понятий, выделяя сущности и связи, описывает объекты и связи предметной области;
Программист (или система автоматизации проектирования БД), используя такие типовые абстрактные понятия (как например числа, множества,
последовательности, агрегаты), определяет соответствующие информационные структуры.
Система управления данными, используя двоичные формы представления типизированных данных, обеспечивает эффективные процедуры хранения и обработки данных.
Именно введение промежуточногоуровня абстракции позволяет иметь раздельное описание логического и физического представления, освобождает конечного пользователя от необходимости беспокоиться о деталях внутримашинного представления и обработки, поскольку он может быть уверен, что программистом выбрана наиболее эффективная форма для данной ситуации. Однако эффективность здесь имеет определенные пределы. Чем ближе система абстракций к особенностям вычислительной среды, тем выше эффективность выполнения программы, но вынужденная «специализация»
абстракций увеличивает вероятность того, что они станут неподходящими для некоторых других применений.
Модель данных должна, так или иначе, дать основу для описания данных и манипулирования данными, а также дать средства анализа и синтеза структур данных.
Необходимо отметить, что предметные среды с точки зрения описания целесообразно условно разделить на два полярных случая:
1.
Предметная среда характеризуется сравнительно небольшим количеством типов отношений, но каждое отношение само есть большое множество.
Эти отношения сравнительно устойчивы, а изменений в пределах каждого множества существенно меньше мощности самого отношения. Например,
отношение «вхождения» элементов изделий, содержащееся в конструкторских спецификациях, для среднего предприятия содержит сотни тысяч записей. В
этом случае, задав схемы отношений и ориентировочные значения их мощностей, можно достаточно полно представить структуру и масштаб предметной среды.
2.
Для предметной среды характерно большое число типов отношений между объектами, но каждое отношение есть множество сравнительно малой мощности.
При этом мощность потока изменений для отношений сравнима с мощностью самих отношений.
Первый случай характерен для отображения процессов на уровне автоматизированных систем управления предприятиями. Современные системы управления базами данных наиболее эффективны именно в подобном случае, при отображении статических в указанном смысле предметных сред. Обычно при этом речь идет о целых классах объектов, например, о деталях данного типа и обычно не отображается состояние каждой конкретной детали.
Второй случай характерен для описания производственного технологического процесса, с учетом временных и пространственных факторов нахождения конкретных объектов.
Если в первом случае говорят о реляционной, иерархической или сетевой моделях данных, то во втором - о семантических сетях и фреймах.
Основное отличие этих методов заключается в том, что первые задают четкую схему (так называемую схему базы данных), в рамках которой и отображается предметная область.
Подобное построение по сути своей является довольно статичным, требует априорного знания типов отношений, в которых может находиться объект,
однако зафиксированная схема базы данных позволяет довольно эффективно организовать поиск необходимой информации.
Во втором случае предметная среда отображается (по крайней мере, на уровне модели) в виде однородной сети, любые изменения которой, как по вводу новых классов объектов, так и новых типов отношений, не связаны с какими-либо структурными преобразованиями сети.
В силу большого количества типов отношений манипулирование подобной «элементарной» информацией достаточно затруднено, поэтому для данного случая характерно введение большого количества общих понятий (и соответствующих им отношений), что упрощает работу с таким представлением.
В контексте машинного представления модель данных может быть использована следующим образом:
·
как средство спецификации типов данных и их организации, разрешенных в конкретной БД;
·
как основа разработки общей методологии построения баз данных;
·
как основа минимизации влияния эволюции баз данных на уже существующие прикладные программы и работу конечных пользователей;
·
как основа разработки семейства языков запросов и языков манипулирования данных;
·
как основа архитектуры СУБД;
·
как основа изучения динамических свойств различных организаций данных.
Таким образом, модель данных - это базовый инструментарий, обеспечивающий на формальном абстрактном уровне конкретные способы представления объектов и связей.
Модель базы данных охватывает более широкий спектр понятий.
Основное назначение модели базы данных состоит в том, чтобы:
·
определить ясную границу между логическим и физическим аспектами управления базой данных (независимость данных);
·
обеспечить конечным пользователям и программистам, создающим БД, возможность и средства общего понимания смысла данных
(коммуникабельность);
·
определить языковые понятия высокого уровня, обеспечивающие возможность выполнения однотипных операций над большими совокупностями записей (в общем случае разнотипных данных) как единую операцию (обработка множеств).
Вопрос 5. Структуры данных (линейные, нелинейные, сетевые).
[9]
Абстрактное понятие структурыближе всего находится к так называемой концептуальной модели предметной среды и часто лежит в основе последней.
Понятие структуры используется на всех уровнях представления предметной области и реализуется как:
·
структура информации - схематичная форма представления сложных композиционных объектов и связей реальной ПрО, выделяемых как актуально необходимые для решения прикладных задач;
·
структура данных - атрибутивная форма представления свойств и связей ПрО, ориентированная на выражение описания данных средствами формальных языков (т.е. учитывающая возможности и ограничения конкретных средств с целью сведения описаний к стандартным типам и регулярным связям);
·
структура записей - целесообразная (учитывающая особенности физической среды) реализация способов хранения данных и организации доступа к ним как на уровне отдельных записей, так и их элементов (с целью определения основных и вспомогательных функциональных массивов, а также совокупности унифицированных процедур манипулирования данными).
Структура является общепринятым и удобным инструментом, одинаково эффективно используемым как на уровне сознания человека при работе с абстрактными понятиями, так и на уровне логики машинных алгоритмов.
Структура позволяет простыми способами свести многомерность содержательного описания к линейной последовательности записей. Именно это позволяет формализовать на общей понятийной основе взаимосвязь представлений информации в разных средах: обеспечить контролируемое сведение бесконечного разнообразия объектов и видов взаимосвязей реального мира к жестко детерминированному описанию - совокупности двоичных данных и машинно-ориентированных алгоритмов их обработки.
Выделение трех видов структур, относящихся к представлению объектов ПрО, имеет, в некотором смысле, принципиальный характер.
Структура информации - это неотъемлемое свойство информации (сведений, сигналов, воспринимаемых субъектом) о некоторой совокупности объектов предметной области, в контексте практической задачи (решаемой субъектом), в общем случае без учета того, будут ли для ее решения использованы средства программирования и вычислительные машины.
Структурирование информации осуществляется системным аналитиком и сводится к выделению операционных объектов и определению их характеристических свойств и взаимосвязей.
Структура данных - это определение информационных массивов (состава и взаимосвязей данных на логическом уровне, соответствующих характеру информации и видам соответствующих преобразований).
При определении структур данных необходимо:
·
установить состав массива,
·
определить оптимальную их взаимосвязь (и, соответственно, определить критерии и методы оценки эффективности),
Пример, выделение групп или агрегатов, имеющих иерархическую идентификацию. Эффективность в этом случае связывается с процессом построения программы («решателя» прикладной задачи) и, в каком-то смысле - с эффективностью работы программиста.
Пример, при функциональной обработке массива необходимо обращаться к отдельным элементам, в то время как в операциях присваивания или при записи массива в файл поэлементное обращении приведет к увеличению размера текста программы, а в ряде случаев - к увеличению времени выполнения.
Структура записей - это определение структуры физической памяти:
·
выделение,
·
освобождение,
·
защита областей физического носителя,
·
способы адресации и пересылки.
Эффективность в этом случае связывается с процессами обмена между устройствами оперативной и внешней памяти, искусственно вводимой для обеспечения функциональной эффективности отдельных операций (например, поиска по ключам) избыточностью данных,
Рассмотрим разновидности и типологию «компьютерных» логических структур данных с точки зрения особенности их организации.
Заметим, что мы не будем рассматривать простейшие типы, к которым относятся стандартные типы – целые и вещественные числа, логические переменные, символы. Их состав и структура определяется в основном набором встроенныхбазовых типов данных и операций, свойственных конкретному типу ЭВМ.
Итак, структура в первую очередь определяет алгоритм выборки отдельных элементов данных, но в то же время необходимо отметить, что она отражает и особенности «технологии» организации и обработки информации, свойственные человеку в его повседневной деятельности.
Физически понятию структура соответствует запись данных.
Запись - это упорядоченная в соответствии с характером взаимосвязей совокупность полей (элементов) данных, размещаемых в памяти в соответствии с их типом.
Память, отводимая для хранения значения элемента данных (поле данных), должна выбираться в соответствии с диапазоном значений, которые может иметь этот элемент. Поскольку для выполнения операции присвоения значения элементу данных (установление соответствующих битов в «0» или «1»)
необходимо сначала выделить память, для чего используются две схемы– статическая и динамическая. Для первой характерно выделение памяти до того,
как реально появляются значения (обычно на этапе трансляции программы); для второй – в тот момент, когда программа во время исполнения получает конкретное значение. Кроме того, характер данных (тип данных) определяет способ представления и, соответственно, некоторое множество стандартных операций (примитивов). Поле представляет собой минимальную адресуемую (идентифицируемую) часть памяти - единицу данных, на которую можно ссылаться при обращении к данным.
Итак, структура данных - это способ отображения значений в памяти:
·
размер области
·
порядок ее выделения (который и определит характер процедуры адресации/выборки).
Зачастую именно успешность структурирования данных определяет сложность процедур их обработки.
Классификация структур данных должна проводиться с двух точек зрения.
1)
с точки зрения порядка их размещения/выборки:
по характеру взаимосвязи элементов структуры виды структур можно разделить на
·
линейные