@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.*

- Download PDF file (www.vldb.org, Darmstadt, Germany)
- Download PDF file (www.acm.org, New York, USA)

- Windows: Click the letter of your CD drive

A B C**D E**F G H I J K L M N O P Q R S T U V W X Y Z - Mac: Click here
- UNIX/LINUX: mount the CD and click on the path of your
*mount point*:

/Anthology/vldb7588 or /cdrom

- Windows: Click the letter of your CD drive

A B C**D E**F G H I J K L M N O P Q R S T U V W X Y Z - Mac: Click here
- UNIX/LINUX: mount the DVD and click on the path of your
*mount point*:

/Anthology/aDVD1 or /dvd

- [1]
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The Design and Analysis of Computer Algorithms.
Addison-Wesley 1974, ISBN 0-201-00029-6

- [2]
- Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
- [3]
- François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52
- [4]
- ...
- [5]
- Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982)
- [6]
- ...
- [7]
- ...
- [8]
- ...
- [9]
- ...
- [10]
- Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269
- [11]
- Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152
- [12]
- John W. Lloyd:
Foundations of Logic Programming, 1st Edition.
Springer 1984, ISBN 3-540-13299-6

- [13]
- ...
- [14]
- Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)