|
|
|
@inproceedings{DBLP:conf/sigmod/SagonasSW94a,
author = {Konstantinos F. Sagonas and
Terrance Swift and
David Scott Warren},
editor = {Richard T. Snodgrass and
Marianne Winslett},
title = {XSB as a Deductive Database},
booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
publisher = {ACM Press},
year = {1994},
pages = {512},
ee = {http://doi.acm.org/10.1145/191839.191970, db/conf/sigmod/sigmod94-512.html},
crossref = {DBLP:conf/sigmod/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
XSB is a logic-based programming system that can serve as an efficient in-memory Deductive Database (DDB) engine. XSB fundamentally extends the standard functionality of Prolog to include implementations of SLG resolution (tabling or memoing), and of HiLog.
Perhaps the most significant difference between the XSB implementation and conventional DDB implementations lies in XSB's use of SLG to extend tuple-at-a-time evaluation with bottom-up declarativity. This strategy can give XSB an advantage over other DDBs in object-oriented applications, where information can be kept in complex terms in addition to being distributed across many relations.
SLG resolution is useful for recursive query evaluation, allowing programs to terminate correctly in many cases where Prolog's SLD resolution does not. In particular, SLG computes all Datalog programs finitely with polynomial data complexity. SLG also provides a solution to the practical problem of Prolog's tendency to redundantly recompute subcomputations. For these reasons, users interested in memory-resident DDBs, Parsing, and Program Analysis applications may benefit from XSB. XSB's SLG implementation:
In addition, version 1.4 of XSB includes indexing capabilities greatly improved over those of standard Prolog systems. Users are offered the choice of Prolog-style hash-based indexing, or transformational indexing. In hash-based indexing, users can index on any argument, or on multiple arguments, removing a limitation of Prolog for data-oriented queries. Furthermore, users can index clauses with transformational indexing which builds a non-deterministic discrimination net, reducing unnecessary backtracking.
The current version of XSB provides significantly faster I/O capabilities than previous versions and emulator improvements. The time for reading formatted data seems roughly equivalent to the data load times of other DDB systems.
XSB has been tested on most common 32-bit hardware platforms running many versions of Unix and is available through anonymous ftp from cs.sunysb.edu.
Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...