Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection
- PDF / 1,625,747 Bytes
- 39 Pages / 439.642 x 666.49 pts Page_size
- 79 Downloads / 178 Views
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection Stefan Mengel1 · Sebastian Skritek2
© The Author(s) 2020
Abstract We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtaining meaningful results over incomplete data sources as it is common in semantic web settings. Recently, a structural characterization of the classes of well-designed pattern trees that can be evaluated in polynomial time was shown. However, projection—a central feature of many query languages—was not considered in this study. We work towards closing this gap by giving a characterization of all tractable classes of simple well-designed pattern trees with projection (under some common complexity theoretic assumptions). Since well-designed pattern trees correspond to the fragment of well-designed {AND, OPTIONAL}-SPARQL queries this gives a complete description of the tractable classes of queries with projections in this fragment that can be characterized by the underlying graph structures of the queries. For non-simple pattern trees the tractability criteria for simple pattern trees do not capture all tractable classes. We thus extend the characterization for the non-simple case in order to capture some additional tractable cases. Keywords SPARQL · Well-designed pattern trees · Query evaluation · FPT · Characterizing tractable classes
This article belongs to the Topical Collection: Special Issue on Database Theory (ICDT 2019) Guest Editor: Pablo Bacel´o S. Skritek was supported by the Austrian Science Fund (FWF): P30930-N35 Sebastian Skritek
[email protected] Stefan Mengel [email protected] 1
CRIL, CNRS & Universit´e d’Artois, Lens, France
2
Faculty of Informatics, TU Wien, Vienna, Austria
Theory of Computing Systems
1 Introduction Well-designed pattern trees (wdPTs) are a query formalism well-suited to deal with the ever increasing amount of incomplete data. Well-designed pattern trees over SPARQL triple patterns are equivalent to the class of well-designed {AND, OPTIONAL}-SPARQL queries, see P´erez et al. [21], and were in fact originally introduced as a formalism to more easily study SPARQL queries. By replacing triple patterns with relational atoms, wdPTs can also be seen as an extension of Conjunctive Queries (CQs): a wdPT is a rooted tree where each node represents a conjunction of atoms, and the tree structure represents a nesting of optional matching. The idea is to start evaluating the CQ at the root and to iteratively extend the retrieved results as much as possible by the results of the CQs in the other nodes. This allows wdPTs to return partial answers in cases where mapping the complete query into the database is impossible—unlike CQs which in such a situation return no answer. Well-designed pattern trees and the corresponding SPARQL fragment represent an important class of SPARQL queries and have been studied
Data Loading...
