1 сентября [Лекции]

Введение

Реляционная модель данных является наиболее популярной теоретико-множественной моделью, получившей широкое распространение и ставшей стандартом разработки современных СУБД.

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

Теоретической основой реляционной модели стала теория отношений, основы которой заложили два логика – американец Чарьлз Содерс Пирс (1839-1914) и немец Эрнст Шредер (1841-1902). В руководствах по теории отношений было показано, что множество отношений замкнуто относительного некоторого набора специальных отношений, образуя тем самым вместе с операциями абстрактную алгебру. Это важнейшее свойство отношений было использовано в реляционной модели для разработки языка манипулирования данными, связанного с исходной алгеброй.

В 1970 году еще один американец – математик Э. Ф. Кодд – впервые сформулировал основные понятия и ограничения реляционной модели, ограничив набор операций в ней семью основными и одной дополнительной операцией. Предложение Кодда были настолько эффективными для использования в области баз данных, что за эту модель он был удостоен престижной премии Тьюринга в области теоретических основ вычислительной техники.

1 сентября [Лекции]

Инфологическая модель данных. Модель «сущность-связь» (ER-модель).

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

Инфологическая модель данных предоставляет интуитивно понятное формализованное описание предметной области. Емкость этого описания должна быть достаточной для оценки глубины и корректности проработки проекта базы данных. Кроме того, данное описание должно быть независимым от выбора конкретной СУБД.

Инфологическое проектирование в первую очередь связано с попыткой представления семантики предметной области в модели базы данных. Данная проблема давно интересует разработчиков, и еще в 70-х года 20 века было предложено несколько моделей данных, названных семантическими моделями. К ним можно отнести семантическую модель данных, которую предложили Хаммер (Hammer) и Мак-Леон (McLeon) в 1981 году, функциональную модель данных, которую также в 1981 году предложил Шипман (Shipman), модель «сущность-связь», предложенную Ченом (Chen) в 1976 году, а также ряд других моделей.

У каждой из этих моделей были свои сильные и слабые стороны, но испытание временем выдержала только одна из них – модель «сущность-связь» Чена. В настоящий момент эта модель, которую еще называют «Entity Relationship», фактически стала стандартом при инфологическом моделировании баз данных. Общепринятым стало сокращенное название ER-модель. Большинство современных CASE-средств содержат инструментальные средства для описания данных в формализме этой модели. Кроме того, разработаны методы автоматического преобразования проекта базы данных из ER-модели в реляционную модель, при котором преобразование выполняется сразу в даталогическую модель, соответствующую конкретной СУБД.

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

Как и любая другая модель, модель «сущность-связь» имеет несколько базовых понятий, на основании которых стоятся уже более сложные объекты по заранее определенным правилам.

ER-модель в наибольшей степени согласуется с концепцией объектно-ориентированного проектирования, которая в настоящий момент является без сомнений основной при разработке крупных информационных систем.

В основе модели «сущность-связь», как следует из ее названия, лежат два основных понятия – сущность и связь.

Сущность является описанием класса однотипных объектов моделируемой предметной области. Говоря о некотором «классе однотипных объектов», предполагается, что сама система (база данных) содержит множество экземпляров такой сущности.

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

Например, информационная система университета оперирует данными учащихся, а соответствующая база данных содержит множество записей, соответствующих различным студентам. Описанием класса будет являться сущность Студент. Экземпляром сущности будет являться описание конкретного студента. Сущность Студент может, например, иметь следующий набор атрибутов: Фамилия, Имя, Отчество, Дата рождения, Год поступления, Номер студенческого билета. Для сущности Студент ключевым атрибутом будет Номер студенческого билета, так как у всех студентов номера студенческих билетов различны.

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

Вторым основополагающим понятием ER-модели является связь – бинарная ассоциация, обозначающая, как сущности соотносятся или взаимодействую между собой. Связь может существовать не только между двумя различными сущностями, но и между сущностью и ей же самой. Такая связь называется рекурсивной.

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

Связи обладают двумя основными качествами – множественность и обязательность. Множественность связи обозначает, со сколькими экземплярами второй сущности связан экземпляр первой и наоборот. Обязательность связи указывает, должен ли каждый экземпляр сущности участвовать в этой связи или нет. Помимо прочего связь имеет имя, а также имена ролей со стороны обеих сущностей.

По множественности связи делятся на три типа: один-к-одному (1:1), один-ко-многим (1:М) и многие-ко-многим (М:М). Связь один-к-одному означает, что экземпляр одной сущности связан только с одним экземпляром другой сущности. Связь один-ко-многим означает, что один экземпляр сущности, расположенный слева в связи, может быть (но не обязан!) связан с несколькими экземплярами другой сущности, расположенными справа в связи. И наконец, связь многие-ко-многим означает, что как один экземпляр первой сущности может быть связан с несколькими экземплярами второй сущности, так и наоборот, один экземпляр второй сущности может быть связан с несколькими экземплярами первой сущности.

Например, рассмотрим связь между сущностями Студент и Преподаватель, которая обозначает руководство дипломной работой. Очевидно, что у одного студента может быть только один руководитель. Вместе с тем, один и тот же преподаватель может одновременно руководить несколькими студентами. Это означает, что необходимая связь по множественности принадлежит к типу 1:М (один-ко-многим), при этом исходит она от преподавателя к студенту (в связи всегда участвует только один преподаватель, а вот студентов может быть несколько).

Как уже говорилось, в разных нотациях множественность связи отображается по-разному. Мы будем использовать нотацию CASE системы POWER DESIGNER, в которой множественность связи отображается путем разделения линии связи на 3. В нашем случае связь имеет имя «Дипломная работа» и имена ролей «Руководит» (у Преподавателя) и «Пишет диплом» (у Студента).

По обязательности связи делятся на обязательные и необязательные. При этом не играет роли множественность связи, а связь может быть обязательной с одной стороны и необязательной с другой. Обязательность связи также по-разному обозначается в разных нотациях. В нотации POWER DESIGNER необязательность связи обозначает пустой кружок на конце связи, а обязательность – перпендикулярная линия, перечеркивающая связь.

Вернемся к рассмотренному ранее примеру руководства дипломной работой. Если рассмотреть введенную связь «Дипломная работа» на предмет обязательности, то можно заметить, что каждый студент, пишущий дипломную работу, должен иметь руководителя. Однако, не каждый преподаватель обязан руководить тем или иным студентом. Это означает, что введенная связь обязательна со стороны преподавателя и необязательна со стороны студента (экземпляр сущности Преподаватель обязательно должен участвовать в связи, а вот экземпляры сущности Студент могут не участвовать в связи вообще).

Зная эти уточнения и используя введенные обозначения, нашу связь можно изобразить следующим образом:

Между сущностями может быть установлено любое количество связей с разными смысловыми нагрузками. Например, между сущностями Студент и Преподаватель могут быть установлены связи «Дипломная работа» и «Лекции». Первая связь будет означать уже рассмотренный случай написания студентом дипломной работы под руководством того или иного преподавателя, а вторая связь – лекции каких преподавателей слушает студент и каким студентам данный преподаватель читает лекции. Очевидно, что вторая связь – пример связи «многие-ко-многим».

Последним и наиболее сложным из понятий, связанных с ER-моделями, является понятие категоризации сущностей. Это означает, что в модели «сущность-связь», как и в объектно-ориентированных языках программирования, можно ввести понятие подтипа сущности, а сущность представить в виде двух или более подтипов. Подтипы – это сущности, каждая из которых имеет общие атрибуты и/или отношения, которые определяются один раз на верхнем уровне и наследуются на нижнем уровне.

Все подтипы одной сущности рассматриваются как взаимоисключающие. То есть при разделении сущности на подтипы она должна быть представлена в виде полного набора взаимоисключающих подтипов. Если на уровне анализа предметной области не удается выявить полный перечень подтипов, то вводится специальный подтип, называемый обычно Другое, который в дальнейшем может быть уточнен.

Сущность, на основе которой строятся подтипы, называется супертипом. Любой экземпляр супертипа относится к конкретному подтипу. Для графического изображения принципа категоризации сущностей используется специальный графический элемент – узел-дискриминатор. В нотации POWER DESIGNER узел-дискриминатор изображается в виде полукруга, обращенного выпуклой стороной к супертипу. Эта сторона соединяется стрелкой с супертипом, а к диаметру полукруга линиями присоединяются подтипы данной сущности.

Узел-дискриминатор может быть взаимоисключающим (mutually exclusive, M/E) или нет. Взаимоисключающий узел-дискриминатор означает, что один экземпляр сущности супертипа может быть связан только с одним экземпляром сущности подтипа, и для каждого экземпляра сущности супертипа существует потомок. Простой узел-дискриминатор подобных ограничений не накладывает.

Рассмотрим в качестве примера категоризацию сущности Отметка. Во врем обучения студенты получают отметки трех типов: за Коллоквиумы, Зачеты и Экзамены. Приведенная в примере диаграмма изображает, что каждая из отметок является отметкой одного из трех указанных типов. Наследуемым от суперсущности общим атрибутом для всех подтипов будет Код отметки.

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

В качестве заключительного примера спроектируем инфологическую модель системы, предназначенной для хранения отметок студентов. Разработку модели начнем с выявления основных сущностей – объектов моделируемой предметной области.

Центральными сущностями модели являются Студент и Отметка, что непосредственно следует из названия задачи. Так как отметку ставит преподаватель, то необходима сущность Преподаватель. Кроме того, сущность Отметка имеет три подтипа (см. предыдущий пример): Коллоквиум, Зачет и Экзамен. Атрибуты сущностей очевидным образом берутся из описания предметной области.

Между сущностями Студент и Отметка устанавливается связь «один-ко-многим», означающая, что за время обучения каждый студент получает целый перечень оценок, в частности формирующих его зачетную книжку (связь можно назвать «Имеет оценки»). Связь необязательная со стороны студента, но обязательна со стороны оценки. Это означает, что у студента может еще не быть оценок (он только что поступил в университет), но вот оценки самой по себе без того, кому она поставлена, быть не может.

Между сущностями Преподаватель и Отметка также устанавливается связь «один-ко-многим», так как один и тот же преподаватель может поставить несколько оценок (одному или многим студентам, связь можно назвать «Поставил оценки»). Связь необязательная со стороны преподавателя, но обязательно со стороны оценки. Это означает, что преподаватель мог не участвовать в приемке тех или иных экзаменов (а значить и ставить оценки), но оценки без того, кто ее поставил, быть не может.

Таким образом, инфологическая модель предметной области может быть представлена в следующем виде:

4 августа [Лекции]

Фактографические и документальные базы данных. Геоинформационные базы данных. XML базы данных.

Помимо разделения по способу описания данных, на базы данных можно взглянуть и с другой стороны, а именно – с точки зрения самих данных, для хранения которых они предназначены. Здесь можно отметить два больших принципиально разных класса. Документальная база данных хранит записи, которые отражают документ и содержат его библиографическое описание и, возможно, иную информацию о нем. Фактически она может хранить сильно неструктурированные данные. В то же время, фактографическая база данных хранит записи, которые содержат данные непосредственно о состоянии внешнего мира (описание предметной области), не опосредованные ссылками на отражающие их документы, а значит – гораздо более структурируемые данные.

Отдельно в ряду современных баз данных с точки зрения обрабатываемой информации стоят геоинформационные базы данных, предназначенные для хранения геоинформационных данных (карт, схем дорог и так далее). Геоинформационные технологии получают в настоящее время широкое распространение, а геоинформационные системы (ГИС) занимают достойное место в ряду информационных систем различного назначения. Востребованность такого рода технологий определяется, прежде всего, специфическими свойствами, присущими только ГИС.

Стремительное развитие web-технологий также привело к возникновению особого рода баз данных – XML-баз данных (XML-ориентированные СУБД), предназначенных для работы с современными web-узлами, многие из которых основаны на технологии XML. Основной задачей такой базы данных является хранение XML-данных, а также всех компонент XML-модели, а также обеспечение эффективной работы с хранимой информацией. Особенностью таких данных является то, что XML-документы могут содержать мегабайты текстовых строк и тегов XML. Такие документы имеют иерархическую структуру, и лучше оставить эту иерархию в неизменном виде, ведь поиск в этом случае окажется гораздо более эффективным.

4 августа [Лекции]

Модели данных (сетевые, иерархические, реляционные).

Разговор о моделях данных нельзя вести, не внеся ясность в сами понятия «данные» и «модель данных», которые являются основополагающими в концепции баз данных.

Данные можно определить как набор некоторых конкретных значений, характеризующих любой из описываемых объектов – например, Ауди ТТ, 2008 год выпуска.

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

За время развития баз данных выделились основные модели данных: сетевые, иерархические, реляционные.

Стандарт сетевой модели впервые был определен в 1975 году организацией CODASYL (Conference of Data System Languages), которая определила базовые понятия и формальный язык описания.

Основными объектами сетевой модели являются:

- элемент данных;

- агрегат данных;

- запись;

- набор данных.

Элемент данных – это минимальная единица информации, доступная пользователю с помощью СУБД.

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

Записью называет совокупность агрегатов или элементов данных, моделирующая некоторый класс объектов реального мира. Набором называют двухуровневый граф, связывающий отношением «один-ко-многим» два типа записи. Фактически набор отражает иерархическую связь между двумя типами записей, родительская запись называется владельцем набора, а подчиненная – членом набора. Между двумя записями может быть определено любое число наборов.

Модель поддерживает язык описания данных и язык манипулирования данными. Операции манипулирования в сетевой модели делятся на навигационные операции и операции модификации.

Иерархическая модель данных является наиболее простой из даталогических моделей. Исторически она появилась первой среди всех даталогических моделей, именно ее поддерживает первая из зарегистрированных промышленных СУБД IMS фирмы IBM.

Основными информационными единицами являются база данных, сегмент и поле. Поле – это минимальная неделимая единица данных, доступная пользователю с помощью СУБД. Сегмент (который в терминологии Data Base Task Group, DBTG называют записью) определяет два понятия – тип сегмента (записи) и экземпляр сегмента (записи).

Тип сегмента – это именованная совокупность типов элементов данных, в него входящих. Экземпляр сегмента образуется из конкретных значений полей или элементов данных, в него в ходящих. Каждый тип сегмента образует набор однородных записей.

В иерархической модели сегменты объединяются в ориентированный древовидный граф. При этом полагают, что направленные ребра графа отражают иерархические связи между сегментами (родительскому по иерархии экземпляру сегмента может соответствовать множество экземпляров подчиненного сегмента). Схема иерархической базы данных представляет собой совокупность отдельных деревьев, каждое из которых называется физической базой данных. Каждая физическая база данных удовлетворяет иерархическим ограничениям:

- у нее существует один корневой сегмент, у которого нет родителя;

- каждый сегмент может быть связан с произвольным числом подчиненных сегментов;

- каждый подчиненный сегмент может иметь только одного родителя.

В рамках иерархической модели выделяют языковые средства описания данных (Data Definition Language, DDL) и манипулирования данными (Data Manipulation Language, DML).

Реляционная модель – яркий представитель теоретико-множественных моделей данных. Теоретические основы модели заложили логики Чарльз Содерс Пирс (1839 – 1914) и Эрнст Шредер (1841 – 1902). Основной структурой данных в реляционной модели является отношение – подмножество декартова произведения исходных множеств, называемых доменами. Каждое отношение моделирует определенную реальную ситуацию и имеет очень простое графическое изображение в виде таблицы, столбцами   которой являются имена доменов, а строками – наборы значений, взятых из этих доменов. Вхождение домена в отношение называется атрибутом.

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

В реляционной модели определен набор операций, составляющих реляционную алгебру. Разработал основы реляционной алгебры Э. Ф. Кодд, который предложил 8 операций – 4 теоретико-множественные и 4 специальные.

31 июля [Статьи]

Конкурсы и гранты: они где-то рядом...

Ключевые слова: конкурс, грант, проект, стипендия, конференция, фонд, образование, поддержка, молодой ученый, студент, аспирант, ВУЗ, научная деятельность

Автор: Приходько Максим Александрович

Наверное начинать статью словами о себе не совсем прилично. Однако, того требует тема, вынесенная в ее заголовок: "Конкурсы и гранты". В свое время мне довелось потратить 5 лет на обучение в МГУ, потом почти столько же на аспирантуру и защиту кандидатской диссертации. И за все эти 10 лет мне ни разу не удалось услышать хотя бы намек на то, что вокруг меня постоянно проходят один за другим конкурсы научных работ, проектов, статей и так далее.

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