Mengel Stefan, Skritek Sebastian
CRIL, CNRS & Université d'Artois, Lens, France.
Faculty of Informatics, TU Wien, Vienna, Austria.
Theory Comput Syst. 2021;65(1):3-41. doi: 10.1007/s00224-020-10002-z. Epub 2020 Sep 10.
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.
我们研究了评估精心设计的模式树的复杂性，这是一种查询语言，它通过定义查询的某些部分为可选来扩展合取查询。这种可选部分的可能性对于从不完整数据源获得有意义的结果很重要，因为在语义网环境中这很常见。最近，有人展示了可以在多项式时间内评估的精心设计的模式树类别的结构特征。然而，该研究未考虑投影（许多查询语言的核心特性）。我们通过给出具有投影的简单精心设计的模式树的所有可处理类别的特征（在一些常见的复杂性理论假设下）来努力填补这一空白。由于精心设计的模式树对应于精心设计的{AND, OPTIONAL}-SPARQL查询的片段，这就完整描述了该片段中具有投影且可由查询的底层图结构表征的可处理查询类。对于非简单模式树，简单模式树的可处理性标准并不能涵盖所有可处理类。因此，我们扩展了非简单情况的特征描述，以涵盖一些其他可处理情况。
