Файл: 1. Введение в теорию баз данных Вопрос Основные понятия.docx
Добавлен: 07.12.2023
Просмотров: 819
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
записи - совокупности (группы)формализованных элементов данных(значений атрибутов, представленных в том или ином формате).
В общем случае объект может описываться совокупностью записей, относящихся к его составным частям или отражающих динамику изменения состояния. Кроме того, в контексте задач хранения и поиска можно говорить, что значение атрибута идентифицирует объект: использование значения в качестве поискового признака позволяет реализовать простой критерий отбора по условию сравнения.
Отметим, что некоторые семантические проблемы идентификации через значение атрибута. Значение атрибута идентифицирует запись о состоянии объекта, и в случае изменения значения, например – табельного номера служащего, будет невозможно ответить на вопрос: идет ли речь о том же служащем, или о новом.
Также как и в реальном мире, отдельный объект всегда уникален (уже хотя бы потому, что мы именно его выделяем среди других). Соответственно, запись, содержащая данные о нем, также должна быть узнаваема однозначно (по крайней мере, в рамках предметной области), т.е. - иметь уникальный идентификатор, причем никакой другой объект не должен иметь такой же идентификатор. Поскольку идентификатор - суть значение элемента данных, в некоторых случаях для обеспечения уникальности требуется использовать более одного элемента.
Например, для однозначной идентификации записей о дисциплинах учебного плана необходимо использовать элементы СЕМЕСТР и НАИМЕНОВАНИЕ ДИСЦИПЛИНЫ, так как одна дисциплина может быть прочитана в разных семестрах.
Предложенная выше схема представляет атрибутивный способ идентификации содержания объекта (см. рис. 11).
Рис. 11. Атрибутивный способ идентификации
Она является достаточно естественной для данных, имеющих фактографическую природу, и описывающих обычно материальные объекты. Информацию, представляемую такого рода данными, называют хорошо структурированной.
Здесь важно отметить, что структурированность относится не только к форме представления данных (формат, способ хранения), но и к способу интерпретации значения пользователем: значение параметра не только представлено в предопределенной форме, но и обычно сопровождается указанием размерности величины, что позволяет пользователю понимать ее смысл без дополнительных комментариев.
Таким образом, фактографические данные предполагают возможность их непосредственной интерпретации.
Однако атрибутивный способ практически не подходит для идентификации слабо структурированной информации, связанной с объектами, имеющими обычно идеальную (умозрительную) природу - категориями, понятиями, знаковыми системами. Такие объекты зачастую определяются логически и опосредованно - через другие объекты.
Для описания таких объектов используются естественные или искусственные языки (например, язык алгебры).
Соответственно, для понимания смысла пользователю необходимо использовать соответствующие правила языка, и, более того, часто необходимо уже располагать некоторой информацией, позволяющей идентифицировать и связать получаемую информацию с наличным знанием. Т.е., процесс интерпретации такого рода данных имеет опосредованныйхарактер и требует использования дополнительной информации, причем такой, которая не обязательно присутствует в формализованном виде в базе данных.
Такое разделение нашло отражение в традиционном разделении баз данных на фактографические и документальные.
Вопрос 3. Поиск записей.[7]
Программисту или пользователю необходимо иметь возможность обращаться к отдельным, нужным ему записям (описаниям объектов) или отдельным элементам данных.
В зависимости от уровня программного обеспечения прикладной программист может использовать следующие способы:
задать машинный адрес данных и в соответствии с физическим форматом записи прочитать значение (это случай, когда программист должен быть «навигатором»);
сообщить системе имя записи или элемента данных, которые он хочет получить, и, возможно, организацию набора данных.
В этом случае система сама произведет выборку (по предыдущей схеме), но для этого она должна будет использовать вспомогательную информацию о структуре данных и организации набора. Такая информация по существу будет избыточной по отношению к объекту, однако общение с базой данных не будет требовать от пользователя знаний программиста и позволит переложить заботы о размещении данных на систему.
В качестве ключа, обеспечивающего доступ к записи, можно использовать идентификатор - отдельный элемент данных.
Ключ, который идентифицирует запись единственным образом, называется
первичным (главным). В том случае, когда ключ идентифицирует некоторую группу записей, имеющих определенное общее свойство, ключ называется вторичным (альтернативным). Набор данных может иметь несколько вторичных ключей, необходимость введения которых определяется практической необходимостью - оптимизацией процессов нахождения записей по соответствующему ключу.
Иногда в качестве идентификатора используют составной сцепленный ключ - несколько элементов данных, которые в совокупности, например, обеспечат уникальность идентификации каждой записи набора данных. При этом ключ может храниться в составе записи или отдельно.
Например, ключ для записей, имеющих неуникальные значения атрибутов, для устранения избыточности может храниться отдельно.
На рис. 12 приведены два таких способа хранения ключей и атрибутов для набора простейшей структуры.
Рис. 12. Способы хранения ключа и атрибута
Введенное понятие ключа является логическим и его не следует путать с физической реализацией ключа - индексом, обеспечивающим доступ к записям, соответствующим отдельным значениям ключа.
Один из способов использования вторичного ключа в качестве входа - организация инвертированного списка, каждый вход которого содержит значение ключа вместе со списком идентификаторов соответствующих записей. Данные в индексе располагаются в возрастающем или убывающем порядке, поэтому алгоритм нахождения нужного значения довольно прост и эффективен, а после нахождения значения запись локализуется по указателю физического расположения. Недостатком индекса является то, что он занимает дополнительное пространство и его надо обновлять каждый раз, когда удаляется, обновляется или добавляется запись. На рис. 13 приведен инвертированный список для предыдущего примера.
Рис. 13. Инвертированный список для ключа «Марка автомобиля»
В общем случае инвертированный список может быть построен для любого ключа, в том числе, составного.
В контексте задач поиска можно сказать, что существуют два основных способа организации данных. Первый способ соответствует первому примеру и представляет прямую организацию массива. Второй способ является инверсией первого.
Прямая организация массива удобна для поиска по условию «Каковы свойства указанного объекта?», а инвертированная – для поиска по условию «Какие объекты обладают указанным свойством?».
Существует следующая типология простых (атомарных) запросов:
Здесь в запросах типов 2, 3, 6 вместо оператора равенства может быть использован другой оператор сравнения (больше, меньше, не равно или другие).
Запросы типа 1 выполняются поиском по «прямому» массиву: доступ к записи производится по первичному ключу.
Запросы типа 2 выполняются поиском по инвертированному списку: доступ к записи ( ям) производится по указателю, выбираемому из списка по значению вторичного ключа. Ответом в этих случаях будет значение атрибута или идентификатора.
Запросы типа 3 имеют ответом имя атрибута.
Запросы типа 2, 5, 6 относятся к нескольким атрибутам, и в этом случае могут быть построены несколько индексов, облегчающих поиск по этим ключам.
Составные условия поиска могут использовать несколько простых условий, обычно связанных логическими (булевыми) операторами.
Следует отметить, что в контексте обработки запросов 2-го типа «Какие объекты имеют заданное значение атрибута?» можно выделить три следующих типа архитектур доступа:
1. Системы с вторичными индексами.
В этих системах последовательность расположения записей соответствует последовательности значений первичного ключа. Как правило, используется один первичный индекс и несколько вторичных.
2. Системы частично инвертированных файлов.
В этих системах записи могут располагаться в произвольной последовательности. В отличие от систем первого типа первичный индекс отсутствует. Вторичные индексы применяются для прямой адресации записей, что существенно облегчает включение в файл новых записей, так как допускается их размещение в любом свободном участке файла.
3. Системы полностью инвертированных файлов.В этих системах предусмотрено наличие файлов, содержащих значения отдельных элементов данных, входящих в состав записей - допускается раздельное хранение элементов данных записи.
Значения элементов данных, составляющих конкретную запись или кортеж, в общем случае могут размещаться в памяти произвольно.
Для ускорения процесса поиска в системе используют два набора индексов: индекс экземпляров (значений ключей) и индекс данных (инвертированный список). С помощью индекса экземпляров можно найти в файле элементы данных, имеющих заданное значение. С помощью индекса данных можно найти записи, связанные с заданными значениями элементов. Такая организация характерна для организации данных документальных информационных систем.
Вопрос 4. Представление предметной области и модели данных.[8]
Если бы назначением базы данных было только хранение и поиск данных в массивах записей, то структура системы и самой базы была бы простой.
Причина сложности в том, что практически любой объект характеризуется не только параметрами-величинами, но и взаимосвязями частей или состояний.
Есть различия и в характере взаимосвязей между объектами предметной области:
одни объекты могут использоваться только как характеристики остальных объектов,
другие - независимы и имеют самостоятельное значение (рис. 14).
Рис. 14. Этапы преобразования представлений ПрО
Отдельный элемент данных (его значение) ничего не представляет. Он приобретает смысл только тогда, когда связан с атрибутом (природой значения, что позволит интерпретировать значение) и другими элементами данных. Поэтому физическому размещению данных (и, соответственно, определению структуры физической записи) должно предшествовать описание логической структуры предметной области - построение модели соответствующего фрагмента реального мира, выделяющей только те объекты, которые будут интересны будущим пользователям, и представленные только теми параметрами, которые будут значимы при решении прикладных задач. Такая модель будет иметь очень мало физического сходства с реальностью, но будет полезна как представлениепользователя о реальном мире. Причем это представление будет задаваться (описываться) удобными для пользователясредствами в не адекватной человеку жесткой вычислительной среде с двоичной логикой и числовым представлением информации.
Таким образом, прежде чем описывать физическую реализацию объектов и связей между ними, необходимо определить:
1) способ, с помощью которого внешние пользователи представляют (описывают) объекты и связи;
В общем случае объект может описываться совокупностью записей, относящихся к его составным частям или отражающих динамику изменения состояния. Кроме того, в контексте задач хранения и поиска можно говорить, что значение атрибута идентифицирует объект: использование значения в качестве поискового признака позволяет реализовать простой критерий отбора по условию сравнения.
Отметим, что некоторые семантические проблемы идентификации через значение атрибута. Значение атрибута идентифицирует запись о состоянии объекта, и в случае изменения значения, например – табельного номера служащего, будет невозможно ответить на вопрос: идет ли речь о том же служащем, или о новом.
Также как и в реальном мире, отдельный объект всегда уникален (уже хотя бы потому, что мы именно его выделяем среди других). Соответственно, запись, содержащая данные о нем, также должна быть узнаваема однозначно (по крайней мере, в рамках предметной области), т.е. - иметь уникальный идентификатор, причем никакой другой объект не должен иметь такой же идентификатор. Поскольку идентификатор - суть значение элемента данных, в некоторых случаях для обеспечения уникальности требуется использовать более одного элемента.
Например, для однозначной идентификации записей о дисциплинах учебного плана необходимо использовать элементы СЕМЕСТР и НАИМЕНОВАНИЕ ДИСЦИПЛИНЫ, так как одна дисциплина может быть прочитана в разных семестрах.
Предложенная выше схема представляет атрибутивный способ идентификации содержания объекта (см. рис. 11).
Рис. 11. Атрибутивный способ идентификации
Она является достаточно естественной для данных, имеющих фактографическую природу, и описывающих обычно материальные объекты. Информацию, представляемую такого рода данными, называют хорошо структурированной.
Здесь важно отметить, что структурированность относится не только к форме представления данных (формат, способ хранения), но и к способу интерпретации значения пользователем: значение параметра не только представлено в предопределенной форме, но и обычно сопровождается указанием размерности величины, что позволяет пользователю понимать ее смысл без дополнительных комментариев.
Таким образом, фактографические данные предполагают возможность их непосредственной интерпретации.
Однако атрибутивный способ практически не подходит для идентификации слабо структурированной информации, связанной с объектами, имеющими обычно идеальную (умозрительную) природу - категориями, понятиями, знаковыми системами. Такие объекты зачастую определяются логически и опосредованно - через другие объекты.
Для описания таких объектов используются естественные или искусственные языки (например, язык алгебры).
Соответственно, для понимания смысла пользователю необходимо использовать соответствующие правила языка, и, более того, часто необходимо уже располагать некоторой информацией, позволяющей идентифицировать и связать получаемую информацию с наличным знанием. Т.е., процесс интерпретации такого рода данных имеет опосредованныйхарактер и требует использования дополнительной информации, причем такой, которая не обязательно присутствует в формализованном виде в базе данных.
Такое разделение нашло отражение в традиционном разделении баз данных на фактографические и документальные.
Вопрос 3. Поиск записей.[7]
Программисту или пользователю необходимо иметь возможность обращаться к отдельным, нужным ему записям (описаниям объектов) или отдельным элементам данных.
В зависимости от уровня программного обеспечения прикладной программист может использовать следующие способы:
задать машинный адрес данных и в соответствии с физическим форматом записи прочитать значение (это случай, когда программист должен быть «навигатором»);
сообщить системе имя записи или элемента данных, которые он хочет получить, и, возможно, организацию набора данных.
В этом случае система сама произведет выборку (по предыдущей схеме), но для этого она должна будет использовать вспомогательную информацию о структуре данных и организации набора. Такая информация по существу будет избыточной по отношению к объекту, однако общение с базой данных не будет требовать от пользователя знаний программиста и позволит переложить заботы о размещении данных на систему.
В качестве ключа, обеспечивающего доступ к записи, можно использовать идентификатор - отдельный элемент данных.
Ключ, который идентифицирует запись единственным образом, называется
первичным (главным). В том случае, когда ключ идентифицирует некоторую группу записей, имеющих определенное общее свойство, ключ называется вторичным (альтернативным). Набор данных может иметь несколько вторичных ключей, необходимость введения которых определяется практической необходимостью - оптимизацией процессов нахождения записей по соответствующему ключу.
Иногда в качестве идентификатора используют составной сцепленный ключ - несколько элементов данных, которые в совокупности, например, обеспечат уникальность идентификации каждой записи набора данных. При этом ключ может храниться в составе записи или отдельно.
Например, ключ для записей, имеющих неуникальные значения атрибутов, для устранения избыточности может храниться отдельно.
На рис. 12 приведены два таких способа хранения ключей и атрибутов для набора простейшей структуры.
Рис. 12. Способы хранения ключа и атрибута
Введенное понятие ключа является логическим и его не следует путать с физической реализацией ключа - индексом, обеспечивающим доступ к записям, соответствующим отдельным значениям ключа.
Один из способов использования вторичного ключа в качестве входа - организация инвертированного списка, каждый вход которого содержит значение ключа вместе со списком идентификаторов соответствующих записей. Данные в индексе располагаются в возрастающем или убывающем порядке, поэтому алгоритм нахождения нужного значения довольно прост и эффективен, а после нахождения значения запись локализуется по указателю физического расположения. Недостатком индекса является то, что он занимает дополнительное пространство и его надо обновлять каждый раз, когда удаляется, обновляется или добавляется запись. На рис. 13 приведен инвертированный список для предыдущего примера.
Рис. 13. Инвертированный список для ключа «Марка автомобиля»
В общем случае инвертированный список может быть построен для любого ключа, в том числе, составного.
В контексте задач поиска можно сказать, что существуют два основных способа организации данных. Первый способ соответствует первому примеру и представляет прямую организацию массива. Второй способ является инверсией первого.
Прямая организация массива удобна для поиска по условию «Каковы свойства указанного объекта?», а инвертированная – для поиска по условию «Какие объекты обладают указанным свойством?».
Существует следующая типология простых (атомарных) запросов:
Здесь в запросах типов 2, 3, 6 вместо оператора равенства может быть использован другой оператор сравнения (больше, меньше, не равно или другие).
Запросы типа 1 выполняются поиском по «прямому» массиву: доступ к записи производится по первичному ключу.
Запросы типа 2 выполняются поиском по инвертированному списку: доступ к записи ( ям) производится по указателю, выбираемому из списка по значению вторичного ключа. Ответом в этих случаях будет значение атрибута или идентификатора.
Запросы типа 3 имеют ответом имя атрибута.
Запросы типа 2, 5, 6 относятся к нескольким атрибутам, и в этом случае могут быть построены несколько индексов, облегчающих поиск по этим ключам.
Составные условия поиска могут использовать несколько простых условий, обычно связанных логическими (булевыми) операторами.
Следует отметить, что в контексте обработки запросов 2-го типа «Какие объекты имеют заданное значение атрибута?» можно выделить три следующих типа архитектур доступа:
1. Системы с вторичными индексами.
В этих системах последовательность расположения записей соответствует последовательности значений первичного ключа. Как правило, используется один первичный индекс и несколько вторичных.
2. Системы частично инвертированных файлов.
В этих системах записи могут располагаться в произвольной последовательности. В отличие от систем первого типа первичный индекс отсутствует. Вторичные индексы применяются для прямой адресации записей, что существенно облегчает включение в файл новых записей, так как допускается их размещение в любом свободном участке файла.
3. Системы полностью инвертированных файлов.В этих системах предусмотрено наличие файлов, содержащих значения отдельных элементов данных, входящих в состав записей - допускается раздельное хранение элементов данных записи.
Значения элементов данных, составляющих конкретную запись или кортеж, в общем случае могут размещаться в памяти произвольно.
Для ускорения процесса поиска в системе используют два набора индексов: индекс экземпляров (значений ключей) и индекс данных (инвертированный список). С помощью индекса экземпляров можно найти в файле элементы данных, имеющих заданное значение. С помощью индекса данных можно найти записи, связанные с заданными значениями элементов. Такая организация характерна для организации данных документальных информационных систем.
Вопрос 4. Представление предметной области и модели данных.[8]
Если бы назначением базы данных было только хранение и поиск данных в массивах записей, то структура системы и самой базы была бы простой.
Причина сложности в том, что практически любой объект характеризуется не только параметрами-величинами, но и взаимосвязями частей или состояний.
Есть различия и в характере взаимосвязей между объектами предметной области:
одни объекты могут использоваться только как характеристики остальных объектов,
другие - независимы и имеют самостоятельное значение (рис. 14).
Рис. 14. Этапы преобразования представлений ПрО
Отдельный элемент данных (его значение) ничего не представляет. Он приобретает смысл только тогда, когда связан с атрибутом (природой значения, что позволит интерпретировать значение) и другими элементами данных. Поэтому физическому размещению данных (и, соответственно, определению структуры физической записи) должно предшествовать описание логической структуры предметной области - построение модели соответствующего фрагмента реального мира, выделяющей только те объекты, которые будут интересны будущим пользователям, и представленные только теми параметрами, которые будут значимы при решении прикладных задач. Такая модель будет иметь очень мало физического сходства с реальностью, но будет полезна как представлениепользователя о реальном мире. Причем это представление будет задаваться (описываться) удобными для пользователясредствами в не адекватной человеку жесткой вычислительной среде с двоичной логикой и числовым представлением информации.
Таким образом, прежде чем описывать физическую реализацию объектов и связей между ними, необходимо определить:
1) способ, с помощью которого внешние пользователи представляют (описывают) объекты и связи;