論文の概要: A tetrachotomy of ontology-mediated queries with a covering axiom
- arxiv url: http://arxiv.org/abs/2006.04167v4
- Date: Thu, 5 May 2022 10:22:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 08:15:12.087654
- Title: A tetrachotomy of ontology-mediated queries with a covering axiom
- Title（参考訳）: 被覆公理を用いたオントロジーによるクエリの四分法
- Authors: Olga Gerasimova, Stanislav Kikot, Agi Kurucz, Vladimir Podolskii,
Michael Zakharyaschev
- Abstract要約: 我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
- 参考スコア（独自算出の注目度）: 1.749935196721634
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Our concern is the problem of efficiently determining the data complexity of
answering queries mediated by description logic ontologies and constructing
their optimal rewritings to standard database queries. Originated in
ontology-based data access and datalog optimisation, this problem is known to
be computationally very complex in general, with no explicit syntactic
characterisations available. In this article, aiming to understand the
fundamental roots of this difficulty, we strip the problem to the bare bones
and focus on Boolean conjunctive queries mediated by a simple covering axiom
stating that one class is covered by the union of two other classes. We show
that, on the one hand, these rudimentary ontology-mediated queries, called
disjunctive sirups (or d-sirups), capture many features and difficulties of the
general case. For example, answering d-sirups is Pi^p_2-complete for combined
complexity and can be in AC0 or LogSpace-, NL-, P-, or coNP-complete for data
complexity (with the problem of recognising FO-rewritability of d-sirups being
2ExpTime-hard); some d-sirups only have exponential-size resolution proofs,
some only double-exponential-size positive existential FO-rewritings and
single-exponential-size nonrecursive datalog rewritings. On the other hand, we
prove a few partial sufficient and necessary conditions of FO- and
(symmetric/linear-) datalog rewritability of d-sirups. Our main technical
result is a complete and transparent syntactic AC0/NL/P/coNP tetrachotomy of
d-sirups with disjoint covering classes and a path-shaped Boolean conjunctive
query. To obtain this tetrachotomy, we develop new techniques for establishing
P- and coNP-hardness of answering non-Horn ontology-mediated queries as well as
showing that they can be answered in NL.
- Abstract（参考訳）: 本研究は,記述論理オントロジーを介する応答クエリのデータ複雑性を効率的に決定し,標準データベースクエリへの最適な書き直しを行う問題である。
オントロジーに基づくデータアクセスとデータログの最適化が起源であり、この問題は一般に計算的に非常に複雑であり、明示的な構文的特徴付けはできないことが知られている。
本稿では,この難しさの根源を理解することを目的として,この問題を裸骨に切り離し,一方のクラスが他方のクラスの結合によってカバーされていることを示す単純な被覆公理を介するブール共役クエリに焦点をあてる。
一方,これらの初歩的なオントロジーによる問合せは解離性シロップ(d-シロップ)と呼ばれ,一般的な症例の特徴や難易度を捉えている。
例えば、d-シロップスの解答は、複合複雑性に対して Pi^p_2 完全であり、AC0 または LogSpace-, NL-, P-, coNP 完全でデータ複雑性(d-シラップのFO-リライト可能性の認識は 2ExpTime-hard である)である。
一方, d-sirupsのfoおよび(対称/線形)データログの可逆性について, 十分かつ必要な条件がいくつか証明された。
我々の主な技術的成果は,d-sirupsの完全かつ透明な構文的ac0/nl/p/conp四分法である。
この四分法を実現するため,非Hornオントロジー型クエリに応答するP-およびcoNP硬度を確立し,NLで応答できることを示す新しい手法を開発した。
関連論文リスト
- MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
大規模言語モデル(LLM)は、高い精度で算術語問題を解くことができるが、訓練された言語よりも複雑な問題にどのように一般化するかは、ほとんど分かっていない。
本研究では、任意に複雑な算術証明問題に対する LLM の評価フレームワーク、MathGAP を提案する。
論文 参考訳（メタデータ） (2024-10-17T12:48:14Z) - The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。
私たちの発見は、難しい複雑さの風景を明らかにします。
このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
論文 参考訳（メタデータ） (2024-10-10T15:22:48Z) - The Computational Complexity of Concise Hypersphere Classification [49.57441416941195]
本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究である。
パラメータ化複雑性のパラダイムを用いて、入力データに存在する可能性のある構造特性の影響を分析する。
論文 参考訳（メタデータ） (2023-12-12T09:33:03Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability [8.618430843854048]
接続的クエリに対する回答の数をカウントすることは、標準的な仮定では効率的な解を持たないデータベースの基本的な問題である。
固有インスタンスの構造特性を調べ、#-ハイパーツリー分解という新しい概念を導入することにより、抽出可能なクラスをピンポイントする。
論文 参考訳（メタデータ） (2023-11-24T16:09:12Z) - Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。
これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。
提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
論文 参考訳（メタデータ） (2023-04-14T11:35:35Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - How to Approximate Ontology-Mediated Queries [22.99749220980996]
ALC と ALCI の記述論理に基づいて,オントロジーによるクエリに対する近似のいくつかの概念を紹介し,研究する。
近似式は,(1) オントロジーを ELI や特定の TGD などのトラクタブル言語で定式化された1つに置き換える,(2) ツリー幅が定数で有界なデータベースのクラスのようなトラクタブルクラスの1つに置き換える,の2種類からなる。
論文 参考訳（メタデータ） (2021-07-12T12:29:50Z) - When is Ontology-Mediated Querying Efficient? [10.971122842236024]
関係データベース上でのオントロジーによるクエリの評価について検討する。
OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。
また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
論文 参考訳（メタデータ） (2020-03-17T16:32:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。