論文の概要: Semi-Oblivious Chase Termination for Linear Existential Rules: An
Experimental Study
- arxiv url: http://arxiv.org/abs/2303.12851v1
- Date: Wed, 22 Mar 2023 18:21:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-24 16:47:02.790459
- Title: Semi-Oblivious Chase Termination for Linear Existential Rules: An
Experimental Study
- Title（参考訳）: 線形実効規則の半公約チェイス終了:実験的検討
- Authors: Marco Calautti, Mostafa Milani, Andreas Pieris
- Abstract要約: チェイス手順は、制約のある推論を可能にする、データベースの基本的なアルゴリズムツールである。
データベースと一連の制約を入力として取り、制約によって決定されたデータベースを反復的に完了します。
しかし、重要な課題は、それが終了しないかもしれないという事実であり、それが与えられたデータベースと一連の制約を終了するかどうかをチェックする問題に繋がる。
- 参考スコア（独自算出の注目度）: 5.936402320555635
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The chase procedure is a fundamental algorithmic tool in databases that
allows us to reason with constraints, such as existential rules, with a
plethora of applications. It takes as input a database and a set of
constraints, and iteratively completes the database as dictated by the
constraints. A key challenge, though, is the fact that it may not terminate,
which leads to the problem of checking whether it terminates given a database
and a set of constraints. In this work, we focus on the semi-oblivious version
of the chase, which is well-suited for practical implementations, and linear
existential rules, a central class of constraints with several applications. In
this setting, there is a mature body of theoretical work that provides
syntactic characterizations of when the chase terminates, algorithms for
checking chase termination, precise complexity results, and worst-case optimal
bounds on the size of the result of the chase (whenever is finite). Our main
objective is to experimentally evaluate the existing chase termination
algorithms with the aim of understanding which input parameters affect their
performance, clarifying whether they can be used in practice, and revealing
their performance limitations.
- Abstract（参考訳）: チェイスプロシージャはデータベースの基本的なアルゴリズムツールであり、既存のルールなどの制約を多くのアプリケーションに当てはめることができる。
データベースと制約のセットを入力として取り、制約によって決定されるようにデータベースを反復的に完了します。
しかし、重要な課題は、データベースが終了しない可能性があるという事実であり、データベースと制約のセットが終了するかどうかをチェックすることに繋がる。
本研究では,実践的な実装に適したチェイスの半公開バージョンと,いくつかのアプリケーションによる制約の集中クラスである線形存在規則に着目した。
この設定では、チェイスがいつ終了するか、チェイス終了のアルゴリズム、正確な複雑性結果、そしてチェイスの結果(有限である場合)の最悪のケース最適境界の構文的特徴を提供する理論的な研究の成熟体が存在する。
本研究の目的は,既存のチェイス終了アルゴリズムを,どの入力パラメータが性能に影響を及ぼすかを理解し,実際に使用できるかを明らかにし,性能制限を明らかにすることにある。
関連論文リスト
- Bisimulation Learning [55.859538562698496]
我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。
提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
論文 参考訳（メタデータ） (2024-05-24T17:11:27Z) - Decidable Reasoning About Time in Finite-Domain Situation Calculus
Theories [9.45355418401911]
最も一般的に使用されるアプローチは、実値の流れる$mathittime(a)$を追加して、各アクションにタイムポイントをアタッチし、結果として各状況にアタッチすることで、時間を表す。
このアプローチでは、言論の領域が有限個の対象に制限されている場合でも、与えられた式を満たす到達可能な状況が決定不能であるかどうかを確認する。
論文 参考訳（メタデータ） (2024-02-05T16:32:12Z) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
オンライン優先制約による非サーボ的スケジューリングについて検討する。
アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
論文 参考訳（メタデータ） (2023-01-30T13:17:15Z) - Offline Policy Optimization with Eligible Actions [34.4530766779594]
オフラインポリシーの最適化は多くの現実世界の意思決定問題に大きな影響を与える可能性がある。
重要度サンプリングとその変種は、オフラインポリシー評価において一般的に使用されるタイプの推定器である。
そこで本稿では, 州ごとの正規化制約によって過度に適合することを避けるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-01T19:18:15Z) - Non-Uniformly Terminating Chase: Size and Complexity [8.250374560598493]
我々は、ロバストなルールベースの終了を形成する、ガード付き生成依存(TGD)に焦点を当てる。
主な発見の1つは、保護されたTGDに対する一様でない半出版的追跡が、データベースの時間内で実現可能であることである。
本稿では,従来のオントロジクエリ応答の文脈で導入された単純化や線形化といった基本的な手法が,チェイス終了問題に安全に適用可能であることを示す。
論文 参考訳（メタデータ） (2022-04-22T09:07:08Z) - Computing unsatisfiable cores for LTLf specifications [3.251765107970636]
有限トレース上の線形時間時間時間論理(LTLf)は、多くのアプリケーション領域で仕様を作成するためのデファクト標準になりつつある。
満足度チェックのための最先端手法を用いて、不満足なコアを抽出する4つのアルゴリズムを提案する。
結果は、異なるアルゴリズムやツールの実現可能性、有効性、相補性を示している。
論文 参考訳（メタデータ） (2022-03-09T16:08:43Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - An Automated Approach to Causal Inference in Discrete Settings [8.242194776558895]
本稿では,効率的な二重緩和法と空間分岐結合法を用いて因果効果を自動的に結合するアルゴリズムを提案する。
このアルゴリズムは、許容可能なデータ生成プロセスを探索し、利用可能な情報と最も正確な範囲を出力する。
これは、不完全境界を特徴付ける$epsilon$-sharpnessと呼ばれる追加の保証を提供する。
論文 参考訳（メタデータ） (2021-09-28T03:55:32Z) - An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。
ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
論文 参考訳（メタデータ） (2021-02-17T19:55:42Z) - Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。
ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。
本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
論文 参考訳（メタデータ） (2020-10-07T08:19:48Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。