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