Oblivious and Semi-Oblivious Boundedness for Existential Rules
We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem. This report contains the paper published at IJCAI 2019 and an appendix with full proofs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the k-Boundedness for Existential Rules
The chase is a fundamental tool for existential rules. Several chase variants are known, which differ on how they handle redundancies possibly caused by the introduction of nulls. Given a chase variant, the halting probl…
Characterizing Boundedness in Chase Variants
Existential rules are a positive fragment of first-order logic that generalizes function-free Horn rules by allowing existentially quantified variables in rule heads. This family of languages has recently attracted signi…
Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study
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 constrai…
Robust Linear Regression for General Feature Distribution
We investigate robust linear regression where data may be contaminated by an oblivious adversary, i.e., an adversary than may know the data distribution but is otherwise oblivious to the realizations of the data samples.…
regressionExact Recovery Guarantees for Parameterized Nonlinear System Identification Problem under Sparse Disturbances or Semi-Oblivious Attacks
In this work, we study the problem of learning a nonlinear dynamical system by parameterizing its dynamics using basis functions. We assume that disturbances occur at each time step with an arbitrary probability $p$, whi…