ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Fixed-point semantics and the representation of algorithms on large data.

Michel de Rougemont: Fixed-point semantics and the representation of algorithms on large data. VLDB 1988: 264-272
@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}
}

Abstract

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.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

Copyright © Tue Mar 16 02:21:59 2010 by Michael Ley (ley@uni-trier.de)