Efficient Dependency Analysis for Existential Rules

Larry GonzalezLarry Gonzalez, Alex IvlievAlex Ivliev, Stephan MennickeStephan Mennicke, Markus KrötzschMarkus Krötzsch

Download

Larry Gonzalez, Alex Ivliev, Stephan Mennicke, Markus Krötzsch
Efficient Dependency Analysis for Existential Rules
, May 2023

Details
Bibtex

KurzfassungAbstract
This short paper reviews the main contributions of our recent work on static analysis of existential rules (a.k.a. tuple-generating dependencies). Between such rules, several kinds of logical relationships -- also called dependencies in an unfortunate clash of terminology -- are of interest, but their computation highly intractable. We develop new, optimised procedures for this task, and present a prototype implementation that scales to real-world inputs of more than 100,000 rules. This allows us to perform much faster acyclicity checks and to identify rule sets that admit efficient core computation via the standard chase.
Projekt:Project: CPEC, InnoSale, KIMEDS, SECAI, ScaDS.AI, Cfaed
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@proceedings{GIMK2023,
  author = {Larry Gonzalez and Alex Ivliev and Stephan Mennicke and Markus
            Kr{\"{o}}tzsch},
  title  = {Efficient Dependency Analysis for Existential Rules},
  year   = {2023},
  month  = {May}
}