The Complexity of Ordering Subgoals.

Jeffrey D. Ullman, Moshe Y. Vardi: The Complexity of Ordering Subgoals. PODS 1988: 74-81

@inproceedings{DBLP:conf/pods/UllmanV88,
  author    = {Jeffrey D. Ullman and
               Moshe Y. Vardi},
  title     = {The Complexity of Ordering Subgoals},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {74-81},
  ee        = {http://doi.acm.org/10.1145/308386.308417, db/conf/pods/UllmanV88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Selection of an appropriate order for the evaluation of subgoals in a logical rule frequently is essential for efficiency. We formulate the problem as one of feasible subgoal orders and show that the question is inherently exponential in time. The proof is by reduction from linear-space alternating Turing machine recognition, which appears to be far easier, in this case, than the more obvious reduction from exponential-time (ordinary) Turing machines.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

References

[Bancilhon et al. 1986]: François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[Chandra et al. 1981]: Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX
[Cook 1974]: Stephen A. Cook: An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. 9(3): 308-316(1974) BibTeX
[Morris 1988]: Katherine A. Morris: An Algorithm for Ordering Subgoals in NAIL! PODS 1988: 82-88 BibTeX
[Morris et al. 1987]: Katherine A. Morris, Jeffrey F. Naughton, Yatin P. Saraiya, Jeffrey D. Ullman, Allen Van Gelder: YAWN! (Yet Another Window on NAIL!). IEEE Data Eng. Bull. 10(4): 28-43(1987) BibTeX
[Sacca and Zaniolo 1987]: Domenico Saccà, Carlo Zaniolo: Implementation of Recursive Queries for a Data Language Based on Pure Horn Logic. ICLP 1987: 104-135 BibTeX
[Shapiro 1984]: Ehud Y. Shapiro: Alternation and the Computational Complexity of Logic Programs. J. Log. Program. 1(1): 19-33(1984) BibTeX
[Ullman 1985]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

Referenced by

Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
Katherine A. Morris: An Algorithm for Ordering Subgoals in NAIL! PODS 1988: 82-88

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]