論文の概要: When is Ontology-Mediated Querying Efficient?
- arxiv url: http://arxiv.org/abs/2003.07800v2
- Date: Wed, 29 Jul 2020 15:25:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-22 21:38:41.175108
- Title: When is Ontology-Mediated Querying Efficient?
- Title（参考訳）: オントロジによるクエリはいつ効率的か?
- Authors: Pablo Barcelo, Cristina Feier, Carsten Lutz, Andreas Pieris
- Abstract要約: 関係データベース上でのオントロジーによるクエリの評価について検討する。
OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。
また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
- 参考スコア（独自算出の注目度）: 10.971122842236024
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In ontology-mediated querying, description logic (DL) ontologies are used to
enrich incomplete data with domain knowledge which results in more complete
answers to queries. However, the evaluation of ontology-mediated queries (OMQs)
over relational databases is computationally hard. This raises the question
when OMQ evaluation is efficient, in the sense of being tractable in combined
complexity or fixed-parameter tractable. We study this question for a range of
ontology-mediated query languages based on several important and widely-used
DLs, using unions of conjunctive queries as the actual queries. For the DL ELHI
extended with the bottom concept, we provide a characterization of the classes
of OMQs that are fixed-parameter tractable. For its fragment EL extended with
domain and range restrictions and the bottom concept (which restricts the use
of inverse roles), we provide a characterization of the classes of OMQs that
are tractable in combined complexity. Both results are in terms of equivalence
to OMQs of bounded tree width and rest on a reasonable assumption from
parameterized complexity theory. They are similar in spirit to Grohe's seminal
characterization of the tractable classes of conjunctive queries over
relational databases. We further study the complexity of the meta problem of
deciding whether a given OMQ is equivalent to an OMQ of bounded tree width,
providing several completeness results that range from NP to 2ExpTime,
depending on the DL used. We also consider the DL-Lite family of DLs, including
members that admit functional roles.
- Abstract（参考訳）: オントロジーによるクエリでは、記述論理(DL)オントロジーは、クエリに対するより完全な回答をもたらすドメイン知識で不完全なデータを統合するために使用される。
しかし、関係データベースに対するオントロジーによるクエリ(OMQ)の評価は、計算的に困難である。
これにより、OMQ評価が効率的で、複合複雑性や固定パラメータのトラクタでトラクタブルであるという意味で、疑問が持ち上がる。
本稿では,複数の重要かつ広く使用されているDLをベースとしたオントロジー型クエリ言語について,実際のクエリとして結合クエリの結合を用いて検討する。
底面の概念で拡張されたDL ELHIに対して、固定パラメータ抽出可能なOMQのクラスの特性を提供する。
ドメインと範囲の制限とボトムコンセプト(逆役割の使用を制限する)によって拡張されたその断片elは、複合複雑性で扱いやすいomqのクラスの特徴付けを提供する。
どちらの結果も、有界木幅の OMQ と等価であり、パラメータ化複雑性理論からの合理的な仮定に基づいている。
それらは、関係データベース上の連結クエリの扱いやすいクラスに対するgroheの独創的な特徴付けに似ている。
さらに、与えられたOMQが有界木幅のOMQと等価かどうかを決定するメタ問題の複雑さについて検討し、使用したDLに応じてNPから2ExpTimeまでの完全な結果を提供する。
また,機能的役割を有するメンバーを含むDL-Liteファミリーについても検討した。
関連論文リスト
- GRS-QA -- Graph Reasoning-Structured Question Answering Dataset [50.223851616680754]
グラフ推論-構造化質問応答データセット(GRS-QA)を導入する。
既存のM-QAデータセットとは異なり、GRS-QAは推論グラフを構築することで複雑な推論経路を明示的にキャプチャする。
実験により, LLMは, 様々な推論構造を用いて, 問合せ処理を行う際に, 異なる性能を示すことが明らかとなった。
論文 参考訳（メタデータ） (2024-11-01T05:14:03Z) - Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。
本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。
オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
論文 参考訳（メタデータ） (2024-03-21T13:52:30Z) - Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge
Base and Database [86.03294330305097]
知識ベース(KB)とデータベース(DB)の両方で質問応答(QA)を統一した意味的要素を提案する。
フレームワークに不可欠な要素としてプリミティブ(KBのリレーションとエンティティ、テーブル名、列名、DBのセル値)を導入します。
生成元を利用して、異なる操作でトップランクプリミティブを変更・構成することで、最終的な論理形式を予測する。
論文 参考訳（メタデータ） (2022-11-09T19:33:27Z) - Ontology-Mediated Querying on Databases of Bounded Cliquewidth [10.880181451789262]
有界クリフ幅のデータベース上でのオントロジーによるクエリ(OMQ)の評価について検討する。
我々の主な貢献は、パラメータのランニング時間依存性の詳細な分析であり、いくつかの興味深い効果を示している。
論文 参考訳（メタデータ） (2022-05-04T17:13:08Z) - Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。
回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。
埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
論文 参考訳（メタデータ） (2022-04-27T11:16:08Z) - Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。
提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
論文 参考訳（メタデータ） (2022-02-22T01:34:35Z) - From Conjunctive Queries to Instance Queries in Ontology-Mediated
Querying [17.79631575141597]
本稿では,ALCファミリーの表現的記述論理と接続的クエリの(一意)に基づくオントロジーによるクエリについて考察する。
この結果には,このような書き換えが可能なタイミングの正確な特徴と,書き換え可能性を決定するための厳密な複雑性境界が含まれている。
論文 参考訳（メタデータ） (2020-10-22T16:40:59Z) - Answering Counting Queries over DL-Lite Ontologies [0.0]
本稿では,クエリをカウントする一般的な形式を導入し,従来の提案に関連付けるとともに,そのようなクエリに答えることの複雑さについて検討する。
我々は、複雑性境界の改善を確立させる、実践的に関連するいくつかの制約について検討する。
論文 参考訳（メタデータ） (2020-09-02T11:10:21Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文 参考訳（メタデータ） (2020-06-07T14:47:07Z) - Counting Query Answers over a DL-Lite Knowledge Base (extended version) [14.504450881786214]
知識ベース(KB)上での問合せ応答の複雑さについて検討する。
我々はPTIMEとcoNPの下位境界と、PTIMEとLOGSPACEの上位境界を提供することで既存の結果を改善する。
論文 参考訳（メタデータ） (2020-05-12T16:01:09Z) - Query Focused Multi-Document Summarization with Distant Supervision [88.39032981994535]
既存の作業は、クエリとテキストセグメント間の関連性を推定する検索スタイルの手法に大きく依存している。
本稿では,クエリに関連するセグメントを推定するための個別モジュールを導入した粗大なモデリングフレームワークを提案する。
我々のフレームワークは、標準QFSベンチマークにおいて、強力な比較システムよりも優れていることを実証する。
論文 参考訳（メタデータ） (2020-04-06T22:35:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。