Home Online Resources Table of Contents

Journal of Logic and Computation, Volume 7, Issue 6: December 1997.

On the indiscernibility of individuals in logic programming

T Eiter1, G Gottlob2 and N Leone2

1Institut fur Informatik, Universitat Giessen, Arndtstrasse 2, D-35392 Giessen, Germany. E-mail: eiter@informatik.uni-giessen.de, 2Information Systems Institute, TU Vienna, Paniglgasse 16, A-1040 Vienna, Austria. E-mail: {gottlob,leone}@dbai.tuwien.ac.at

According to Leibniz' principle, two individuals a and b are indiscernible, if they share the same properties. Indiscernibility of objects provide 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 the certain computational tasks.

Pages 805-824

This page is run by Oxford University Press, Great Clarendon Street, Oxford OX2 6DP, UK
as part of the OUP Journals World Wide Web service.
Comments and feedback: www-admin@oup.co.uk
URL: http://www.oup.co.uk/logcom/hdb/Volume_07/Issue_06/070805.sgm.abs.html
Last modification: 16 April 1998.
Copyright© Oxford University Press, 1998.