Fixed-point semantics and the representation of algorithms on large data
Michel de Rougemont · Very Large Data Bases · 1988
In the first part of this paper, we differen- tiate between two fixed-point semantics that can be used to interpret logic-programs using relations to- gether with functions: on the one hand the fixed-point semantic used in logic-programming ( 121, where no dif- ference is made between data and logical definitions, and on the other hand the fixed-point semantic used in the theory of inductive definitions 1131, where the logical definitions are interpreted relative to the data. We take a logic-program defining a boolean predicate P and show that if we follow the first semantic, P is interpreted as false, and that if we follow the second, P is always true. If we view the logic-program as a set r of axioms, then r +=/in P, whereas not ( I' /= P), i.e. P is a logical consequence for finite structures of r, but not a logical consequence of I'. In the second part of the paper, we illustrate this fun- damental distinction as we try to represent classical (and hence efficient) algorithms, by logic-programs. We take Shortest-paths algorithms on valued graphs as examples and in particular represent Dijkstra's shortest path algorithm as an inductive definition, un- der the operational semantic introduced in (7,6).