A Variant of Earley Deduction With Partial Evaluation

2014/05/22 by Heike Stephan, Stephan, Heike, Stefan Brass +1
Computer Science · #Advanced Database Systems and Queries #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies #cs.DB #cs.LO

paper · pdf · doi:10.48550/arxiv.1405.5645

WLP 2012

arxiv created 2014/05/22 · arxiv updated 2014/05/23

Abstract

We present an algorithm for query evaluation given a logic program consisting of function-free Datalog rules. It is based on Earley Deduction [4, 6] and uses a partial evaluation similar to the one we devel oped for our SLDMagic method [1]. With this, finite automata modeling the evaluation of given queries are generated. In certain cases, the new method is more efficient than SLDMagic and the standard Magic Set method since it can process several deduction steps as one.

Related

• Application of Methods for Syntax Analysis of Context-Free Languages to Query Evaluation of Logic Programs
• A Linear Algebraic Approach to Datalog Evaluation
• Query Evaluation in DatalogMTL -- Taming Infinite Query Results
• An Evaluation Algorithm for Datalog with Equality
• Querying Incomplete Data : Complexity and Tractability via Datalog and First-Order Rewritings