Non-Uniformly Terminating Chase: Size and Complexity

• URL: http://arxiv.org/abs/2204.10584v2
• Date: Tue, 26 Apr 2022 06:56:40 GMT
• Title: Non-Uniformly Terminating Chase: Size and Complexity
• Authors: Marco Calautti, Georg Gottlob, Andreas Pieris
• Abstract summary: We focus on guarded-generating dependencies (TGDs), which form a robust rule-based termination. One of our main findings is that non-uniform semi-oblivious chase for guarded TGDs is feasible in time w.r.t the database. We show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.
• Score: 8.250374560598493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central algorithmic tool in rule-based ontological reasoning. In this context, a key problem is non-uniform chase termination: does the chase of a database w.r.t. a rule-based ontology terminate? And if this is the case, what is the size of the result of the chase? We focus on guarded tuple-generating dependencies (TGDs), which form a robust rule-based ontology language, and study the above central questions for the semi-oblivious version of the chase. One of our main findings is that non-uniform semi-oblivious chase termination for guarded TGDs is feasible in polynomial time w.r.t. the database, and the size of the result of the chase (whenever is finite) is linear w.r.t. the database. Towards our results concerning non-uniform chase termination, we show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.

Related papers

• Cell as Point: One-Stage Framework for Efficient Cell Tracking [54.19259129722988]
  We propose a novel end-to-end one-stage framework that reimagines cell tracking by treating Cell as Point. Unlike traditional methods, CAP eliminates the need for explicit detection or segmentation, instead jointly tracking cells for sequences in one stage. CAP demonstrates promising cell tracking performance and is 10 to 55 times more efficient than existing methods.
  arXiv  Detail & Related papers  (2024-11-22T10:16:35Z)
• ION-C: Integration of Overlapping Networks via Constraints [2.6068919473964893]
  We present the first algorithm for enumerating the minimal equivalence class of ground-truth DAGs consistent with all input graphs by exploiting local independence relations, called ION. The ION-C algorithm was run on random synthetic graphs with varying sizes, densities, and degrees of overlap between subgraphs. To validate ION-C on real-world data, we ran the algorithm on overlapping graphs learned from data from two successive iterations of the European Social Survey (ESS)
  arXiv  Detail & Related papers  (2024-11-06T20:12:47Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  We propose a model-based primal-dual algorithm to learn in an unknown CMDP. We prove that our algorithm achieves sublinear regret without error cancellations.
  arXiv  Detail & Related papers  (2024-02-24T09:47:46Z)
• Double-Bounded Optimal Transport for Advanced Clustering and Classification [58.237576976486544]
  We propose Doubly Bounded Optimal Transport (DB-OT), which assumes that the target distribution is restricted within two boundaries instead of a fixed one. We show that our method can achieve good results with our improved inference scheme in the testing stage.
  arXiv  Detail & Related papers  (2024-01-21T07:43:01Z)
• Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study [5.936402320555635]
  The chase procedure is a fundamental algorithmic tool in databases that allows us to reason with constraints. 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.
  arXiv  Detail & Related papers  (2023-03-22T18:21:01Z)
• Forward LTLf Synthesis: DPLL At Work [1.370633147306388]
  We propose a new AND-OR graph search framework for synthesis of Linear Temporal Logic on finite traces (LTLf) Within such framework, we devise a procedure inspired by the Davis-Putnam-Logemann-Loveland (DPLL) algorithm to generate the next available agent-environment moves. We also propose a novel equivalence check for search nodes based on syntactic equivalence of state formulas.
  arXiv  Detail & Related papers  (2023-02-27T14:33:50Z)
• Crake: Causal-Enhanced Table-Filler for Question Answering over Large Scale Knowledge Base [11.888045774125787]
  We formalize semantic parsing into two stages. In the first stage, we propose a causal-enhanced table-filler to overcome the issues in sequence-modelling and to learn the internal causalities. In the second stage, an efficient beam-search algorithm is presented to scale complex queries on large-scale KBs.
  arXiv  Detail & Related papers  (2022-07-08T04:21:26Z)
• Understanding Deep Learning via Decision Boundary [81.49114762506287]
  We show that the neural network with lower decision boundary (DB) variability has better generalizability. Two new notions, algorithm DB variability and $(epsilon, eta)$-data DB variability, are proposed to measure the decision boundary variability.
  arXiv  Detail & Related papers  (2022-06-03T11:34:12Z)
• A2Log: Attentive Augmented Log Anomaly Detection [53.06341151551106]
  Anomaly detection becomes increasingly important for the dependability and serviceability of IT services. Existing unsupervised methods need anomaly examples to obtain a suitable decision boundary. We develop A2Log, which is an unsupervised anomaly detection method consisting of two steps: Anomaly scoring and anomaly decision.
  arXiv  Detail & Related papers  (2021-09-20T13:40:21Z)
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games [102.23975166536326]
  Tree-form sequential decision making (TFSDM) extends classical one-shot decision making by modeling tree-form interactions between an agent and a potentially adversarial environment. It captures the online decision-making problems that each player faces in an extensive-form game, as well as Markov decision processes and partially-observable Markov decision processes where the agent conditions on observed history. In this paper, we give the first algorithm for the bandit linear optimization problem for dilatedDM that offers both (i) linear-time losses and (ii) $O(sqrtT)$ cumulative regret in
  arXiv  Detail & Related papers  (2021-03-08T05:00:13Z)
• Characterizing Boundedness in Chase Variants [1.7033055327465234]
  We investigate the decidability of the k-boundedness problem, which asks whether the depth of the chase for a given set of rules is bounded by an integer k. We show that the main chase variants satisfy this property, namely the oblivious, semi-oblivious, and restricted chase, as well as their breadth-first versions.
  arXiv  Detail & Related papers  (2020-04-21T14:07:10Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.