Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

2007 г.

История и актуальные проблемы темпоральных баз данных

Б.Б. Костенко, Московский Государственный Университет им. М.В. Ломоносова
С.Д. Кузнецов, Институт системного программирования РАН

Страницы: назад 1 2 3 4

8. Актуальные вопросы и задачи, перспективы исследований

При описании темпоральных систем уже подчеркивалось наличие отдельных проблем, которые должны быть решены прежде, чем будет создана полноценная темпоральная СУБД. С другой стороны, опыт технологии Oracle Flashback показывает, что для конкретной задачи можно реализовать специализированную темпоральную поддержку. Кроме того, существует множество проблем и задач, которые могут быть решены в рамках исследований в области темпоральных и пространственно-временных баз данных [RHE+04]. В этом разделе перечисляются некоторые из подобных задач.

8.1. Эффективные пользовательские интерфейсы и представления

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

8.2. Извлечение данных и знаний из пространственно-временных систем

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

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

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

8.3. Новый уровень мобильности

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

8.4. Пространственное разрежение

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

8.5. Нетрадиционные методы доступа

Для решения нетрадиционных проблем пространственно-временных баз данных требуются новые подходы. Например, во многих работах, посвященных движущимся объектам, для моделирования областей пространства используются графы, а не евклидово представление пространства. Вместо евклидовых расстояний могут использоваться расстояния на дороге. Методы доступа к подобным данным должны соответствовать специфике проблемы. Исследования методов доступа к пространственно-временным данным, главным образом, фокусируются на двух аспектах: (1) хранение и поиск исторической информации и (2) предсказание будущего. Для решения первой задачи было предложено несколько индексных структур, минимизирующих объем хранимых данных и стоимость выполнения запроса. Подобные индексы обычно основываются на многоверсионных или трехмерных вариациях R-деревьев. Методы для предсказания будущего основаны на том предположении, что в дополнение к текущей позиции объектов известны и скорости их движения. Целью является нахождение объектов, которые будут удовлетворять пространственным условиям в некоторый момент (или интервал времени) будущего на основе заданных текущих скоростей движения (например, «на основе текущей информации найти все машины, которые будут в центре города через 10 минут»). Индексы, практически пригодные для предсказания будущего, основываются на TPR-деревьях и их вариациях (также являющих развитием идей R-деревьев).

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

8.6. Новые типы пространственно-временных запросов

Существует множество областей, где могут быть эффективно использованы пространственно-временные базы данных, но для решения задач оказываются недостаточными возможности формулировки запросов языка SQL. К запросам нового типа относятся непрерывные запросы, где результат сильно зависит от темпорального контекста. Примером непрерывного запроса может служить следующий: «на основе текущего положения и скорости автомобиля найти две ближайшие АЗС в течение следующих пяти минут?» Результат в форме <{A, B}, [0,1)>, <{B,C}, [1,5)> означает, что АЗС A и B будут ближайшими в интервале времени [0,1), а АЗС B и C – в интервале [1,5). Заметим, что соответствующий моментальный запрос («какие две АЗС являются сейчас ближайшими?») в высоко динамичном окружении обычно будет бессмысленным: если точка запроса или объект базы данных двигается, то результат может сразу стать недействительным.

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

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

8.7. Приближенные запросы

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

8.8. Неопределенности при обработке «неточных» данных

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

9. Итоги и перспективы

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

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

10. Литература

[AJS95] Arie Segev, Christian S. Jensen, and Richard T. Snodgrass. Report on The 1995 International Workshop on Temporal Databases. ACM SIGMOD Record 24(4), December 1995
[BBJ+97] J. Bair, M. H. Böhlen, C. S. Jensen, and R. T. Snodgrass. Notions of Upward Compatibility of Temporal Query Languages. Wirtschaftsinformatik, 39(1):25–34, February 1997
[BBJ98] M. H. Böhlen, R. Busato, and C. S. Jensen. Point-Versus Interval-Based Temporal DataModels. In Proceedings of the Fourteenth International Conference on Data Engineering, pp. 192–200, Orlando, Florida, February 1998
[Böh95] Michael H. Böhlen. Temporal Database System Implementations. ACM SIGMOD Record 24(4), December 1995
[BZ82] J. Ben-Zvi, “The Time Relational Model,” PhD thesis, Computer Science Dept., UCLA, 1982
[CDI+97] J. Clifford, C. E. Dyreson, T. Isakowitz, C. .S. Jensen, and R. T. Snodgrass. On the Semantics of ‘Now’ in Databases. ACM Transactions on Database Systems, 22(2), June 1997
[DDL02] C.J. Date, Hugh Darwen, Nikos Lorentzos. Temporal Data & the Relational Model. Morgan Kaufmann; 1st edition, November 19, 2002
[GJS+05] Dengfeng Gao, S. Jensen, T. Snodgrass, D. Soo. Join operations in temporal databases. The VLDB Journal, Volume 14 Issue 1, 2005
[GS03] Dengfeng Gao and Richard T. Snodgrass. Syntax, Semantics, and Query Evaluation of the τXQuery Temporal XML Query Language, TimeCenter TR-72, March 2003
[GS03+] Dengfeng Gao and Richard T. Snodgrass. Temporal Slicing in the Evaluation of XMLQueries. Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003
[Jcc07] JCC's SQL Standards Page. http://jcc.com/SQL.htm JCC Consulting, 2007
[JT95] Jan Chomicki and David Toman. Implementing Temporal Integrity Constraints Using an Active DBMS. IEEE Transactions on Knowledge and Data Engineering,  7(4), August 1995
[LBM+05] Lomet, D., Barga, R., Mokbel, M., Shegalov, G., Wang, R., and Zhu, Y. Immortal DB: Transaction Time Support for Sql Server. SIGMOD Conference, Baltimore, MD, June 2005
[Ora07a] Технология Oracle Flashback, 2007.
[Ora07b] Oracle Workspace Manager, 2007.
[RHE+04] Roddick, J. F., Hoel, E., Egenhofer, M. J., Papadias, D., and Salzberg, B. Spatial, temporal and spatio-temporal databases - hot issues and directions for phd research. SIGMOD Rec. 33(2), June 2004
[SAAB95] Richard T. Snodgrass, editor, Ilsoo Ahn, Gad Ariav, Don Batory, James Clifford, Curtis E. Dyreson, Ramez Elmasri, Fabio Grandi, Christian S. Jensen, Wolfgang Kaefer, Nick Kline, Krishna Kulkarni, T. Y. Cliff Leung, Nikos Lorentzos, John F. Roddick, Arie Segev, Michael D. Soo and Suryanarayana M. Sripada, The TSQL2 Temporal Query Language, Kluwer Academic Publishers, 1995. Спецификация TSQL2 доступна по адресу ftp://ftp.cs.arizona.edu/tsql/tsql2/bookspec.pdf, а комментарии – на ftp://ftp.cs.arizona.edu/tsql/tsql2/eval.pdf
[SBJ96a] Snodgrass, R. T., M. H. Böhlen, C. S. Jensen and A. Steiner. Adding Valid Time to SQL/Temporal. ANSI X3H2-96-501r2, ISO/IEC JTC 1/SC 21/WG 3 DBL-MAD-146r2, November, 1996
[SBJ96b] Snodgrass, R. T., M. H. Böhlen, C. S. Jensen and A. Steiner. Adding Transaction Time to SQL/Temporal, ANSI X3H2-96-502r2, ISO/IEC JTC 1/SC 21/WG 3 DBL-MAD-147r2, November, 1996
[Sno96] Snodgrass, R.T. Addendum to Valid- and Transaction-time Proposals. ANSI X3H2-96-582, ISO/IEC JTC1/SC21/WG3 DBL MAD-203, November 1996,  ftp://ftp.cs.arizona.edu/tsql/tsql2/sql3/ansi-96-582.pdf
[Sno97] Snodgrass, R.T. A Second Addendum to Valid- and Transaction-time Proposals. ANSI X3H2-97-010, ISO/IEC JTC1/SC21/WG3 DBL MAD-220, January 1997
[Sno99] Richard T. Snodgrass. Developing Time-Oriented Database Applications in SQL. Morgan Kaufmann Publishers, 1999.
[Ste98] Andreas Steiner. A Generalisation Approach to Temporal Data Models and their Implementations. Doctoral Thesis, ETH No.12434, Department of Computer Science, ETH Zurich, Switzerland, 1998
[Tim07] Официальный сайт проекта TimeDB
[TJS98] K. Torp, C. S. Jensen, and R. T. Snodgrass. Stratum Approaches to Temporal DBMS Implementation. In Proceedings of the 1998 International Database Engineering and Applications Symposium, Cardiff, Wales, UK, July 1998
[Tom96] David Toman. Point vs. Interval-based Query Languages for Temporal Databases.  Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Montreal, Quebec, Canada, 1996
[Tom98] D. Toman. Point-Based Temporal Extensions of SQL and Their Efficient Implementation. Temporal Databases: Research and Practice, Springer; 1st edition, July 1, 1998
[TS01] Paolo Terenziani, Richard T. Snodgrass. Reconciling Point-based and Interval-based Semantics in Temporal Relational Databases: A Proper Treatment of the Telic/Atelic Distinction, IEEE Transactions on Knowledge and Data Engineering, 16(5), May 2004

Страницы: назад 1 2 3 4

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

VPS в 21 локации

От 104 рублей в месяц

Безлимитный трафик. Защита от ДДоС.

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

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

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

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

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