Efficient Instantiation of Disjunctive Databases
Nicola Leone, Simona Perri, Wolfgang Faber, Gerald Pfeifer · 2001
Most deductive database systems are endowed with an instantiation module. The instantiator generates a new program which is equivalent to the input program, but does not contain any variables (i.e., it is ground). The instantiation process may be computationally expensive in some cases, and the instantiator is crucial for the efficiency of the entire ASP system. In this report we describe the instantiation procedure of DLV system, which is one of its strong points. Using differential and other advanced database techniques together with suitable data structures, the DLV instantiator efficiently generates a ground instantiation of the input that has the same stable models as the full program instantiation, but is much smaller in general. Moreover, in case of normal stratified programs, it already computes the single stable model without producing any instantiation.