TY - GEN
T1 - The tractability frontier of well-designed SPARQL queries
AU - Romero, Miguel
N1 - Funding Information:
∗This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/5/27
Y1 - 2018/5/27
N2 - We study the complexity of query evaluation of SPARQL queries. We focus on the fundamental fragment of well-designed SPARQL restricted to the AND, OPTIONAL and UNION operators. Our main result is a structural characterisation of the classes of well-designed queries that can be evaluated in polynomial time. In particular, we introduce a new notion of width called domination width, which relies on the well-known notion of treewidth. We show that, under some complexity theoretic assumptions, the classes of well-designed queries that can be evaluated in polynomial time are precisely those of bounded domination width.
AB - We study the complexity of query evaluation of SPARQL queries. We focus on the fundamental fragment of well-designed SPARQL restricted to the AND, OPTIONAL and UNION operators. Our main result is a structural characterisation of the classes of well-designed queries that can be evaluated in polynomial time. In particular, we introduce a new notion of width called domination width, which relies on the well-known notion of treewidth. We show that, under some complexity theoretic assumptions, the classes of well-designed queries that can be evaluated in polynomial time are precisely those of bounded domination width.
KW - Domination width
KW - Evaluation
KW - Pattern trees
KW - Polynomial time
KW - Treewidth
KW - Well-designed SPARQL
UR - http://www.scopus.com/inward/record.url?scp=85048028659&partnerID=8YFLogxK
U2 - 10.1145/3196959.3196973
DO - 10.1145/3196959.3196973
M3 - Conference contribution
AN - SCOPUS:85048028659
T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
SP - 295
EP - 306
BT - PODS 2018 - Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
A2 - Van den Bussche, Jan
A2 - Ugarte, Mart�n
A2 - Arenas, Marcelo
PB - Association for Computing Machinery
T2 - 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2018
Y2 - 10 June 2018 through 15 June 2018
ER -