On expressibility of non-monotone operators in SPARQL

Conference item

SPARQL, a query language for RDF graphs, is one of the key technologies for the Semantic Web. The expressivity and complexity of various fragments of SPARQL have been studied extensively. It is usually assumed that the optional matching operator OPTIONAL has only two graph patterns as arguments. The specification of SPARQL, however, defines it as a ternary operator, with an additional filter condition. We address the problem of expressibility of the full ternary OPTIONAL via the simplified binary version and show that it is possible, but only with an exponential blowup in the size of the query (under common complexity-theoretic assumptions). We also study expressibility of other non-monotone SPARQL operators via optional matching and each other.

Authors: Kontchakov, R; Kostylev, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: AAAI Press
• Host title: Proceedings, Fifteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2016)
• Pages: 369-378
• Publication date: 2016-04-25
• Acceptance date: 2016-01-21
• Event title: 15th International Conference on Principles of Knowledge Representation and Reasoning
• Event location: Cape Town, South Africa
• Event website: http://kr2016.cs.uct.ac.za
• Event start date: 2016-04-25
• Event end date: 2016-04-29
• ISBN: 9781577357551
• Language: English