RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Научная сессия МИАН, посвященная подведению итогов 2015 года
11 ноября 2015 г. 11:45, г. Москва, конференц-зал МИАН (ул. Губкина, 8)
 


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

В. В. Подольский
Видеозаписи:
MP4 487.8 Mb
MP4 123.6 Mb

Количество просмотров:
Эта страница:264
Видеофайлы:56

В. В. Подольский
Фотогалерея


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

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

Список литературы
  1. Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Thomas Schwentick, Michael Zakharyaschev, “The price of query rewriting in ontology-based data access”, Artificial Intelligence, 213 (2014), 42–59  crossref  mathscinet  zmath  isi  elib  scopus
  2. Stanislav Kikot, Roman Kontchakov, Vladimir V. Podolskii, Michael Zakharyaschev, “On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Bounded Chase”, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), ACM Digital Library, 2014, 57:1–57:10 , arXiv: 1401.4420
  3. Meghyn Bienvenu, Stanislav Kikot, Vladimir V. Podolskii, “Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results”, 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE, 2015, 317–328 , arXiv: 1406.3047  mathnet  crossref


Статьи по теме:

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017