Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2005 г.

Языки пространственных запросов

Часть 3 из книги "Основы пространственных баз данных"

Шекхар Шаши, Чаула Санжей
Издательство "КУДИЦ-ОБРАЗ"

Полное содержание книги

Часть 3

Язык запросов, главное средство взаимодействия с базой данных, – это основное необходимое условие существования СУБД. Популярным коммерческим языком запросов к реляционным системам управления базами данных (RDBMS, relational database management system) является SQL. Отчасти он основан на формальном языке запросов, реляционной алгебре (РА), его отличают простота использования, интуитивность и универсальный характер. СУПБД представляют собой частный случай расширяемых СУБД и работают как с пространственными, так и с непространственными данными, поэтому вполне естественно попытаться найти расширение SQL, позволяющее обращаться к пространственным данным.

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

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

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

Уникальная особенность пространственных данных состоит в том, что «естественная» среда взаимодействия с пользователем является наглядной, графической, а не текстовой. Поэтому любой язык пространственных запросов должен поддерживать сложный компонент графической визуализации. Показав это, мы сосредоточимся далее на неграфических пространственных расширениях SQL. В разделе 3.1 будет описана база данных World, которая послужит основой всех примеров запросов в этой главе. Разделы 3.2 и 3.3 соответственно содержат краткий обзор РА и языка SQL. Раздел 3.4 посвящен обсуждению требований, предъявляемых к пространственным расширениям SQL. Кроме того, мы расскажем о стандарте консорциума OGIS, предназначенном для расширения SQL применительно к географическим данным. В разделе 3.5 будет показано, как часто встречающиеся пространственные запросы можно сформулировать при помощи OGIS-расширения SQL. В разделе 3.6 вы познакомитесь с языком SQL3 и реализацией подмножества этого языка, предлагаемой фирмой Oracle.

3.1. СТАНДАРТНЫЕ ЯЗЫКИ ЗАПРОСОВ К БАЗАМ ДАННЫХ

Пользователи взаимодействуют с данными, находящимися в СУБД, посредством языка запросов. В отличие от традиционных языков программирования языки запросов к базам данных относительно просты в изучении и использовании. В этом разделе мы обсудим два таких языка запросов. Первый из них, РА, является более формальным, нежели второй, и обычно не реализуется в коммерческих базах данных. Говоря о важности РА, следует помнить, что она образует ядро SQL – самого популярного и имеющего множество реализаций языка запросов к базам данных.

3.1.1. База данных World

С РА и языком SQL мы познакомимся на примере учебной базы данных. Новая учебная база данных требуется нам здесь для того, чтобы придать разнообразие примерам и упражнениям. База данных World (Мир) состоит из трех сущностей: Country (Страны), City (Города) и River (Реки). Расширенная путем введения пиктограмм диаграмма «сущность-связь» этой базы данных, а также примеры таблиц приведены соответственно на рис. 3.1 и в таблице 3.1. Схема базы данных показана ниже. Заметим, что подчеркнутые атрибуты являются первичными ключами. Например, Name является первичным ключом таблиц Country, City и River.

Country [Страны] (Name [Название]: varchar(35), 
             Cont [Континент]: varchar(35), 
  Pop [Население]: integer, GDP [ВВП]:Integer, 
  Life-Exp [Продолжительность жизни]: integer, 
                    Shape [Очертания]:char(13))
City [Города] (Name [Название]: varchar(35), 
       Country [Страна]: varchar(35),
  Pop [Население]: integer, Capital [Столица]:char(1), 
               Shape [Очертания]:char(9))
River [Реки] (Name [Название]: varchar(35), 
            Origin [Исток]: varchar(35),
  Length [Длина]: integer, Shape [Очертания]:char(13))

img01

Рис. 3.1. Диаграмма «сущность-связь» базы данных World

Таблица 3.1. Таблицы базы данных World с примерами записей

(а) Страны

(б) Города

(в) Реки

Сущность Country имеет шесть атрибутов. Название страны (Name) и континент (Cont), где она находится, хранятся как символьные строки, максимальная длина которых равна 35. Население (Pop) и валовый внутренний продукт (GDP) имеют целый тип. ВВП – это совокупная стоимость товаров и услуг, произведенных в стране за один финансовый год. Атрибут Life-Exp отражает выраженную в годах (округленную до ближайшего целого) среднюю продолжительность жизни граждан страны. Атрибут очертания (Shape) требует некоторых пояснений. Геометрические очертания страны представлены столбцом Shape таблицы 3.1. В реляционных базах данных, где типы данных ограничены, атрибут Shape является внешним ключом к таблице очертаний. В объектно-реляционных или объектно-ориентированных базах данных атрибут Shape имеет абстрактный тип данных (АТД) «многоугольник». Поскольку в данный момент нашей целью является введение основ РА и SQL, мы не будем строить запросов по атрибуту Shape до изложения раздела 3.4.

Отношение City содержит пять атрибутов: Name, Country, Pop, Capital и Shape. Атрибут страна (Country) является внешним ключом по отношению к таблице Country. Столица (Capital) – это символьное поле длины 1 с фиксированным набором значений; город может либо быть столицей страны, либо не быть ею. Атрибут очертания (Shape) – это внешний ключ к таблице, содержащей образ, составленный из точек. Что же касается отношения Country, то мы не станем выполнять запросы к столбцу Shape до изучения типов данных OGIS в языке SQL3.

Четыре атрибута отношения River называются Name, Origin, Length и Shape. Атрибут исток (Origin) является внешним ключом отношения Country и определяет страну, где река берет свой исток. Атрибут очертания (Shape) представляет собой внешний ключ к таблице, содержащей образ, составленный из линий. Чтобы определить страну, на территории которой находится исток реки, геометрической информации, заданной атрибутом Shape, недостаточно. Перегрузку имен в таблицах можно преодолеть, используя «точечную» нотацию уточненного имени атрибута, содержащего название таблицы: таблица.атрибут. Конструкции Country.Name, city.Name и river.Name однозначно определяют атрибут Name в пределах различных таблиц. Также нам потребуется информация о направлении течения рек. В главе 7 мы обсудим пространственно-сетевые запросы, в которых важна информация о направлении.

3.2. РЕЛЯЦИОННАЯ АЛГЕБРА

Реляционная алгебра – это формальный язык запросов, связанный с реляционной моделью. Алгеброй называется математическая структура, состоящая из двух различных множеств (Ωa, Ωo). Ωa – множество операндов, Ωo – множество операций. Алгебра должна удовлетворять большому количеству аксиом, однако решающее значение имеет то, что результат операции над операндом должен входить во множество Ωa. Простым примером алгебры является множество целых чисел. Операндами являются целые числа, операциями – сложение и умножение. В главе 8 мы обсудим другие виды алгебр, связанных с растровыми объектами и изображениями.

В РА существует только один тип операндов и шесть базовых операций. Операнд – это отношение (таблица), к операциям же относятся выборка (selection), проекция (project), объединение (union), векторное произведение (cross-product), разность (difference) и пересечение (intersection). Представим некоторые из базовых операций более подробно.

3.2.1. Операции выборки и проекции

РА предоставляет две операции, предназначенные для работы с данными одного отношения: выборку и проекцию. Операция выборки возвращает подмножество строк реляционной таблицы, операция проекции извлекает подмножество столбцов. Например, чтобы составить список всех стран таблицы Country, расположенных в Северной Америке (СА), используется следующее выражение реляционной алгебры:

img02

Результат этой операции показан в таблице 3.2(а). Столбцы, возвращаемые операцией выборки σ, определяются оператором выборки, то есть оператором сравнения, который в этом примере записывается как cont = "Северная Америка". Оператор выборки не изменяет схему входного отношения. Формально синтаксис операции выборки имеет вид:

img03

Подмножества столбцов всех строк отношения извлекаются посредством операции проекции π. Например, для получения названий всех стран, перечисленных в таблице Country, используется выражение

img04

Формально синтаксис операции проекции имеет вид:

img05

Операции выборки и проекции можно применять совместно. Следующее выражение возвращает названия стран Северной Америки. Результат показан в таблице 3.2(в).

img06

Таблица 3.2. Результаты двух базовых операций РА: выборки и проекции

3.2.2. Операции над множествами

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

  • Объединение. Если R и S есть отношения, то возвращает все кортежи, которые встречаются или в R, или в S. Например, мы можем использовать операцию объединения для составления списка стран, которые либо расположены в Северной Америке, либо имеют реки, берущие исток на этом континенте.

    1.    R = πNameCont=СА(Country)).

    2.    S = πOrigin(River).

    3.   

    Результирующее отношение показано в таблице 3.4(а). Заметим, что атрибуты R.Name и S.Origin имеют общую область определения, поскольку атрибут R.Origin связан с Country.Name. Этого достаточно для того, чтобы отношения R и S были совместными по объединению.

  • Разность. R – S возвращает все кортежи в R, которые отсутствуют в S. Оператор разности может использоваться, например, для отыскания всех стран в Северной Америке, на территории которых нет истоков рек (перечисленных в таблице River). Результирующее отношение показано в таблице 3.4(б).

    1.    R = πNameCont=СА(Country)).

    2.    S = πOrigin(River).

    3.    R – S.

  • Пересечение. Для двух совместных по объединению отношений R и S оператор пересечения возвращает все кортежи, встречающиеся как в R, так и в S. Отметим, что эта операция, хотя и весьма удобна, является избыточной: ее можно получить из операции разности: = R – (R – S). Чтобы найти все страны, которые расположены в Южной Америке и на территории которых находятся истоки рек, используем операцию пересечения. Результат представлен в таблице 3.4(в).
  • 1.    R = πNameCont=ЮА(Country)).

    2.    S = πOrigin(River).

    3.    .

  • Векторное произведение. Эта операция применяется к любой паре отношений, а не только к отношениям, совместным по объединению. R x S возвращает отношение, схема которого содержит все атрибуты R, за которыми следуют все атрибуты S. Для простоты в таблице 3.3 приведен абстрактный пример этой операции. Обратите внимание на использование «точечной» нотации для различения атрибутов обоих отношений.

Таблица 3.3. Векторное произведение отношений R и S
R R.A R.B

A1 B1
A2 B2

(а) Отношение R
S S.C S.D

C1 D1
C2 D2

(b) Отношение S
R × S R.A R.B S.C S.D

A1 B1 C1 D1
A1 B1 C2 D2
A2 B2 C1 D1
A2 B2 C2 D2

(c) R × S

Таблица 3.4. Результаты операций над множествами
НАЗВАНИЕ
Канада
Мексика
Бразилия
Куба
США

(а) Объединение
НАЗВАНИЕ
Канада
Мексика
Куба

(б) Разность
НАЗВАНИЕ
Бразилия

(в) Пересечение

3.2.3. Операция соединения

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

Условные соединения

Условное соединение общего вида |c для отношений R и S выражается так:

img07

Условие c обычно относится как к атрибутам R, так и к атрибутам S. Например, операция соединения может использоваться для формирования запроса названий тех стран, количество жителей которых превышает численность населения Мексики (см. таблицу 3.5).

1. R = πName, Pop(Country).

2. S = R. (S – полная копия отношения R).

3. Построим векторное произведение R x S. Схема отношения R x S выглядит так:

4. Применим условие: количество жителей страны в отношении S превышает численность населения Мексики.

img08.

Естественное соединение

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

1. Переименуем отношение Country в C, отношение River – в R.

2. Вычислим векторное произведение C x R.

3. Выполним соединение обоих отношений по атрибутам C.Name и R.Origin. Области определения этих двух атрибутов идентичны:

img09

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

5. Окончательный результат получается в результате выполнения операции проекции по атрибутам Name и Pop:

img10

Таблица 3.5. Результаты операций над множествами

3.3. ЭЛЕМЕНТАРНОЕ ВВЕДЕНИЕ В SQL

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

Язык SQL включает, по меньшей мере, два отдельных компонента: язык описания данных (ЯОД, англ. DDL, data description language) и язык модификации данных (ЯМД, англ. DML, data modification language)1. ЯОД используется для создания, удаления или изменения структур описания таблиц базы данных. На ЯМД формулируются запросы, инициирующие вставку и удаление строк из таблиц, заданных средствами ЯОД. Кроме того, SQL содержит другие операторы языка управления данными. Здесь мы изложим краткое введение в SQL. Наша цель – рассказать об этом языке в той мере, насколько это необходимо, чтобы читатель смог по достоинству оценить пространственные расширения, которые мы будем обсуждать в разделе 3.4. Более подробное и полное изложение SQL можно найти в любой книге, посвященной базам данных [Elmasri and Navathe, 2000; Ullman and Widom, 1999].

3.3.1. Язык описания данных

Создание реляционной схемы, создание и удаление таблиц выполняются посредством одного из компонентов SQL – языка описания данных. Например, ниже на языке SQL описана схема отношения City, введенная в разделе 3.2. Таблицы Country и River описаны в таблице 3.6.

CREATE      TABLE CITY {
            Name  VARCHAR(35),
            Country  VARCHAR(35),
            Pop  INT,
            Capital  CHAR(1),
            Shape  CHAR(13),
            PRIMARY KEY  Name }

Оператор CREATE TABLE применяется для описания отношений, входящих в реляционную схему. Именем таблицы является CITY. Таблица состоит из четырех столбцов, при этом должно быть указано название каждого столбца и соответствующий тип данных. Атрибуты название (Name) и страна (Country) должны быть строками ASCII-символов длиной не более 35 символов. Атрибут население (Population) имеет целочисленный тип, а столица (Capital) – это однобуквенный атрибут, принимающий либо значение Д (да), либо значение H (нет). В языке SQL92 возможные типы данных закреплены стандартом и не могут определяться пользователем. Мы не приводим полного набора типов данных, который можно найти в любой книге по базам данных. Наконец, первичным ключом отношения служит атрибут Name. Значит, каждая строка таблицы должна иметь уникальное значение этого атрибута. Таблицы, которые более не используются, можно удалить из базы данных, применяя команду Drop Table. Еще одна важная команда ЯОД – Alter Table, она позволяет вносить изменения в схему отношения.

Таблица 3.6. Схемы таблиц Country и River на языке SQL
CREATE   TABLE Country {
         Name  VARCHAR(35),
         Cont  VARCHAR(35),
         Pop  INT,
         GDP  INT,
         Shape  CHAR(15),
         PRIMARY KEY  
         (Name) }

(а) Схема Country

CREATE   TABLE River {
         Name  VARCHAR(35),
         Origin  VARCHAR(35),
         Length  INT,
         Shape  CHAR(15),
         PRIMARY KEY 
         (Name) }

(б) Схема River

3.3.2. Язык модификации данных

После того, как таблица создана по правилам ЯОД, она готова принимать данные. Эта задача, которую часто называют «заселением таблицы» («populating the table»), выполняется средствами другого компонента SQL – языка модификации данных. К примеру, следующий оператор добавляет к таблице River одну строку:

INSERT INTO River(Name, Origin, Length) 
    VALUES(‘Миссисипи’,‘США’, 6000) 

Если заданы не все атрибуты отношения, выполняется автоматическая подстановка значений по умолчанию. Наиболее часто по умолчанию используется «пустое» значение NULL. Попытка добавить в таблицу River другую строку с Name = ‘Миссисипи’ будет отвергнута СУБД в силу ограничений по первичному ключу, которые сформулированы на ЯОД.

Основная форма оператора удаления строк из таблицы имеет такой вид:

DELETE FROM < ТАБЛИЦА > WHERE < УСЛОВИЯ >

Например, следующий оператор удаляет из таблицы River строку, которую мы только что вставили.

DELETE FROM River
       WHERE Name = ‘Миссисипи’

3.3.3. Основная форма запроса на языке SQL

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

SELECT  имена-столбцов
FROM    отношения
WHERE   ограничения-на-кортежи

Эта форма эквивалентна выражению РА, состоящему из операций π, σ и |. SQL-оператор SELECT включает большее число предложений, относящихся к агрегированию (например, GROUP BY, HAVING), упорядочению результатов (например, ORDER BY) и т. д. Более того, SQL позволяет составлять вложенные запросы. Проиллюстрируем сказанное рядом примеров.

3.3.4. Примеры запросов на языке SQL

Приведем несколько примеров того, как составляются различные типы SQL-запросов. Мы хотим передать дух универсальности и мощи оператора SELECT. Все таблицы, используемые в запросах, входят в учебную базу данных WORLD, представленную в разделе 3.1.1. Результаты различных запросов можно найти в таблицах 3.7 и 3.8.

1. Запрос. Составить список всех городов в таблице City и тех стран, где эти города находятся.

SELECT    Ci.Name, Ci.Country
FROM      CITY Ci

Примечания. Выражение SQL эквивалентно операции проекции в РА. Предложение WHERE отсутствует в SQL-выражении потому, что в этом запросе не требуется использовать конструкцию, эквивалентную реляционно-алгебраической операции выборки. Отметим также необязательное применение каскадной «точечной» нотации. Таблица CITY переименована в Ci, и для обращения к ее атрибутам используются имена Ci.Name и Ci.Country.

2. Запрос. Составить список названий столиц, перечисленных в таблице CITY.

SELECT      *
FROM        CITY
WHERE       CAPITAL=‘Д’

Примечания. Это SQL-выражение эквивалентно операции выборки, введенной в РА. К сожалению, реляционно-алгебраическая операция выборки задается в языке SQL ключевым словом WHERE, а не предложением SELECT! Знак * в предложении SELECT означает, что должны быть перечислены все атрибуты, входящие в таблицу CITY.

3. Запрос. Составить список атрибутов стран, занесенных в отношение Country, где средняя продолжительность жизни меньше 70 лет.

SELECT    Co.Name, Co.Life-Exp
FROM        Country Co
WHERE     Co.Life-Exp < 70

Примечания. В терминах РА это выражение эквивалентно π ○ σ. Проецируемые атрибуты, в нашем примере это Co.Name и Co.Life-Exp, определяются предложением SELECT. Условие выборки задается ключевым словом WHERE.

4. Запрос. Составить список столичных городов и показателей численности населения тех стран, ВВП которых превышает один триллион долларов.

SELECT    Ci.Name, Co.Pop
FROM        City Ci, Country Co
WHERE     Ci.Country = Co.Name AND
          Co.GDP > 1000.0 AND
          Ci.Capital= ‘Д’

Примечания. Это неявный способ выражения операции соединения. SQL2 и SQL3 также поддерживают явную операцию JOIN. В таком случае обе таблицы City и Country сопоставляются по своим общим атрибутам Ci.country и Co.name. Более того, два условия выборки из таблиц City и Country задаются независимо друг от друга. Обратите внимание на то, как каскадная «точечная» нотация устраняет потенциальный конфликт, который может возникнуть в результате использования одинаковых имен атрибутов в обоих отношениях.

5. Запрос. Как называется столица и какова численность населения страны, где начинается река Св. Лаврентия?

SELECT      Ci.Name, Ci.Pop
FROM          City Ci, Country Co, River R
WHERE       R.Origin = Co.Name AND
            Co.Name = Ci.Country AND
            R.Name = ‘Св. Лаврентия’ AND
            Ci.Capital= ‘Д’

Примечания. Выполнение этого запроса требует соединения трех таблиц. Таблицы River и Country соединяются по атрибутам Origin и Name. Таблицы Country и City соединяются по атрибутам Name и Country. Соответственно имеются два условия выборки по таблицам River и City.

6. Запрос. Какова средняя численность населения нестоличных городов, перечисленных в таблице City?

SELECT     AVG(Ci.Pop)
FROM         City Ci
WHERE      Ci.Capital= ‘Н’

Примечания. AVG (среднее, англ. average) – это пример операции агрегирования, то есть расчета составного атрибута. Подобные операции отсутствуют в РА. Кроме AVG, есть и такие операции агрегирования, как COUNT, MAX, MIN и SUM. Операции агрегирования расширяют функциональность языка SQL, поскольку они позволяют производить вычисления над полученными данными.

7. Запрос. Найти средний ВВП каждого континента.

SELECT      Co.Cont, Avg(Co.GDP) AS Continent-GDP
FROM          Country Co
GROUP BY    Co.Cont

Примечания. Данный запрос иллюстрирует наиболее характерное отступление от базового формата SQL-запроса. Оно связано с наличием предложения GROUP BY, которое разбивает таблицу на основе указанного в нем атрибута. В приведенном примере Co.cont может принять одно из двух значений: СА и ЮА. Следовательно, таблица Country делится на две группы записей. Значение среднего ВВП (GDP) рассчитывается для каждой группы отдельно. Затем оно сохраняется так, как предписывает предложение SELECT, то есть в виде атрибута Continent-GDP (ВВП-континента).

8. Запрос. Для каждой страны, на территории которой расположены истоки хотя бы двух рек, определить длину самой короткой реки.

SELECT      R.Origin, MIN(R.length) AS Min-length
FROM           River R
GROUP BY    R.Origin
HAVING      COUNT(*) > 1

Примечания. Этот запрос подобен предыдущему. Отличие состоит в том, что предложение HAVING позволяет задавать условия выборки для различных групп, сформированных предложением GROUP BY. Таким образом, в рассмотрение принимаются только те группы, которые насчитывают более одного члена.

9. Запрос. Составить список стран, ВВП которых превосходит ВВП Канады.

SELECT    Co.Name
FROM        Country Co
WHERE     Co.GDP  > ANY (  SELECT Co1.GDP
                  FROM     Country Co1
                  WHERE    Co1.Name = ‘Канада’ )

Примечания. Это пример вложенного запроса. К таковым относятся запросы, содержащие другие, встроенные в них запросы. Вложенный запрос становится обязательным, когда перед расчетом запроса требуется создать промежуточную таблицу, которой не существует. Вложенный запрос обычно встречается в предложении WHERE, однако, кроме того, хотя и редко, может появляться в предложениях FROM и SELECT. ANY – оператор сравнения множеств. Полный обзор вложенных запросов вы сможете найти в любой книге по базам данных.

Таблица 3.7. Таблицы-результаты операций выборки, проекции и выборки-проекции

Название Страна Население (млн) Столица Очертания
Гавана Куба 2,1 Д Point
Вашингтон США 3,2 Д Point
Бразилиа Бразилия 1,5 Д Point
Оттава Канада 0,8 Д Point
Мехико Мексика 14,1 Д Point
Буэнос-Айрес Аргентина 10,75 Д Point

(а) Запрос 2. Выборка
Название Страна
Гавана Куба
Вашингтон США
Монтеррей Мексика
Торонто Канада
Бразилиа Бразилия
Росарио Аргентина
Оттава Канада
Мехико Мексика
Буэнос-Айрес Аргентина

(б) Запрос 1. Проекция
Название Продолжительность жизни
Мексика 69,36
Бразилия 65,60

(в) Запрос 3. Выборка и проекция

Таблица 3.8. Результаты выполнения примеров запросов
Ci.Name Co.Pop
Бразилиа 183,3
Вашингтон 270,0

(а) Запрос 4
Ci.Name Ci.Pop
Вашингтон 3,2

(б) Запрос 5
Среднее население
2,2

(в) Запрос 6
Континент ВВП континента
СА 2343,05
ЮА 676,1

(г) Запрос 7
Исток Мин-длина
США 1200

(д) Запрос 8
Co.Name
Мексика
Бразилия
США

(е) Запрос 9

3.3.5. Реляционная алгебра и язык SQL: резюме

РА – формальный язык запросов к базам данных. Обычно она не реализуется в коммерческих СУБД, однако образует ядро SQL. SQL – наиболее популярный и имеющий множество реализаций язык баз данных. Он включает два компонента: ЯОД и ЯМД. Схема таблиц базы данных определяется и заселяется средствами ЯОД. Запросы к базе данных фактически составляются на ЯМД. Мы сделали краткий обзор языка SQL. Более подробная информация приведена в любой книге по базам данных.

3.4. РАСШИРЕНИЕ SQL ДЛЯ ПРОСТРАНСТВЕННЫХ ДАННЫХ

Даже будучи мощными языками обработки запросов, РА и SQL имеют свои недостатки. Основным из них является то, что эти языки традиционно обеспечивали поддержку лишь простых типов данных, например целых чисел, дат и строк. Приложения пространственных БД должны работать со сложными типами, такими, как точки, линии и многоугольники. Производители баз данных ответили на это двояко: либо для хранения пространственной информации они стали использовать большие двоичные объекты (blobs, binary large objects), либо создали гибридные системы, в которых пространственные атрибуты сохраняются в файлах операционной системы средствами ГИС. SQL не может обрабатывать данные, хранимые как blob-атрибуты, и ответственность за обработку данных в форме больших двоичных объектов ложится на приложение [Stonebraker and Moore, 1997]. Это решение не является ни эффективным, ни эстетичным, поскольку данные зависят от кода приложения на некотором языке программирования. В гибридных системах пространственные атрибуты хранятся в виде отдельных файлов операционной системы и потому не могут пользоваться преимуществами традиционных служб базы данных, таких, как язык запросов, управление параллелизмом и поддержка индексирования.

Основное влияние на расширение возможностей СУБД в части поддержки пространственных (сложных) объектов оказали объектно-ориентированные системы. Программа, призванная обогатить реляционную базу данных объектно-ориентированными функциями, укладывается в общие рамки концепции ОР-СУБД. Ключевое свойство ОР-СУБД состоит в том, что такая система работает с SQL3/SQL99, версией языка SQL, которая, в свою очередь, поддерживает понятие пользовательских типов (как в языках Java или C++). Нашей задачей является изучение SQL3/SQL99 в той мере, насколько это необходимо для использования его как средства манипулирования пространственными данными и их выборки.

Главное требование к пространственному языку SQL лежит в плоскости обеспечения более высокого уровня абстракции в представлении пространственных данных путем введения понятий, более близких к нашему пониманию пространства [Egenhofer, 1994]. Для достижения этого вводится объектно-ориентированное понятие пользовательских АТД. АТД – это пользовательский тип и связанные с ним функции. Например, если мы располагаем информацией о земельных участках, хранящейся в базе данных в виде многоугольников, то полезным АТД могла бы стать комбинация типа «многоугольник» и нескольких связанных с ним функций (методов), скажем функции смежности adjacent. Функция adjacent может применяться по отношению к земельным участкам для того, чтобы определить, имеют ли они общие границы. Понятие «абстрактный» используется потому, что конечному пользователю нет необходимости знать детали реализации функций, связанных с этим типом. Все, что должны знать конечные пользователи, – это средства взаимодействия, то есть доступные функции и типы данных для входных параметров и конечного результата.

3.4.1. Стандарт OGIS как расширение языка SQL

Консорциум OGIS был создан ведущими производителями программного обеспечения с целью выработки промышленного стандарта, регламентирующего взаимодействие ГИС. Модель пространственных данных OGIS может быть встроена в большое количество различных языков программирования, например C, Java, SQL и т. д. В этом разделе мы остановимся на встраивании этой модели в язык SQL.

Стандарт OGIS основан на модели геометрических данных, представленной на рис. 2.2. Вспомним, что эта модель данных состоит из базового класса GEOMETRY, который является абстрактным, – иначе говоря, мы не можем описать объекты как экземпляры этого класса, – однако задает пространственную систему координат, применимую ко всем производным от него классам. Четыре основных класса, порожденных от предка GEOMETRY, – это Point, Curve, Surface и GeometryCollection. С каждым из этих классов связан набор операций, выполняемых над экземплярами классов. Некоторые важные операции, а также их назначение приведены в таблице 3.9.

Операции, определенные в стандарте OGIS, делятся на три категории.

Таблица 3.9. Примеры операций, входящих в стандарт OGIS [OGIS, 1999]
Базовые функции SpatialReference() Возвращает базовую систему координат геометрии
Envelope() Возвращает минимальный ортогональный ограничивающий прямоугольник геометрии
Export() Возвращает альтернативное представление геометрии
IsEmpty() Возвращает истинное значение, если геометрия является пустым множеством
IsSimple() Возвращает истинное значение, если геометрия является простой (без самопересечений)
Boundary() Возвращает границы геометрии
Топологические операции и операции над множествами Equal Возвращает истинное значение, если внутренние области и границы обеих геометрий пространственно равны
Disjoint Возвращает истинное значение, если границы и внутренняя область не пересекаются
Intersect Возвращает истинное значение, если геометрии имеют общие элементы
Touch Возвращает истинное значение, если границы двух поверхностей пересекаются, а внутренние области – нет
Cross Возвращает истинное значение, если внутренняя область поверхности пересекается кривой
Within Возвращает истинное значение, если внутренняя область одной геометрии не пересекается с внешней областью другой геометрии
Contains Проверяет, содержит ли одна геометрия другую
Overlap Возвращает истину, если внутренние области двух геометрий имеют непустое пересечение
Пространственный анализ Distance Возвращает кратчайшее расстояние между двумя геометриями
Buffer Возвращает геометрию, содержащую все точки, лежащие на указанном или меньшем расстоянии от данной геометрии
ConvexHull Возвращает наименьшее выпуклое геометрическое множество, заключающее в себе данную геометрию
Intersection Возвращает геометрическое пересечение двух геометрий
Union Возвращает геометрическое объединение двух геометрий
Difference Возвращает фрагмент геометрии, который не пересекается с другой геометрией
SymmDiff Возвращает фрагменты двух геометрий, которые не пересекаются друг с другом

1. Базовые операции, применимые ко всем геометрическим типам данных. Например, SpatialReference возвращает базовую систему координат, в которой описана геометрия объекта. К числу распространенных систем координат относятся широко известная система широт и долгот, а также часто используемая система Universal Traversal Mercator (UTM).

2. Операции, выявляющие топологические отношения между пространственными объектами. Например, операция overlap проверяет, имеют ли внутренние области двух объектов (см. главу 2) непустое множество пересечений.

3. Общие операции пространственного анализа. Например, операция distance возвращает кратчайшее расстояние между двумя пространственными объектами.

3.4.2. Ограничения стандарта

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

Даже в рамках объектной модели операции OGIS ограничиваются простыми запросами ВЫБОРКИ – ПРОЕКЦИИ – СОЕДИНЕНИЯ. Поддержка пространственных запросов агрегирования, содержащих предложения GROUP BY и HAVING, ставит ряд проблем (см. упражнение 4). Наконец, стандарт OGIS нацелен исключительно на базовые топологические и метрические пространственные соотношения. Отсутствует поддержка целого класса метрических операций, а именно операций на основе предиката направления (например, «на север», «на юг», «левая сторона», «передняя часть»). Также не поддерживаются динамические операции, которые основаны на очертаниях и понятии видимости и обсуждались в разделе 2.1.5.

3.5. ПРИМЕРЫ ЗАПРОСОВ, СОДЕРЖАЩИХ ПРОСТРАНСТВЕННЫЕ ОПЕРАЦИИ

Таблица 3.10. Основные таблицы
CREATE    TABLE Country(
          Name  
            varchar(30
          ),
          Cont 
            varchar(30
          ),
          Pop   Integer,
          GDP   Number,
          Shape Polygon);

(а)

CREATE    TABLE River(
          Name  
            varchar(30
          ),
          Origin  
            varchar(30
          ),
          Length Number,
          Shape 
                 LineString
          );

(б)

CREATE    TABLE City (
          Name  
             varchar(30
          ),
          Country 
             varchar(30
          ),
          Pop   integer,
          Shape Point );

(в)


Используя типы данных и операции стандарта OGIS, мы сформулируем SQL-запросы к базе данных World, иллюстрирующие пространственные соотношения между тремя сущностями: странами (Country), городами (City) и реками (River). Для начала переопределим реляционную схему, предполагая доступность в языке SQL типов данных и операций OGIS. Пересмотренная схема показана в таблице 3.10.

1. Запрос. Отыскать в таблице Country названия всех стран, которые являются соседями Соединенных Штатов.

SELECT    C1.Name AS "Соседи США"
FROM        Country C1, Country C2
WHERE     Touch(C1.Shape, C2.Shape) = 1 AND
          C2.Name = ‘США’

Примечания. Предикат Touch проверяет, являются ли два любых геометрических объекта смежными без наложения. Эта операция полезна для отыскания соседних объектов. Операция Touch – один из восьми топологических предикатов, описанных в стандарте OGIS. Приятно отметить одно из свойств топологических операций – их инвариантность по отношению ко многим геометрическим преобразованиям. В частности, на результаты топологических операций не влияет выбор координатной системы базы данных World.

Топологические операции применимы к большому числу различных сочетаний геометрических типов данных. Следовательно, в идеальной ситуации эти операции должны быть определены в стиле «перегрузки». К сожалению, многие объектно-реляционные СУБД не поддерживают таких понятий объектно-ориентированной парадигмы, как наследование классов и перегрузка операций. Поэтому в практических целях для каждой комбинации применяемых геометрических типов эти операции можно определить отдельно.

2. Запрос. Для всех рек, перечисленных в таблице River, определить страны, по которым они протекают.

SELECT    R.Name C.Name
FROM        River R, Country C
WHERE     Cross(R.Shape, C.Shape) = 1

Примечания. Cross – еще один топологический предикат. Чаще всего он используется для проверки наличия пересечения между объектами LineString и Polygon, как в этом примере, или между парой объектов LineString.

3. Запрос. Какой город, содержащийся в таблице City, ближе других расположен ко всем рекам, перечисленным в таблице River?

SELECT    C1.Name,  R1.Name
FROM        City C1,    River R1
WHERE     Distance    (C1.Shape, R1.Shape)    <
            ALL (SELECT Distance(C2.Shape, R1.Shape)
            FROM        City C2
            WHERE       C1.Name <> C2.Name
                        )

Примечания. Distance – двухместная операция вещественного типа. Используется в предложении WHERE и еще раз – в предложении SELECT подзапроса. Функция Distance описана для любых комбинаций геометрических объектов.

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

SELECT    Ci.Name
FROM        City Ci, River R
WHERE     Overlap(Ci.Shape, Buffer(R.Shape,300)) = 1 AND
          R.Name = ‘Св. Лаврентия’

Примечания. Буфером (Buffer) геометрического объекта называется центрированная относительно объекта геометрическая область, размер которой определяется параметром операции Buffer. В данном примере размер буферной области определяется запросом. Операция нахождения буфера используется во многих приложениях ГИС, включая противопаводочные мероприятия, а также муниципальные правила городского и сельского районирования. Графическое изображение операции нахождения буфера показано на рис. 3.2. Города A и B здесь, вероятно, будут затронуты наводнением, тогда как город C останется за пределами зоны подтопления.

img11

Рис. 3.2. Буфер реки и точки внутри и вне буфера

5. Запрос. Составить список названий, численности населения и площади стран, содержащихся в таблице Country.

SELECT   C.Name, C.Pop, Area(C.Shape) AS "Площадь"
FROM       Country C

Примечания. Этот запрос иллюстрирует применение функции Area. Данная функция применяется только для геометрических типов Polygon и MultiPolygon. Очевидно, что вычисление результата Area зависит от базовой системы координат базы данных World. Например, если очертания в кортежах таблицы Country заданы широтой и долготой, то расчету значения Area должно предшествовать промежуточное преобразование координат. То же справедливо для функций Distance и Length.

6. Запрос. Составить список длин рек в пределах каждой страны, по которой они протекают.

SELECT    R.Name, C.Name, Length(
            Intersection(R.Shape, C.Shape))
          AS "Length"
FROM        River R, Country C
WHERE     Cross(R.Shape, C.Shape) = 1

Примечания. Значение, возвращаемое двухместной операцией Intersection, имеет геометрический тип. Операция Intersection отличается от функции Intersects, которая играет роль топологического предиката, определяющего, пересекаются ли две геометрии. Результат операции Intersection над объектами типа LineString и Polygon может иметь тип Point или LineString. Если река пересекает территорию страны, то результат будет иметь тип LineString. В этом случае функция Length возвратит ненулевую длину реки в каждой стране, по которой та протекает.

7. Запрос. Для всех стран составить список ВВП и расстояний от столичных городов до экватора.

SELECT    Co.GDP, Distance(Point(0,Ci.Shape.y),Ci.Shape)
          AS "Расстояние"
FROM        Country Co, City Ci
WHERE     Co.Name = Ci.Country AND
          Ci.Capital = ‘Д’

Примечания. Поиск неявных соотношений между наборами данных, хранящимися в базе данных, не входит в функции стандартных СУБД. Современные системы баз данных развиваются в направлении оперативной обработки транзакций (OLTP), в то время как приведенный запрос, в том виде, как он сформулирован, относится к сфере аналитической обработки (OLAP). Саму технологию OLAP относят к технологиям добычи данных, нам предстоит рассмотреть эту тему в главе 8. Лучшее, что мы можем сделать на данный момент, – перечислить все столицы и их удаленность от экватора.

Point(0,Ci.Shape.y) – это точка на экваторе, имеющая ту же долготу, что и текущая столица, представленная атрибутом Ci.Name. Результаты показаны в таблице 3.11.

8. Запрос. Составить список всех стран, упорядоченный по количеству государств-соседей.

SELECT    Co.Name, Count(Co1.Name)
FROM        Country Co, Country Co1
WHERE     Touch(Co.Shape, Co1.Shape)
GROUP BY  Co.Name
ORDER BY  Count(Co1.Name)

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

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

SELECT    Co.Name
FROM        Country Co, Country Co1
WHERE     Touch(Co.Shape, Co1.Shape))
GROUP BY  Co.Name
HAVING    Count(Co1.Name) = 1
SELECT    Co.Name
FROM        Country Co
WHERE     Co.Name IN
          (SELECT   Co.Name
          FROM      Country Co, Country Co1
          WHERE     Touch(Co.Shape, Co1.Shape)
          GROUP BY  Co.Name
          HAVING    Count(*) = 1)

Примечания. Здесь мы имеем вложенный запрос, находящийся в предложении FROM. Результатом запроса в конструкции FROM является таблица, состоящая из пар стран, которые являются соседями. Предложение GROUP BY делит новую таблицу на части в соответствии с названиями государств. Наконец, HAVING инициирует принудительное объединение результатов выборки в пары с теми странами, которые имеют только одного соседа. Ключевое слово HAVING играет ту же роль, что и WHERE, за исключением одного: HAVING должно включать такие функции агрегирования, как count, sum, max и min.

10. Запрос. Какая страна имеет наибольшее число соседей?

CREATE VIEW Neighbor AS
SELECT      Co.Name, Count(Co1.Name) AS num_neighbors
FROM            Country Co, Country Co1
WHERE       Touch(Co.Shape, Co1.Shape)
GROUP BY    Co.Name
SELECT    Co.Name, num_neighbors
FROM        Neighbor
WHERE     num_neighbor = (SELECT Max(num_neighbors)
          FROM Neighbor)

Примечания. Этот запрос демонстрирует применение представлений (views) с целью упрощения сложных запросов. Первый запрос (представление) вычисляет количество соседей каждой страны. Представление создает виртуальную таблицу, которая в последующих запросах может использоваться как обычная таблица. Второй запрос производит выборку страны с наибольшим количеством соседей из представления Neighbor (Соседи).

Таблица 3.11. Результаты запроса 7
Co.Name Co.GDP Расст-до-экватора (в км)
Гавана 16,9 2562
Вашингтон 8003 4324
Бразилиа 1004 1756
Оттава 658 5005
Мехико 694,3 2161
Буэнос-Айрес 348,2 3854

3.6. НАПРАВЛЕНИЯ РАЗВИТИЯ: ОБЪЕКТНО-ОРИЕНТИРОВАННЫЙ ДИАЛЕКТ SQL

Стандарт OGIS содержит описание типов данных и связанных с ними операций, которые считаются необходимыми для таких пространственных приложений, как ГИС. Например, тип данных Point обладает важной операцией Distance, вычисляющей расстояние между двумя точками. Операция length в отношении типа Point оказывается семантически некорректной. Эти наблюдения по своему характеру напоминают мысль о том, что операция concatenation (сцепление) более осмысленна для типа данных Character, нежели, скажем, для типа Integer.

В реляционных базах данных набор типов фиксирован. В объектно-реляционных и объектно-ориентированных базах данных подобное ограничение ослаблено, и сделано это с целью поддержки пользовательских типов данных. Даже несмотря на то, что подобная возможность оборачивается явным преимуществом, особенно при работе с такими нетрадиционными приложениями баз данных, как, например, ГИС, бремя описания синтаксически и семантически корректных типов данных теперь лежит на разработчике приложения базы данных. Чтобы взять часть этого бремени на себя, производители коммерческих баз данных начали создавать «пакеты», нацеленные на конкретные приложения и предоставляющие пользователям баз данных средства «бесшовного» интерфейса. Например, корпорация Oracle предлагает ориентированный на ГИС пакет под названием Spatial Data Cartridge.

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

3.6.1. Взгляд на SQL3

Язык SQL3/SQL99 предлагает два основных расширения SQL2/SQL92, принятой на сегодняшний день черновой версией SQL.

1. АТД. АТД может быть описан при помощи оператора CREATE TYPE. Как и классы в объектно-ориентированной технологии, АТД состоит из атрибутов и функций-членов, предназначенных для доступа к значениям атрибутов. Функции-члены могут изменять значения атрибутов типа данных, а значит, могут изменять и состояние базы данных. АТД можно использовать как тип столбца реляционной схемы. Для доступа к значению, которое содержится в АТД, нужно вызвать функцию-член, описанную в операторе CREATE TYPE. Например, следующий код порождает тип Point и описывает одну функцию-член Distance:

CREATE TYPE Point (
    x     NUMBER,
    y     NUMBER,
  FUNCTION    Distance(:u Point,:v Point)
          RETURNS NUMBER
                 );

Двоеточия перед u и v указывают, что это – локальные переменные.

2. Тип строки. Тип строки (row type) – это тип отношения. Тип строки задает схему отношения. Например, следующий оператор объявляет тип строки с именем Point:

CREATE ROW TYPE   Point (
      x     NUMBER,
      y     NUMBER );

Теперь можно создавать таблицу, которая содержит экземпляры типа строки. Например:

CREATE TABLE Pointtable of TYPE Point;

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

3.6.2. Объектно-реляционная схема

Oracle8 – это ОР-СУБД, разработанная Oracle Corporation. Подобные продукты предлагаются и другими производителями баз данных, например фирмой IBM. В ОР-СУБД Oracle частично реализован стандарт SQL3. АТД носит в этой системе название «объектного типа» («object type»).

Рассмотрим, как в Oracle8 построены три базовых типа пространственных данных: Point, LineString и Polygon.

CREATE  TYPE Point AS OBJECT (
        x   NUMBER,
        y   NUMBER,
  MEMBER FUNCTION Distance(P2 IN Point) RETURN NUMBER,
  PRAGMA RESTRICT_REFERENCES(Distance, WNDS));

Тип Point имеет два атрибута x и y, а также одну функцию-член Distance. PRAGMA указывает на то, что функция Distance не изменяет состояние базы данных: WNDS (Write No Database State). Разумеется, в стандарте OGIS описано большое количество других операций, относящихся к типу Point, однако для простоты мы показали только одну. После создания тип Point может использоваться как тип атрибута в отношениях. Например, схему отношения City можно описать так:

CREATE  TABLE City (
        Name  varchar(30),
        Country    varchar(35),
        Pop    int,
        Capital    char(1),
        Shape Point );

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

INSERT INTO CITY(‘Бразилиа’, ‘Бразилия’, 1.5, ‘Д’,
         Point(-55.4,-23.2));

Создание типа данных LineString несколько сложнее аналогичной процедуры для типа Point. Начнем с создания промежуточного типа LineType:

CREATE TYPE LineType AS VARRAY(500) OF Point;

LineType – это массив переменного размера, который состоит не более чем из 500 элементов типа Point. Если тип объявлен как Varray, то функции-члены этого типа описывать запрещено. Поэтому сконструируем другой тип LineString:

CREATE  TYPE LineString AS OBJECT (
        Num_of_Points INT,
        Geometry LineType,
        MEMBER FUNCTION Length(SELF IN) RETURN NUMBER,
        PRAGMA RESTRICT_REFERENCES(Length, WNDS));

Атрибут Num_of_Points (количество точек) содержит размер (число элементов типа Point) каждого экземпляра типа LineString. Теперь мы готовы к заданию схемы таблицы River:

CREATE  TABLE River(
        Name  varchar(30),
        Origin  varchar(30),
        Length  number,
        Shape LineString );

При добавлении данных в таблицу River нужно отслеживать различные используемые типы данных.

INSERT INTO RIVER(‘Миссисипи’, ‘США’, 6000,
    LineString(3, LineType(Point(1,1),Point(1,2),
    Point(2,3)))

Тип Polygon аналогичен типу LineString. Последовательность операций описания типов, создания таблицы и добавления данных приведена в таблице 3.12.

Таблица 3.12. Последовательность операций при создании таблицы Country
CREATE TYPE PolyType AS VARRAY(500) OF Point

(а)

CREATE  TYPE Polygon AS OBJECT (
        Num_of_Points INT,
        Geometry PolyType ,
        MEMBER FUNCTION Area(SELF IN) RETURN NUMBER,
        PRAGMA RESTRICT_REFERENCES(Length, WNDS));

(б)

CREATE  TABLE  Country(
        Name  varchar(30),
        Cont  varchar(30),
        Pop  int,
        GDP  number,
        Life-Exp  number,
        Shape  LineString );

(в)

INSERT INTO Country(‘Мексика’, ‘СА’, 107.5, 694.3, 69.36,
  Polygon(23, Polytype(Point(1,1), ..., Point(1,1)))

(г)

3.6.3. Примеры запросов

1. Запрос. Перечислить все пары городов из таблицы City и расстояния между ними.

SELECT  C1.Name, C1.Distance(C2.Shape) AS ‘‘Расстояние’’
FROM       City C1, City C2
WHERE   C1.Name <> C2.Name

Примечания. Обратите внимание на объектно-ориентированную форму записи функции Distance в предложении SELECT. Сравните ее с обычной нотацией, использованной в разделе 3.5: Distance(C1.Shape, C2.Shape). Условие в предложении WHERE гарантирует, что функция Distance не применяется по отношению к двум копиям одного и того же города.

2. Запрос. Проверить правильность вычисления длин рек, которые приведены в таблице River, на основе геометрической информации в атрибуте Shape.

SELECT  R.Name, R.Length, R.Length() 
                 AS ‘‘Рассчитанная длина’’
FROM        River R

Примечания. Этот запрос используется для проверки корректности данных. Длины рек уже содержатся в таблице River в виде атрибута Length. Используя функцию Length(), мы можем убедиться в целостности данных таблицы.

3. Запрос. Привести названия, численность населения и площадь всех стран, граничащих с США.

SELECT  C2.Name, C2.Pop, C2.Area() AS ‘‘Площадь’’
FROM      Country C1, Country C2
WHERE   C1.Name = ‘США’ AND
        C1.Touch(C2.Shape) = 1

Примечания. Area() – естественная функция, поддерживаемая АТД Polygon. Наряду с ней запрос также использует топологический предикат Touch.

3.7. РЕЗЮМЕ

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

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

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

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

SQL3/SQL 1999 представляет собой стандартизированную платформу объектно-реляционного расширения языка SQL. Эта платформа не ориентирована исключительно на ГИС или пространственные базы данных, ее действие распространяется на объектно-реляционные базы данных общего назначения. Самый естественный вариант ее внедрения состоит в реализации стандарта OGIS в составе подмножества языка SQL3.

Библиографические заметки

3.1, 3.2, 3.3. Полное изложение реляционной алгебры и SQL можно найти в любой книге, посвященной введению в базы данных, в том числе в работах [Elmasri and Navathe, 2000; Ramakrishnan, 1998; Ullman and Widom, 1999].

3.4, 3.5. Расширения SQL для пространственных приложений изложены в [Egenhofer, 1994]. Нормативный документ консорциума OGIS [OpenGIS, 1998] представляет собой попытку согласования с языком SQL различных пространственных расширений. Примеры языков запросов для поддержки анализа пространственных данных приведены в статье [Lin and Huang, 2001].

3.6. SQL 1999/SQL3 – принятый стандарт объектно-реляционного расширения SQL. Подмножества этого стандарта уже реализованы в коммерческих продуктах, включая Oracle8 компании Oracle и DB2 корпорации IBM.

УПРАЖНЕНИЯ

Все запросы в упражнениях 1 и 2 относятся к информации, приведенной в таблице 3.1.

1. Выразите следующие запросы на языке реляционной алгебры.

  1. Найти все страны, ВВП которых выше 500 млрд дол., но ниже 1 трлн дол.
  2. Привести среднюю продолжительность жизни в странах, на территории которых расположены истоки рек.
  3. Найти все страны, расположенные в Южной Америке либо имеющие население менее 2 млн чел.
  4. Составить список городов, находящихся за пределами Южной Америки.

2. Выразите на языке SQL запросы, перечисленные в упражнении 1.

3. Выразите следующие запросы на языке SQL.

  1. Вычислить количество стран, в которых проживает менее 100 млн чел.
  2. Найти в Северной Америке государство с наименьшим ВВП. Не использовать функцию Min. Указание: вложенный запрос.
  3. Составить список стран, расположенных в Северной Америке или имеющих столицы с числом жителей менее 5 млн чел.
  4. Найти страну, занимающую второе место по уровню ВВП.

4. Reclassify (см. раздел 2.1.5) – это функция агрегирования, которая объединяет пространственные геометрические объекты на основе непространственных атрибутов. Она создает новые объекты из уже существующих, в общем случае, путем удаления внутренних границ между соседними многоугольниками, в которых выбранный атрибут принимает одинаковое значение. Можно ли выразить операцию Reclassify при помощи операций OGIS и языка SQL92 с поддержкой пространственных типов данных? Поясните ответ.

5. Рассмотрим геометрическую модель данных на рис. 2.2. Принимая, что в «мировом» масштабе города представляются точечными типами данных, ответьте на вопрос: какой тип данных нужно использовать для представления стран мира? Примечание. Сингапур, Ватикан и Монако – это государства. Каковы будут результаты реализации пространственных функций, рекомендованных стандартом OGIS?

6. Автор статьи [Egenhofer, 1994] предлагает список требований к расширениям языка SQL для пространственных приложений. Эти требования перечислены ниже. Какие из рекомендаций вошли в стандарт OGIS SQL? Назовите возможные причины того, что внедрение прочих рекомендаций было отложено.
Пространственные АТД Пространственная иерархия абстрактных типов данных и операции над ними
Графическое представление Естественная среда взаимодействия с пространственными данными
Сочетание результатов Сочетание результатов последовательности запросов
Контекст Погружение результата в тот или иной контекст путем включения информации, которая не запрашивалась в явном виде
Изучение контекста Обеспечение механизмов управления процессом построения карты
Выбор методом указания Постановка и задание ограничений путем указания на карту
Манипуляции с изображением Изменение графического представления пространственных объектов и их частей
Легенда Описательная легенда
Метки Метки для лучшего понимания изображения
Выбор масштаба карты Построенная карта должна дать пользователю возможность применять свои навыки в интерпретации фактического размера изображенных объектов; выбор указанного масштаба визуализации
Интересующая область Средства сужения интересующей области до конкретного географического района

7. Стандарт OGIS включает набор топологических пространственных предикатов. Как следует расширить стандарт с целью включения в него предикатов направления, таких, как восток, север, северо-восток и т. д.? Заметим, что предикаты направления могут допускать нечеткую формулировку: «Где заканчивается северо-восток и начинается восток?»

8. Это упражнение связано с исследованием пространственно-расширенной модели девяти пересечений DE-9IM (dimension-extended nine-intersection model). Она расширяет описанную в главе 2 модель девяти пересечений Эгенхофера. Матрица-шаблон модели DE-9IM показана ниже.

img12.

Ключевое различие между 9IM и DE-9IM состоит в том, что проверка каждого элемента матрицы на пустоту заменяется в модели DE-9IM требованием наличия лишь информации о размерности геометрического объекта. Размерность плоских двухмерных объектов может принимать четыре значения: –1 для пустого множества, 0 для точек, 1 для линий и 2 для объектов ненулевой площади. Во многих случаях значение элемента матрицы не имеет значения. Приведем список значений, которые могут содержаться в элементах матрицы.

T: X и Y должны пересекаться: = 0, 1, 2. X и Y – это либо внутренние, либо внешние области, либо границы A и B соответственно.

F: = –1. X и Y должны быть непересекающимися.

*: Существование пересечения не имеет значения. = {–1, 0, 1, 2}.

0: = 0.

1: = 1.

2: = 2.

Ниже приведена сигнатурная матрица (signature matrix) двух равных объектов.

img13

  1. Какой вид имеет сигнатурная матрица (матрицы) топологических операций touch и cross? Заметим, что сигнатурная матрица зависит от комбинации типов данных. Сигнатурная матрица комбинации точка/точка отличается от аналогичной матрицы комбинации составной многоугольник/составной многоугольник.
  2. Какую операцию (и комбинацию типов данных) представляет следующая сигнатурная матрица?
  3. img14

  4. Проанализируйте примеры, приведенные на рис. 3.3. Каковы их сигнатурные матрицы в моделях 9IM и DE-9IM? Действительно ли DE-9IM превосходит 9IM? Выскажите свое мнение.

img15
Рис. 3.3. Примеры объектов [Clementini and Felice, 1995]

9. Выразите следующие запросы на языке SQL, используя неточечные типы данных и функции стандарта OGIS.

  1. Перечислить все города из таблицы City, находящиеся в пяти тысячах миль от Вашингтона.
  2. Какова длина участков реки Парана в Аргентине и Бразилии?
  3. Имеют ли Аргентина и Бразилия общую границу?
  4. Составить список стран, которые полностью лежат к югу от экватора.

10. Дана схема:

RIVER [РЕКИ] (NAME [НАЗВАНИЕ]:char, 
           FLOOD-PLAIN [ПОЙМА]:polygon, 
           GEOMETRY [ГЕОМЕТРИЯ]:linestring)
ROAD [ДОРОГИ] (ID [НОМЕР]:char, NAME [НАЗВАНИЕ]:char, 
           TYPE [ТИП]:char, 
           GEOMETRY [ГЕОМЕТРИЯ]:linestring)
FOREST [ЛЕСА] (NAME [НАЗВАНИЕ]:char, 
           GEOMETRY [ГЕОМЕТРИЯ]:polygon)
LAND-PARCELS [ЗЕМЕЛЬНЫЕ-УЧАСТКИ] (ID [НОМЕР]:integer, 
           GEOMETRY [ГЕОМЕТРИЯ]:polygon, county[округ]:char)

Используя типы данных и операции, закрепленные в стандарте OGIS, переведите следующие запросы на язык SQL.

  1. Составить список всех рек, протекающих по территории леса Итаска Стейт-Форест.
  2. Перечислить все гудронные дороги, пересекающие Фрэнсис-Форест.
  3. Найти все дороги, которые проходят в пределах поймы реки Монтана и могут затапливаться во время наводнения.
  4. В двухмильной зоне от реки Ред-Ривер и в пяти милях от государственного парка «Биг-Три» запрещено городское строительство. Найти земельные участки, которые нельзя застраивать, а также округа, на территории которых эти участки находятся.
  5. Река служит участком границы округа.

11. Изучите такие компиляторы, как YACC (Yet Another Compiler Compiler). Разработайте синтаксическую схему создания операторов описания данных на языке SQL3, пользуясь аннотированными пиктограммами на диаграммах «сущность-связь».

12. Каким должен быть подход к моделированию следующих пространственных отношений при использовании модели девяти пересечений или топологических операций OGIS?

  1. Река (LineString) начинается на территории округа (Polygon).
  2. Страна (например, государство Ватикан) полностью окружена территорией одной другой страны (например, Италии).
  3. Одна река (например, Миссури) впадает в другую (например, Миссисипи).
  4. Лес является частью другого лесного массива.

13. Обратитесь к примерам запросов на языке РА, которые приведены в Приложении, посвященном базе данных «Государственный парк». Составьте SQL-выражения,  соответствующие каждому запросу на языке РА.

14. Перечертите приведенную на рис. 3.4 диаграмму «сущность-связь», используя пиктограммы. Как в новой диаграмме следует представить атрибуты Fishing-Opener (Открытие-сезона) и Distance (Расстояние)? Создайте таблицы, преобразуя полученную в результате диаграмму «сущность-связь» с использованием конструкций SQL3/OGIS.

15. Проанализируйте проекты таблиц на рис. 1.3 и 1.4. Опишите SQL-запросы для вычисления пространственных свойств (например, площади, периметра) переписных участков, используя все способы представления. Какое представление позволяет получить более простые запросы?

16. Вернитесь к Java-программе из раздела 2.1.6. Напишите на языке Java программу для выполнения пространственных запросов, перечисленных в разделе 3.6.3. Сравните составление запросов к пространственным наборам данных на языках Java и SQL3/OGIS.

17. Определите средствами SQL3 пользовательские типы данных, предназначенные для представления геометрических типов составных данных стандарта OGIS.

18.Вернитесь к реляционной схеме «Государственного парка» в примере раздела 2.2.3. Кратко опишите SQL-операторы ЯМД для создания соответствующих таблиц при помощи пространственного типа данных OGIS.

19. Проанализируйте запросы на основе информации об очертаниях объектов – например, перечислить страны, границы которых похожи на дамский сапог, или переписные участки квадратной формы. Предложите расширение языка SQL3/OGIS для поддержки подобных запросов.

20. Проанализируйте запросы на основе информации о видимости например, перечислить объекты, которые видны (не загораживаются) при данном положении наблюдателя. Предложите набор типов данных и операций, образующих расширение SQL3/OGIS для поддержки запросов такого вида.

3.8. Приложение: БАЗА ДАННЫХ «ГОСУДАРСТВЕННЫЙ ПАРК»

База данных State Park (Государственный парк) состоит из двух сущностей: Park (Парк) и Lake (Озеро). Атрибуты этих двух сущностей и связей показаны на рис. 3.4. Отображение диаграммы «сущность-связь» на реляционную схему приведено ниже. Сущности и связи между ними представлены в таблице 3.13.

StatePark [ГосПарки] (Sid [П-номер]: integer, 
                      Sname [П-название]: string, 
                      Area [Площадь]: float, 
                      Distance [Расстояние]: float)
Lake [Озера] (Lid [О-номер]: integer, 
              Lname [О-название]: string, 
              Depth [Глубина]: float, 
              Main-Catch [Основной-Улов]: string)
ParkLake [ОзераПарков] (Lid [О-номер]: integer, 
                        Sid [П-номер]: integer, 
                  Fishing-Opener [Открытие-Сезона]: date)

Данная схема представляет три сущности: StatePark, Lake и ParkLake. Сущность StatePark представляет все государственные парки штата Миннесота, а ее атрибутами являются уникальный национальный идентификатор Sid, название парка Sname, площадь парка в квадратных километрах Area, а также расстояние от Миннеаполиса – Distance. Сущность Lake также имеет уникальный идентификатор Lid и название Lname; средняя глубина озера хранится в атрибуте Depth, самый распространенный в озере вид рыб – в атрибуте Main-catch. Сущность ParkLake применяется для соединения запросов к обеим сущностям – StatePark и Lake. Она определяет озера, которые расположены на территории государственных парков. Ее атрибутами являются Lid, Sid, а также дата открытия сезона рыбной ловли на озере – Fishing-Opener. В данном случае мы предполагаем, что на разных озерах Открытие-Сезона происходит в разное время.

img16

Таблица 3.13. Таблицы базы данных StatePark
Park Sid Sname Area Distance

S1 Итаска 150,0 52
S2 Вудбери 255,0 75
S3 Брайтон 175,0 300

(а) Park
Lake Lid Lname Depth Main-Catch

100 Лино 20,0 Плотва
200 Часка 30,0 Форель
300 Суссекс 45,0 Плотва
400 Тодд 28,0 Окунь

(б) Lake
ParkLake Lid Sid Fishing-Opener

100 S1 15.05
200 S1 15.05
300 S3 01.06

(в) ParkLake

3.8.1. Примеры запросов на языке реляционной алгебры

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

Запрос. Найти название государственного парка, где расположено озеро с номером 100.

img17

Примечания. Начнем с выборки множества кортежей отношения ParkLake, имеющих значение атрибута Lid, равное 100. Множество-результат подвергается естественному соединению по ключу Sid с отношением StatePark. Результат проецируется на атрибут Название отношения StatePark, то есть Spname. Пользуясь оператором переименования ρ, этот запрос можно разбить на части. Оператор переименования применяется для присваивания названия промежуточному отношению, появляющемуся в ходе вычисления сложного запроса. Также его можно использовать для переименования атрибутов отношений. Например,

img18

переименовывает отношение СтароеНазв в НовоеНазв. Кроме того, первый атрибут отношения НовоеНазв, считая слева направо, получает имя Att1.

Пользуясь этим соглашением об именовании отношений, можно разбить этот запрос на части:

img19

Альтернативная формулировка запроса выглядит так:

img20

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

1. Запрос. Найти названия государственных парков с озерами, где основной улов составляет форель.

img21

Примечания. Здесь последовательно применяются два оператора соединения. Однако сначала мы сокращаем размер множества путем предварительной выборки всех озер, где основным уловом является форель. Затем соединяем результат по ключу Lid с отношением ParkLake. После этого следует другое соединение с отношением StatePark по ключу Sid. Наконец, мы проецируем ответ на название парка (Spname).

2. Запрос. Найти виды рыб, которые являются основным уловом в озерах, расположенных на территории государственного парка Итаска.

img22

Примечание. Этот запрос очень похож на предыдущий.

Запрос. Найти названия государственных парков, где есть хотя бы одно озеро.

img23

Примечание. Соединение по атрибуту Sid создает промежуточное отношение, в котором кортежи из StatePark присоединяются к кортежам ParkLake. Затем результат проецируется на атрибут Spname.

3. Запрос. Составить список государственных парков, основной улов в озерах которых – это окунь или плотва.

img24

Примечания. Здесь мы впервые используем оператор объединения. Сначала производится выборка озер, где основной улов составляют окунь или плотва. Затем выполняется соединение по атрибуту Lid с отношением ParkLake и по атрибуту Sid с отношением StatePark. Результат получен проекцией по атрибуту Spname.

4. Запрос. Определить названия государственных парков, в которых есть озера, где основным уловом являются и окунь, и плотва.

img25

Примечание. Формулировка этого запроса очевидна.

5. Запрос. Определить названия государственных парков, в которых есть, по крайней мере, два озера.

img26

6. Запрос. Определить идентификаторы, то есть атрибуты Sid, государственных парков, которые находятся на расстоянии не менее 50 миль от Миннеаполиса и в озерах которых основным уловом не является форель.

img27

Примечание

1 Существует и другое название этого компонента SQL – язык манипулирования данными (DML, data manipulation language). – Примеч. пер.

Новости мира IT:

Архив новостей

Последние комментарии:

Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...