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

Поиск
RSS
Ближайшие семинары





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








Коллоквиум Факультета компьютерных наук НИУ ВШЭ
11 сентября 2017 г. 16:40, г. Москва, Кочновский проезд, д. 3, ауд. 317
 


Расширение well-designed SPARQL

Е. В. Костылев

University of Oxford

Количество просмотров:
Эта страница:20

Аннотация: SPARQL — это стандартный язык запросов для RDF-данных. Одной из важнейших особенностей этого языка относительно многих других является оператор OPTIONAL, допускающий частичные ответы в тех случаях, когда полные ответы недоступны из-за недостатка данных. Однако запросы с OPTIONAL имеют высокую сложность — соответствующая проблема является PSPACE-полной. Фрагмент языка, допускающий только ограниченное использование OPTIONAL (так называемый well-designed SPARQL), имеет более низкую сложность — coNP. Однако, как показывают наши исследования, только чуть больше половины реальных запросов с OPTIONAL к DBpedia попадают в этот фрагмент. Мы предлагаем новый класс запросов, расширяющий well-designed SPARQL, который, во-первых, включает 99% запросов с OPTIONAL и, во-вторых, также имеет coNP-сложность вычисления. Мы также исследуем другие свойства нового фрагмента, такие как сложность проверки эквивалентности и вычислительная мощность.

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