Search Strategy and Selection Function for an Inferential Relational System.

@article{DBLP:journals/tods/Minker78,
  author    = {Jack Minker},
  title     = {Search Strategy and Selection Function for an Inferential Relational
               System},
  journal   = {ACM Trans. Database Syst.},
  volume    = {3},
  number    = {1},
  year      = {1978},
  pages     = {1-31},
  ee        = {http://doi.acm.org/10.1145/320241.320242, db/journals/tods/Minker78.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

An inferential relational system is one in which data in the system consists of both explicit facts and general axioms (or "views"). The general axioms are used together with the explicit facts to derive the facts that are implicit (virtual relations) within the system. A top-down algorithm, as used in artificial intelligence work, is described to develop inferences within the system. The top-down approach starts with the query, a conjunction of relations, to be answered. Either a relational fact solves a given relation in a conjunct, or the relation is replaced by a conjunct of relations which must be solved to solve the given relation. The approach requires that one and only one relation in a conjunction be replaced (or expanded) by the given facts and general axioms. The decision to expand only a single relation is termed a selection function. It is shown for relational systems that such a restriction still guarantees that a solution to the problem will be found if one exists.

The algorithm provides for heuristic direction in the search process. Experimental results are presented which illustrate the techniques. A bookkeeping mechanism is described which permits one to know when subproblems are solved. It further facilitates the outputting of reasons for the deductively found answer in a coherent fashion.

Copyright © 1978 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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/An3-1 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/aDVD2 or /dvd

References

[1]

...

[2]

Chin-Liang Chang, James R. Slagle: An Admissible and Optimal Algorithm for Searching AND/OR Graphs. Artif. Intell. 2(2): 117-128(1971) BibTeX

[3]

...

[4]

...

[5]

Daniel H. Fishman: A Problem-Oriented Search Procedure for Theorem Proving. IEEE Trans. Computers 25(8): 807-815(1976) BibTeX

[6]

...

[7]

...

[8]

...

[9]

Richard B. Kieburtz, David C. Luckham: Compatibility and Complexity of Refinements of the Resolution Principle. SIAM J. Comput. 1(4): 313-332(1972) BibTeX

[10]

...

[11]

Robert A. Kowalski: Predicate Logic as Programming Language. IFIP Congress 1974: 569-574 BibTeX

[12]

Robert A. Kowalski, Donald Kuehner: Linear Resolution with Selection Function. Artif. Intell. 2(3/4): 227-260(1971) BibTeX

[13]

...

[14]

David C. Luckham, Nils J. Nilsson: Extracting Information from Resolution Proof Trees. Artif. Intell. 2(1): 27-54(1971) BibTeX

[15]

Jack Minker: Performing Inferences over Relation Data Bases. SIGMOD Conference 1975: 79-91 BibTeX

[16]

...

[17]

Jack Minker: Binary relations, matrices and inference developments. Inf. Syst. 3(1): 37-47(1978) BibTeX

[18]

Jack Minker, Daniel H. Fishman, James R. McSkimin: The Q^* Algorithm - A Search Strategy for a Deductive Question-Answering System. Artif. Intell. 4(3): 225-243(1973) BibTeX

[19]

...

[20]

...

[21]

...

[22]

...

[23]

...

[24]

John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX

[25]

Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX

[26]

...

[27]

...

[28]

Gordon J. van der Brug, Jack Minker: State-Space, Problem-Reduction, and Theorem Proving-Some Relationships. Commun. ACM 18(2): 107-115(1975) BibTeX

Referenced by

1. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
2. Cheong Youn, Hyoung-Joo Kim, Lawrence J. Henschen, Jiawei Han: Classification and Compilation of Linear Recursive Queries in Deductive Databases. IEEE Trans. Knowl. Data Eng. 4(1): 52-67(1992)
3. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
4. Eliezer L. Lozinskii: A Problem-Oriented Inferential Database System. ACM Trans. Database Syst. 11(3): 323-356(1986)
5. Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541
6. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
7. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
8. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
   Contents
9. Alain Pirotte: Fundamental and Secondary Issues in the Design of Non-Procedural Relational Languages. VLDB 1979: 239-250
10. Stanley Y. W. Su, Der Her Lo: A Semantic Association Model for Conceptual Design. ER 1979: 169-192