Логическое (даталогическое) проектирование

Логическое (даталогическое) проектирование — создание схемы базы данных на основе конкретной модели данных, например, реляционной модели данных. Для реляционной модели данных даталогическая модель — набор схем отношений, обычно с указанием первичных ключей, а также «связей» между отношениями, представляющих собой внешние ключи.

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

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

Физическое проектирование

Физическое проектирование — создание схемы базы данных для конкретной СУБД. Специфика конкретной СУБД может включать в себя ограничения на именование объектов базы данных, ограничения на поддерживаемые типы данных и т.п. Кроме того, специфика конкретной СУБД при физическом проектировании включает выбор решений, связанных с физической средой хранения данных (выбор методов управления дисковой памятью, разделение БД по файлам и устройствам, методов доступа к данным), создание индексов и т.д.

52.

54. Назначение и функции языков описания данных

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

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

1. Наиболее известные представители семейства языков манипулирования данными

Data Manipulation Language (DML) (язык управления (манипулирования) данными) — это семейство компьютерных языков, используемых в компьютерных программах или пользователями баз данных для получения, вставки, удаления или изменения данных в базах данных.

На текущий момент наиболее популярным языком DML является SQL, используемый для получения и манипулирования данными в РСУБД. Другие формы DML использованы в IMS/DL1, базах данных CODASYL (таких как IDMS), и других.

Языки DML изначально использовались только компьютерными программами, но с появлением SQL стали также использоваться и людьми.

Функции языков DML определяются первым словом в предложении (часто называемом запросом), которое почти всегда является глаголом. В случае с SQL эти глаголы — «select» («выбрать»), «insert» («вставить»), «update» («обновить»), и «delete» («удалить»). Это превращает природу языка в ряд обязательных утверждений (команд) к базе данных.

Языки DML могут существенно различаться у различных производителей СУБД. Существует стандарт SQL, установленный ANSI, но производители СУБД часто предлагают свои собственные «расширения» языка.

Языки DML разделяются в основном на два типа:

Procedural DMLs — описывают действия над данными.

Declarative DMLs — описывают сами данные.

1. Определение информационно-поискового языка

Информационно-поисковый язык (ИПЯ) — искусственный язык, представляющий совокупность средств для описания формальной и содержательной структуры для поиска (путем индексирования) по запросу пользователя

В ИПЯ можно выделить алфавит, лексику и грамматику.

Алфавит — совокупность определенных символов для записи слов и выражений. Во многих языках для этого используются символы естественного языка.

Лексика — совокупность всех использующихся в языке слов — лексических единиц.

Грамматика — правила составления выражений. Грамматика во многих ИПЯ формальна, а в некоторых вообще отсутствует.

1. Место индексирования в технологии информационного поиска. Виды индексирования

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

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

Существуют некоторые ограничения на типы индексируемых данных (javascript, flash файлы).

Методы

Латентно-семантическое индексирование

Вероятностный латентно-семантический анализ

1. Языки манипулирования данными Web

Рассмотренные выше языки интерпретируют страницы Web как атомарные объекты с двумя свойствами: они могут содержать или не содержать некоторые текстовые образцы и они могут указывать на другие объекты. Опыт использования таких языков показывает, что имеется две основные области приложений, для которых они могут быть полезны. Одна из них, рассматриваемая в разделе 4, - создание оболочек (wrapping) для данных, трансформация и реструктуризация данных. Вторая из этих областей - создание и реструктуризация Web-сайтов - обсуждается в разделе 5. В обеих этих областях приложений часто оказывается существенной возможность иметь доступ к внутренней структуре страниц Web из языка запросов, если мы хотим, чтобы декларативные запросы могли оперировать большой частью задачи. Например, задача извлечения множества кортежей из HTML-страниц сайта Internet Movie Database требует синтаксического анализа HTML-страниц и избирательного доступа к некоторым поддеревьям в дереве синтаксического анализа.

Язык WebOQL: WebOQL - функциональный язык, но запросы формулируются в знакомой форме select-from-where. Предположим, например, что база данных документов на рис. 1 имеет имя СтатьиПоИнформатике и что мы хотим осуществить из нее выборку названия и URL полных текстов статей Смита.

Язык STRUQ: это язык запросов системы управления Web-сайтами STRUDEL, описываемой ниже в разделе 5. Хотя STRUQL был разработан в контексте специфического приложения Web, он является универсальным языком запросов для слабоструктурированных данных, основанным на модели данных помеченных ориентированных графов. Кроме того, модель данных STRUDEL включает именованные коллекции и поддерживает несколько атомарных типов, которые обычно появляются на страницах Web, таких как URL и Postscript, текст, изображение и HTML-файлы. Результат запроса в STRUQL представляет собой граф в той же самой модели данных, что и входные графы. В системе STRUDEL язык STRUQL использовался для решения двух задач: для запросов к неоднородным источникам с тем, чтобы интегрировать их в граф данных сайта, и для запросов к этому графу данных с целью продуцирования графа сайта.

Система FLORID: Система FLORID [HLLS97, LHL+98] - реализация прототипа дедуктивного и объектно-ориентированного формализма F-логики [KLW95].

Языки ULIXES и PENELOPE: В проекте ARANEUS [AMM97b] процесс обработки запросов и реструктуризации разбивается на две фазы. На первой фазе для построения реляционных представлений над Web используется язык ULIXES. Эти представления могут далее анализироваться и интегрироваться с использованием стандартных технологий баз данных. По запросам, сформулированным на языке ULIXES, производится выборка реляционных данных из экземпляров схем страниц, которые определены средствами модели ADM, с интенсивным использованием выражений путей без символа <*> (star-free). Вторая фаза заключается в генерации гипертекстовых представлений данных с использованием языка PENELOPE. Проблемы оптимизации запросов для реляционных представлений, поддерживаемых над множествами страниц Web, например, построенных средствами ULIXES, обсуждаются в [MMM98].

1. Языки запросов первого поколения для Web

Авторы языков запросов первого поколения для Web стремились сочетать в них возможности запросов, основанных на содержании, присущие поисковым машинам Web, с возможностями запросов, основанных на структуре, подобными тем, которые характерны для систем баз данных. Такие языки, к числу которых относятся W3QL [KS95], WebSQL [MMM97, AMM97a] и WebLog [LSS96], сочетают в себе условия, налагаемые на образцы текста, появляющиеся в документах, с графовыми шаблонами, описывающими структуру связей. Далее мы будем использовать WebSQL для демонстрации примеров запросов, возможных в языках такого рода.

Язык WebSQL: В языке WebSQL предлагается моделировать Web как реляционную базу данных, состоящую из двух (виртуальных) отношений: Документ и Якорь. Отношение Документ содержит по одному кортежу для каждого документа из Web, а отношение Якорь - по одному кортежу для каждого якоря в каждом документе из Web. Такая реляционная абстракция Web позволяет нам использовать для формулировки запросов язык, подобный SQL.

Если бы Документ и Якорь были фактическими отношениями, мы могли бы просто использовать SQL, чтобы записывать на нем запросы. Но поскольку эти отношения являются полностью виртуальными и не имеется какого-либо способа производить над ними вычисления, мы не можем оперировать ими непосредственно. Семантика WebSQL зависит от материализации частей этих отношений путем спецификации представляющих интерес документов во фразе FROM запроса. Основным способом материализации части Web является навигация из известных URL. Для описания такой навигации используются правильные выражения путей. Атом такого правильного выражения может иметь форму d1 = > d2, означающую, что документ d1 указывает на d2, и d2 хранится на ином сервере, чем d1. Он может иметь также форму d1 - > d2, которая, в свою очередь, означает, что d1 указывает на d2, и d2 хранится на том же самом сервере, что и d1.

Предположим, например, что мы хотим найти список триплетов вида (d1, d2, метка), где d1 - документ, хранимый на нашем локальном сайте, d2 - документ, хранимый где-либо еще, и d1 указывает на d2 с помощью связи, помеченной меткой. Допустим также, что все наши локальные документы достижимы из www.mysite.start. Тогда указанную задачу можно решить с помощью запроса:

SELECT d.url, e.url, a.label

FROM Document d SUCH THAT

<www.mysite.start> -> d,

Document e SUCH THAT d => e,

Anchor a SUCH THAT a.base = d.url

WHERE a.href = e.url

Предложение FROM порождает экземпляры двух переменных, определенных на отношении Документ, - d и e, и одной переменной a - на отношении Якорь. Области определения переменной d принадлежит каждый локальный документ, достижимый из начального документа, а e принимает значения на множестве всех не локальных документов, достижимых непосредственно из d. В свою очередь, значением переменной a может являться каждая связь, которая исходит из документа d. Дополнительное условие, предписывающее, чтобы целевым документом связи a был документ e, задается предложением WHERE. Другим способом материализации части отношений Документ и Якорь является использование условий, налагаемых на содержание (content condition). Например, если для нас представляли интерес только документы, которые содержат строку "база данных", мы могли бы добавить в предложение FROM условие: d MENTIONS "база данных". В этом случае в реализации использовались бы поисковые машины для генерации возможных документов, удовлетворяющих условию NENTION.

Другие языки: Язык W3QL [KS95] подобен, по существу, WebSQL, с некоторыми значительными различиями: он использует внешние программы (аналогично определяемым пользователем функциям в объектно-реляционных языках) для спецификации условий, налагаемых на содержание файлов, а не формирование условий в синтаксисе языка, и это обеспечивает механизмы для обработки форм, встречающихся в процессе навигации. В работе [KS98] Конопницкий и Шмуэли описывают планируемые расширения, позволяющие превратить W3QL в то, что мы называем теперь языками второго поколения. Эти расширения предусматривают моделирование внутренней структуры документов, иерархическое моделирование Web, в котором явно фигурирует понятие Web-сайта, а также отказ от использования метода внешних программ для спецификации в пользу обобщенного расширяемого метода, основанного на стандарте MIME.

WebLog [LSS96] отличается от рассмотренных выше языков использованием дедуктивных правил вместо SQL-подобного синтаксиса (см. описание FLORID ниже).

WQL, язык запросов проекта WebDB [LSCH98], подобен WebSQL, но он в большей мере поддерживает функциональные возможности SQL, допуская, например, агрегацию и группирование, и, кроме того, обеспечивает ограниченную поддержку запросов внутридокументной структуры. Это обстоятельство позволяет отнести его к классу языков, обсуждаемых в следующем подразделе.

1. Второе поколение: Языки манипулирования данными Web

Рассмотренные выше языки интерпретируют страницы Web как атомарные объекты с двумя свойствами: они могут содержать или не содержать некоторые текстовые образцы и они могут указывать на другие объекты. Опыт использования таких языков показывает, что имеется две основные области приложений, для которых они могут быть полезны. Одна из них, рассматриваемая в разделе 4, - создание оболочек (wrapping) для данных, трансформация и реструктуризация данных. Вторая из этих областей - создание и реструктуризация Web-сайтов - обсуждается в разделе 5. В обеих этих областях приложений часто оказывается существенной возможность иметь доступ к внутренней структуре страниц Web из языка запросов, если мы хотим, чтобы декларативные запросы могли оперировать большой частью задачи. Например, задача извлечения множества кортежей из HTML-страниц сайта Internet Movie Database требует синтаксического анализа HTML-страниц и избирательного доступа к некоторым поддеревьям в дереве синтаксического анализа.

В этом подразделе мы опишем языки запросов второго поколения для Web, которые мы называем "языками манипулирования данными Web". Эти языки превосходят языки первого поколения в двух важных аспектах. Прежде всего, они обеспечивают доступ к структуре объектов Web, которыми они манипулируют. В отличие от языков первого поколения, они моделируют внутреннюю структуру документов Web, а также внешние связи, которые их соединяют. Они поддерживают связи для моделирования гиперссылок, а некоторые из них поддерживают также упорядоченные совокупности записей для более естественного представления данных. Во-вторых, эти языки обеспечивают возможности создания новых сложных структур в результате запроса. Поскольку данные в Web обычно являются слабоструктурированными, в этих языках придается особое значение поддержке возможностей для работы со слабоструктурированными данными. Далее кратко описываются три языка этого класса: WebOQL [AM98], STRUQL [FFLS97] и FLORID [HLLS97].

1. ПРИНЦИПИАЛЬНАЯ ОСОБЕННОСТЬ ИНТЕРФЕЙСОВ к WEB

Интерактивные интерфейсы запросов

Все языки, рассмотренные в предыдущих двух подразделах, слишком сложны для непосредственного применения интерактивными пользователями, точно так же, как и SQL. Предполагается, что они, подобно SQL, должны использоваться, главным образом, как инструментальные средства программирования. Однако проводились работы по созданию интерактивных интерфейсов запросов, пригодных для случайных пользователей. Одним из них является Dataguides [GW97] - интерактивное средство запросов для слабоструктурированных данных, основанное на иерархических "выжимках" (summaries) графа данных. Расширения для поддержки запросов в отдельных сложных Web-сайтах рассмотрены в [GW98]. Система, описанная в [HML+98], поддерживает запросы, которые сочетают мультимедийные возможности, например, схожесть с данным эскизом или изображением, возможности работы с текстами, такие как поиск по ключевым словам, а также семантику предметной области.

1. Приниципиальная особенность интерфейсов к Web?

Слабоструктури́рованные да́нные (полуструктурированные или плохо структурированные данные) — это форма структурированных данных, не соответствующая строгой структуре таблиц и отношений в моделях реляционных баз данных, тем не менее эта форма данных содержит теги и другие маркеры для отделения семантических элементов и для обеспечения иерархической структуры записей и полей в наборе данных.[1]. Таким образом, такой вид данных можно назвать бессхемным (schemaless), а структуру — самоописываемой.

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

Слабоструктурированные данные становятся важным объектом для исследований по нескольким причинам:

к таким источникам данных, как Веб, удобно обращаться как к базам данных, но Веб нельзя «уложить» в прокрустово ложе какой-либо определённой схемы данных;

желательно иметь предельно гибкий формат для обмена данными между разными базами данных;

даже при работе со структурированными данными может быть удобно представлять их в виде слабоструктурированных данных с целью навигации по ним.

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

1. Разновидности ИПЯ и их возможности в привязке к информационно-поисковым системам Интернета.

Типы и виды ИПЯ

Способ задания лексических единиц

Контролируемые — языки, словарный состав которых задается и контролируется с помощью словарей и таблиц. К ним относят различные системы классификации (УДК, ББК, классификация Дьюи).

Язык предметных рубрик. На основе иерархической классификации строят систематические каталоги. На основе языка предметных рубрик строят предметные каталоги. Алфавитные каталоги — ручной поиск.

Дескрипторные ИПЯ, а также язык ключевых слов — автоматический поиск.

Неконтролируемые — лексика не задается словарем, а строится на основе выбора терминов естественного языка. Такие ИПЯ широко начали применяться в последнее время.

Порядок записи лексических единиц

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

Координируемые ИПЯ — языки, в которых лексические единицы связывается, координируются между собой или в процессе индексирования или в процессе использования.

Предкоординируемые — связи между лексическими единицами устанавливаются перед поиском.

Посткоординируемые — когда связи между лексическими единицами устанавливаются только при поиске.

1. Классы языков запросов Web

Языки запросов объектно-ориентированных баз данных

Потребность в поддержании в объектно-ориентированной СУБД не только языка (или семейства языков) программирования ООБД, но и развитого языка запросов в настоящее время осознается практически всеми разработчиками. Система должна поддерживать легко осваиваемый интерфейс, прямо доступный конечному пользователю в интерактивном режиме.

22.4.1. Явная навигация как следствие преодоления потери соответствия

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

22.4.2. Ненавигационные языки запросов

Беери отмечает существование трех подходов. Первый подход - языки, являющиеся объектно-ориентированными расширениями языков запросов реляционных систем. Наиболее распространены языки с синтаксисом, близким к известному языку SQL. Это связано, конечно, с общим признанием и чрезвычайно широким распространением этого языка. В частности, в своем Манифесте третьего поколения СУБД М. Стоунбрекер и его коллеги по комитету перспективных систем БД утверждают необходимость поддержания SQL-подобного интерфейса во всех СУБД следующего поколения. Мы уже видели, какое влияние оказывает эта точка зрения на развитие языка SQL.

Второй подход основывается на построении полного логического объектно-ориентированного исчисления. По поводу построения такого исчисления имеются теоретические работы, но законченный и практически реализованный язык запросов нам неизвестен. Видимо к этому же направлению строго теоретически обоснованных языков запросов можно отнести и работы, основанные на алгебраической теории категорий.

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

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

В языке запросов объектно-ориентированной СУБД ORION полностью поддерживается принцип инкапсуляции объектов. В реализованном варианте языка запросы могут основываться только на одном классе (предлагался подход к определению запроса на нескольких классах в стиле расширения семантики реляционного оператора соединения). Синтаксис языка ориентирован на SQL. Очень развит набор допустимых предикатов селекции. В частности, для атрибута, доменом которого является суперкласс, можно указать имя интересующего пользователя подкласса.

Язык запросов системы Iris находится в значительной степени под влиянием реляционной парадигмы. Даже название этого языка OSQL отражает его тесную связь с реляционным языком SQL. По сути дела, OSQL - это реляционный язык, рассчитанный на работу с ненормализованными отношениями. Естественно, при таком подходе в OSQL нарушается инкапсуляция объектов.

На наш взгляд, особый интерес представляет декларативный язык запросов системы O2 RELOOP. В общих словах, это декларативный язык запросов с SQL-ори-ентированным синтаксисом, основанный на специально разработанной для модели O2 алгебре объектов и значений. (Кстати, это не единственная работа в направлении построения алгебры для объектно-ориентированных моделей данных.) Особенно впечатляющим качеством языка RELOOP является естественность его построения в общем контексте модели O2. Запрос задается всегда на значении-множестве или списке. Если мы вспомним, что долговременному классу в O2 соответствует одноименное значение-множество, то тем самым можно определить запрос на любом хранимом классе. Результатом запроса может являться объект, значение-множество или значение-список. При этом элементами значений-множеств могут являться объекты (простая выборка), либо значения-кортежи с элементами-объектами разных классов (например). В совокупности эти особенности языка позволяют формулировать запросы над несколькими классами (специфическое соединение, порождающее не новые объекты, а кортежи из существующих объектов), а также употреблять вложенные подзапросы.

Не нашли, что искали? Воспользуйтесь поиском: