[Коллоквиум]: Расширение well-designed SPARQL
161 views · Published 1 October 2017 · 1:12:55 · Indexed 6 November 2026
Channel: ФКН ВШЭ · 2017 · Education
Докладчик: Егор Костылев, University of Oxford SPARQL — это стандартный язык запросов для RDF-данных. Одной из важнейших особенностей этого языка относительно многих других является оператор OPTIONAL, допускающий частичные ответы в тех случаях, когда полные ответы недоступны из-за недостатка данных. Однако запросы с OPTIONAL имеют высокую сложность — соответствующая проблема является PSPACE-полной. Фрагмент языка, допускающий только ограниченное использование OPTIONAL (так называемый well-designed SPARQL), имеет более низкую сложность — coNP. Однако, как показывают наши исследования, только чуть больше половины реальных запросов с OPTIONAL к DBpedia попадают в этот фрагмент. Мы предлагаем новый класс запросов, расширяющий well-designed SPARQL, который, во-первых, включает 99% запросов с OPTIONAL и, во-вторых, также имеет coNP-сложность вычисления. Мы также исследуем другие свойства нового фрагмента, такие как сложность проверки эквивалентности и вычислительная мощность.
More from this channel
-
1:18:31
[Коллоквиум]: On scale invariance, multifractal formalism, and their applications
-
1:09:43
[Коллоквиум]: Resourse Allocation in the Cloud - Assaf Schuster, Techion
-
1:08:04
[ИТ-лекторий] Занимательная прикладная аналитика в Яндексе
-
1:17:41
[Коллоквиум]: Probabilistic graphical models: Factor graphs and more
-
1:05:46
[Коллоквиум]: Process Mining: Data Science in Action - Wil van der Aalst
-
2:18
[Презентация факультета в ДК ЗИЛ]: Григорий Бакунов, директор по распрост. инф. технологий Яндекс
-
2:55
[Презентация факультета в ДК ЗИЛ]: Григорий Канторович, проректор по работе с абитуриентами ВШЭ
-
11:34
[Презентация факультета в ДК ЗИЛ]: Иван Аржанцев, декан факультета компьютерных наук