On the indiscernibility of individuals in logic programming
Thomas Eiter · Journal of Logic and Computation · 1997
According to Leibniz' principle, two individuals a and b are indiscernible, if they share the same properties. Indiscernibility of objects provides a potential for optimization in deductive systems, and has, for example, been exploited in the area of active database systems. In this paper, we address the issue of indiscernibility in logic programs and outline possible benefits for computation. After a formal definition of the notion of indiscernibility, we investigate some basic properties. The main contribution is then an analysis of the computational cost of checking indiscernibility of individuals (i.e. constants) in logic programs without function symbols, which we pursue in detail for ground logic programs. For the concern of query optimization, they show that online computation of indiscernibility is expensive, and thus suggest adopting an offline strategy, which may pay off for certain computational tasks.