論文の概要: Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics

• arxiv url: http://arxiv.org/abs/2511.07095v1
• Date: Mon, 10 Nov 2025 13:34:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-11 21:18:45.275267
• Title: Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics
• Title（参考訳）: コストベースセマンティクスに基づく記述論理知識データベースの検索データの複雑さ
• Authors: Meghyn Bienvenu, Quentin Manière,
• Abstract要約: コストベースセマンティクスに基づく不整合重み付き記述論理(DL)知識ベースを問合せする際のデータ複雑性について検討する。 簡単に言うと、この考え方は、各解釈に違反した公理と主張の重みに基づくコストを割り当てることである。 そこで本研究では,一階書き直しにより,一階書き直しによって,一階書き直しの解や連結クエリの解を計算できることを見出した。
• 参考スコア（独自算出の注目度）: 4.511923587827302
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions, and certain and possible query answers are determined by considering all (resp. some) interpretations having optimal or bounded cost. Whereas the initial study of cost-based semantics focused on DLs between $\mathcal{EL}_\bot$ and $\mathcal{ALCO}$, we consider DLs that may contain inverse roles and role inclusions, thus covering prominent DL-Lite dialects. Our data complexity analysis goes significantly beyond existing results by sharpening several lower bounds and pinpointing the precise complexity of optimal-cost certain answer semantics (no non-trivial upper bound was known). Moreover, while all existing results show the intractability of cost-based semantics, our most challenging and surprising result establishes that if we consider $\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$ ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity ($\mathsf{TC}_0$).
• Abstract（参考訳）: 本稿では、最近導入されたコストベースセマンティクスに基づいて、一貫性のない重み付き記述論理(DL)知識ベースを問合せする際のデータ複雑さについて検討する。 簡単に言えば、各解釈は、違反した公理と主張の重みに基づいてコストを割り当てることであり、最適または有界なコストを持つ全ての(一部の)解釈を考慮して、確実かつ可能な問合せ解が決定される。 コストベースのセマンティクスの最初の研究は、$\mathcal{EL}_\bot$と$\mathcal{ALCO}$の間のDLに焦点を当てていたが、逆の役割や役割の包含を含むかもしれないDLを考えると、顕著なDL-Lite方言をカバーしている。 我々のデータ複雑性分析は、いくつかの下位境界を鋭くし、最適コストの特定の解のセマンティクス(非自明な上限は知られていない)の正確な複雑さを指摘することによって、既存の結果を大きく超えています。 さらに、既存のすべての結果がコストベースのセマンティクスの難易度を示している一方で、最も難解で驚くべき結果は、$\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$オントロジーと固定コストバウンドを考えると、インスタンスクエリに対する特定の回答と共役クエリに対する可能な回答は、一階書き直しを使って計算でき、従って最小のデータ複雑性($\mathsf{TC}_0$)を享受できるということである。

関連論文リスト

• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  タスク分解を用いて問題空間をトラバースする新しい手法を提案する。 我々はLarge Language Modelsを使ってソリューションを計画し、クエリを事実に軟式化し、論理プログラミングコードを使って述語する。 提案手法は,生成したコードに対する推論プロセスの忠実度を計算し,外部の解法に頼らずにマルチホップ探索のステップを解析する。
  論文  参考訳（メタデータ） (2024-10-14T19:39:11Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• Queries With Exact Truth Values in Paraconsistent Description Logics [5.222978725954348]
  本稿では,古典的不整合記述論理(DL)知識ベースを問合せするための新しいアプローチを提案する。 正確には(mathbfT$)、正確には(mathbfF$)、両方の(mathbfB$)、そしてどちらも(mathbfN$)である。
  論文  参考訳（メタデータ） (2024-08-01T08:11:50Z)
• Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases [5.222978725954348]
  我々は、公理とアサーションの両方が(おそらく無限の)重みを持つ重み付き知識基底を考える。 確実かつ可能な答えの2つの概念は、コストが与えられた境界を超えない解釈を考えることによって定義される。 我々の主な貢献は、有界コスト満足度と確実かつ可能な回答認識の組合せとデータ複雑さの包括的分析である。
  論文  参考訳（メタデータ） (2024-07-30T11:56:02Z)
• H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
  本稿では,2段階のプロセスにシンボル的アプローチと意味的アプローチ(テキスト的アプローチ)を統合し,制約に対処する新しいアルゴリズムを提案する。 実験の結果,H-STARは3つの質問応答(QA)と事実検証データセットにおいて,最先端の手法を大幅に上回っていることがわかった。
  論文  参考訳（メタデータ） (2024-06-29T21:24:19Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  Description Logics (DL) におけるプライバシ保護クエリ応答に関する研究 DL-Lite$_mathcal$$で応答するデータ複雑性の結果を導出します。 我々は,CQEに対する近似秘密性解答という意味論的に確立された概念を同定する。
  論文  参考訳（メタデータ） (2020-04-24T17:28:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。