We introduce and study several notions of approximation for ontology-mediated queries based on the description logics ALC and ALCI. Our approximations are of two kinds: we may (1) replace the ontology with one formulated in a tractable ontology language such as ELI or certain TGDs and (2) replace the database with one from a tractable class such as the class of databases whose treewidth is bounded by a constant. We determine the computational complexity and the relative completeness of the resulting approximations. (Almost) all of them reduce the data complexity from coNP-complete to PTime, in some cases even to fixed-parameter tractable and to linear time. While approximations of kind (1) also reduce the combined complexity, this tends to not be the case for approximations of kind (2). In some cases, the combined complexity even increases.
翻译:我们根据描述逻辑ALC 和 ALCI 引入并研究一些近似近似概念,用于以本体学为介于本体学的查询。我们的近似概念分为两类:(1) 将本体学替换为可移植本体学语言,如ELI或某些TGD,(2) 将数据库替换为可移植类数据库,如树枝受常数约束的数据库类别。我们确定由此产生的近似的计算复杂性和相对完整性。 (几乎)所有这些概念都降低了从CONP完成到PTime的数据复杂性,有时甚至降低到可固定参数可移动和线性时间。虽然种类近似(1) 也降低了综合复杂性,但这类近似不常见(2) 在某些情况下,综合复杂性甚至增加。