|
|
|
@inproceedings{DBLP:conf/vldb/Rougemont88,
author = {Michel de Rougemont},
editor = {Fran\c{c}ois Bancilhon and
David J. DeWitt},
title = {Fixed-point semantics and the representation of algorithms on
large data},
booktitle = {Fourteenth International Conference on Very Large Data Bases,
August 29 - September 1, 1988, Los Angeles, California, USA,
Proceedings},
publisher = {Morgan Kaufmann},
year = {1988},
isbn = {0-934613-75-3},
pages = {264-272},
ee = {db/conf/vldb/Rougemont88.html},
crossref = {DBLP:conf/vldb/88},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
In the first part of this paper, we differentiate between two fixed-point semantics that can be used to interpret logic-programs using relations together with functions: on the one hand the fixed-point semantic used in logic-programming [12], where no difference is made between data and logical definitions, and on the other hand the fixed-point semantic used in the theory of inductive definitions [13], 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 Gamma of axioms, then Gamma |=f in P, whereas not ( Gamma |= P), i.e. P is a logical consequence for finite structures of Gamma, but not a logical consequence of Gamma.
In the second part of the paper, we illustrate this fundamental 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, under the operational semantic introduced in [7,6].
Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.
