|
 ABSTRACT
SLD resolution with negation as finite failure (or SLDNF) reflects the procedural interpretation of Horn-clause predicate logic as a programming language and forms the computational basis for prolog systems. Despite its advantages in memory management, SLDNF is often not appropriate for query evaluation for three reasons; a) it may not terminate due to infinite positive recursion; b) it may not terminate due to infinite recursion through negation; and c) it may repeatedly evaluate the same clause body literal, leading to unacceptable performance.
We address all three problems for goal-oriented query evaluation of arbitrary programs by presenting an extension of SLDNF, called SLG resolution, with the following distinctive features:
- (i) SLG resolution is a partial deduction procedure, consisting of several transformations. Each query is transformed step by step into a set of answer clauses;
- (ii) SLG resolution is sound and ideally complete for all non-floundering queries with respect to all three-valued stable models (including the well founded partial model);
- (iii) SLG resolution allows an arbitrary computation rule and an arbitrary control strategy for selecting transformations to apply;
- (iv) SLG resolution avoids both positive and negative loops and always terminates for programs with the bounded-term-size property;
- (v) SLG resolution has a polynomial time data complexity for well founded negation.
Restricted forms of SLG resolution are identified for definite, locally stratified, and modularly stratified programs, thereby shedding light on the role each transformation plays. To provide answers to a query under different three-valued stable models, SLG resolution can be enhanced by further processing of the derived set of answer clauses.
SLG resolution makes many more clausal specifications into effective programs. With simple (user or computer generated) annotations, SLDNF resolution and SLG resolution can be fully integrated. Thus a system including SLG resolution can be fully integrated. Thus a system including SLG resolution is naturally upward compatible with Prolog. For all these reasons we believe that SLG resolution will provide the computational basis for the next generation of logic programming systems.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
 |
2
|
Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States
[doi> 10.1145/6012.15399]
|
| |
3
|
|
| |
4
|
W. Chen, T. Swift, and D.S. Warren. Implementations of the well founded semantics. In Preparation.
|
| |
5
|
W. Chen and D.S. Warren. Towards effective evaluation of general logic programs. Technical Report 93-CSE-11, Department of Computer Science and Engineering, Southern Methodist University, 1993.
|
| |
6
|
W. Chen and D.S. Warren. A goal-oriented approach to computing well founded semantics. In Joint Intl. Conference and Symposium on Logic Programming, November 1992. also available as SMU Technical Report 92-CSE-9.
|
| |
7
|
K.L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 293-322. Plenum, New York, 1978.
|
| |
8
|
S.W. Dietrich and D.S. Warren. Extension tables: Memo relations in logic programming. Technical Report 86/18, Department of Computer Science, SUNY at Stony Brook, 1986.
|
| |
9
|
David B. Kemp, Peter J. Stuckey, and Divesh Srivastava. Magic sets and bottom-up evaluation of well-founded models. In Intl. Logic Programming Symposium, pages 337-351, 1991.
|
| |
10
|
David B. Kemp, Peter J. Stuckey, and Divesh Srivastava. Query restricted bottom-up evaluation of normal logic programs. In Joint Intl. Conference and Symposium on Logic Programming, pages 288- 302, 1992.
|
| |
11
|
D.B. Kemp and R.W. Topor. Completeness of a top-down query evaluation procedure for stratified databases. In Joint Intl. Conference and Symposium on Logic Programming, pages 178-194, 1988.
|
| |
12
|
J. Komorowski. Towards a programming methodology founded on partial deduction. In Proceedings of the European Conference on Artificial Intelligence, 1990.
|
| |
13
|
|
| |
14
|
|
| |
15
|
S. Morishita. An alternating fixpoint tailored to magic programs. In Proceedings of the Deductive Database Workshop at Joint International Conference and Symposium on Logic Programming, 1992.
|
| |
16
|
H. Przymusinska and T.C. Przymusinski. Weakly perfect model semantics for logic programs. In R.A. Kowalski and K.A. Bowen, editors, Joint Intl. Conference and Symposium on Logic Programming, pages 1106-1120, 1988.
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
R. Ramakrishnan, D. Srivastava, and S. Sudarshan. Controlling the search in bottom-up evaluation. In Joint Intl. Conference and Symposium on Logic Programming, pages 273-287, 1992.
|
| |
22
|
|
| |
23
|
|
| |
24
|
|
| |
25
|
|
| |
26
|
H. Seki and H. Itoh. A query evaluation method for stratified programs under the extended cwa. In Joint Intl. Conference and Symposium on Logic Programming, pages 195-211, 1988.
|
| |
27
|
|
| |
28
|
|
| |
29
|
|
| |
30
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.2