ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
On the complexity of generating optimal plans with cross products (extended abstract)
Full text PdfPdf (2.01 MB)
Source Symposium on Principles of Database Systems archive
Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents
Tucson, Arizona, United States
Pages: 238 - 248  
Year of Publication: 1997
ISBN:0-89791-910-6
Authors
Wolfgang Scheufele  Universität Mannheim, Lehrstuhl für Praktische Informatik III, 68131 Mannheim, Germany
Guido Moerkotte  Universität Mannheim, Lehrstuhl für Praktische Informatik III, 68131 Mannheim, Germany
Sponsor
SIGMOD: ACM Special Interest Group on Management of Data
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 4,   Downloads (12 Months): 32,   Citation Count: 3
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/263661.263687
What is a DOI?

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
Sophie Cluet , Guido Moerkotte, On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products, Proceedings of the 5th International Conference on Database Theory, p.54-67, January 11-13, 1995
 
2
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
 
3
F. K. Hwang and G. J. Chang. Enumerating consecutive and nested partitions for graphs. DIMACS Technical Report 93-15, Rutgers University, 1993.
4
Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984  [doi>10.1145/1270.1498]
5
Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
 
6
Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
 
7
M. Minoux. Mathematical Programming. Theory and Algorithms. Wiley, 1986.
 
8
C. Monma and J. Sidney. Sequencing with seriesparallel precedence constraints. Math. Oper. Res., 4:215-224, 1979.
 
9
Kiyoshi Ono , Guy M. Lohman, Measuring the complexity of join enumeration in query optimization, Proceedings of the sixteenth international conference on Very large databases, p.314-325, September 1990, Brisbane, Australia
10
P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts  [doi>10.1145/582095.582099]
 
11
Louis Shapiro , A. B. Stephens, Bootstrap percolation, the Schro¨der numbers, and the N-kings problem, SIAM Journal on Discrete Mathematics, v.4 n.2, p.275-280, May 1991  [doi>10.1137/0404025]
 
12
Eugene J. Shekita , Honesty C. Young , Kian-Lee Tan, Multi-Join Optimization for Symmetric Multiprocessors, Proceedings of the 19th International Conference on Very Large Data Bases, p.479-492, August 24-27, 1993
 
13
M. Steinbrunn, G. Moerkotte, and A. Kemper. Optimizing join orders. Technischer Bericht MIP-9307, Universit~.t Passau, September 1993.
 
14
Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
15
Bennet Vance , David Maier, Rapid bushy join-order optimization with Cartesian products, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.35-46, June 04-06, 1996, Montreal, Quebec, Canada

CITED BY  3
Donald Kossmann , Konrad Stocker, Iterative dynamic programming: a new class of query optimization algorithms, ACM Transactions on Database Systems (TODS), v.25 n.1, p.43-82, March 2000
Zhimin Chen , Vivek Narasayya, Efficient computation of multiple group by queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Yong-Xuan Lai , Yi-Long Chen , Hong Chen, PEJA: progressive energy-efficient join processing for sensor networks, Journal of Computer Science and Technology, v.23 n.6, p.957-972, November 2008

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation


General Terms:
Algorithms, Measurement, Performance, Verification

Collaborative Colleagues:
Wolfgang Scheufele: colleagues
Guido Moerkotte: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player