Optimizations to Earley Deduction for DATALOG Programs 1
Harry H. Porter · 2009
The optimizations described below are designed to improve performance of the algorithm when there are large numbers of clauses with identical schemata. While it may often be the case that a DATALOG program has large numbers of unit clauses with the same schema, the real saving arises because many clauses with the same schema are derived during a typical deduction. The first optimization is a data structure that saves space when this condition is met. We then look at ways to do the subsumption checking and the reduction and instantiation steps quickly using this data representation.