Online Papers Printing Instructions

Please use psnup to print online papers: 2 to a page.  

  For North American papers:  psnup -n2 -r  | lpr -Pps1
  For European papers:        psnup -n2 -r -SA4  | lpr -Pps1

Please remember also to delete postscript files from your home directories
after printing.

Block 0: Introduction to Object-Oriented Databases, Query Languages and Algebras

January 29: An Introduction to Object Oriented Databases
Lecturer: Stan Zdonik 

Required Readings:  

 Fundamentals of Object-Oriented Databases, (Provided in class),
 Introduction to the book, 'Readings in Object-Oriented Databases',
 David Maier and Stanley B. Zdonik, Morgan-Kaufman, 1990.


Supplemental Readings:  

 M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdonik. 
 The Object-Oriented Database System Manifesto, (Online),
 In Proceedings of the First International Conference on Deductive and 
 Object-Oriented Databases, pages 223-40, Kyoto, Japan, December 1989. Also appears 
 in Building an Object-Oriented Database System: The Story of O2. F. Bancilhon, C. Delobel, 
 and P. Kanellakis. (eds.) Morgan Kaufmann, 1992. 

 O. Deux et al.
 The O2 System, (Provided in class), 
 In Communications of the ACM, Volume 34 (10), October, 1991. 

 Paul Butterworth, Amos Otis and Jacob Stein.
 The Gemstone Object Database Management System, (Provided in class), 
 In Communications of the ACM, Volume 34 (10), October, 1991.

January 31: Intro (cont.), Equality and Mutability

Lecturers:  

 Stan Zdonik 
 Mitch Cherniack 

 
Required Readings:  

 Mitch Cherniack, Stanley B. Zdonik and Marian H. Nodine.
 To Form A More Perfect Union (Intersection, Difference), (Online),
 In Database Programming Languages (DBPL-5), Proceedings of the Fifth 
 International Workshop on Database Programming Languages, Gubbio, Italy, 
 September 1995.  To appear.


Supplemental Readings:  

 Henry Baker.
 Equal Rights for Functional Objects or, 
 The More Things Change, The More They Are The Same, (Online), 
 OOPS Messenger, 4 (4): pp. 1 - 26, October, 1993.

 Peter Grogono and Patrice Chalin.
 Copying, Sharing and Aliasing, (Online), 
 In the Colloquium on Object-Orientation in Databases and Software Engineering, 
 Montreal, Quebec, 1994.

 Peter Grogono and Philip Santas.
 Equality and Assignment in Object-Oriented Languages, (Online), 
 In EastEurOOPe '93, pp. 191 - 201, November, 1993.

 Gail M. Shaw and Stanley B. Zdonik.
 Object-Oriented Queries: Equivalence and Optimization, (Online), 
 In Won Kim, Jean-Marie Nicolas and Shojiro Nishioe (eds.),	
 Proceedings of the First International Conference on Deductive
 and Object-Oriented Databases, pp. 264--278, Kyoto, Japan, December, 1989.

February 5: Common Languages for Discourse - OQL and KOLA

Lecturers:  

 Stan Zdonik 
 Mitch Cherniack 

 
Required Readings:  

 R. G. G. Cattell (ed.). 
 Object Query Language. (On Reserve)
 Chapter 4 of The Object Database Standard: ODMG-93, Release 1.2,
 Morgan-Kaufman, 1993.

 Mitch Cherniack.
 Form(ers) over Function(s): The KOLA Query Algebra, (Online),
 Technical Report, Brown University, December, 1995.


Supplemental Readings:  

 Mitch Cherniack and Stanley B. Zdonik.
 Rule Languages and Internal Algebras for Rule-Based Optimizers, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on Management of Data,
 Montreal, Canada, June 1996, To appear. 

Block 1: Optimization of Relational Queries

February 7, 12, 14, 21 (No class 19th)
 
Readings:  

 Matthias Jarke and Jurgen Koch. 
 Query Optimization in Database Systems, (In Package), ACM Computing Surveys,
 vol. 16 (2), pp. 111-152, June, 1984.

 Goetz Graefe.
 Query Evaluation Techniques for Large Databases, (Online),
 ACM Computing Surveys, pp. 73-170, June 1993.

 Eugene Wong and Karel Youssefi.
 Decomposition - A Strategy for Query Processing, (In Package),
 TODS 1 (2), pp. 223-241, September, 1976.

 Priti Mishra and Margaret H. Eich.
 Join Processing in Relational Databases, (In Package)
 ACM Computing Surveys 24 (1), pp. 63-113, March 1992.

 Bennet Vance and David Maier. 
 Rapid Bushy Join-order Optimization with Cartesian Products, (Online),
 In Proceedings of the ACM SIGMOD International Conference on Management of Data,
 Montreal, Canada, 1996 (To Appear).
  







Block 2: Optimizing with Encapsulated Methods and Predicates
February 26, 28, March 4, 6 
 
Readings:  

Methods

 Richard L. Cole and Goetz Graefe.  
 Optimization of Dynamic Query Evaluation Plans (Handed Out In Class), 
 In Richard T. Snodgrass and Marianne Winslett (Eds.),
 Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 
 Minneapolis, Minnesota, May 24 - May 27, 1994.
 pp. 150-160, 1989.

 Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim and Timos K. Sellis. 
 Parametric Query Optimization, (On reserve),
 In Li-Yan Yuan (Ed.), 18th International Conference on Very Large Data Bases, 
 August 23-27, 1992, Vancouver, Canada, Proceedings. Morgan Kaufmann, p.103-114.

 Alfons Kemper, Christoph Kilger, Guido Moerkotte.
 Materialization of Functions in Object Bases: 
 Design, Implementation and Assessment, (Online),
 IEEE Trans. Knowledge and Database Engineering, 1992. 

 Vassilis Christophides, Sophie Cluet and Guido Moerkotte. 
 Evaluating Queries with Generalized Path Expressions, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on Management of Data,
 Montreal, Canada, June 1996, To appear. 

 Joseph M. Hellerstein and Jeffrey F. Naughton.
 Query Execution Techniques for Caching Expensive Methods, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on Management of Data,
 Montreal, Canada, June 1996, To appear. 


Predicates

 Joseph M. Hellerstein. 
 Practical Predicate Placement, (Online),
 In Proceedings of the ACM SIGMOD International Conference on Management 
 of Data, Minneapolis, May, 1994. 

 Alfons Kemper, Guido Moerkotte, Klaus Peithner and Michael Steinbrunn. 
 Optimizing Disjunctive Queries with Expensive Predicates, (Online), 
 In Richard T. Snodgrass, Marianne Winslett (Eds.), Proceedings of the 
 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, 
 May 24-27, 1994. SIGMOD Record 23(2), June 1994 

 Michael Steinbrunn, Klaus Peithner, Guido Moerkotte and Alfons Kemper.
 Bypassing Joins in Disjunctive Queries, (Online),
 In 21st International Conference on Very Large Data Bases, 
 September 11-15, 1995, Zurich, Switzerland. Proceedings: Morgan Kaufmann. 








Block 3: Cost Models and Indices
March 11, 13, 18, 20
 
Readings:
  
Indexing

 David Maier and Jacob Stein. 
 Indexing in an Object-Oriented DBMS, In Klaus R. Dittrich, Umeshwar Dayal (Eds.), (On Reserve),
 1986 International Workshop on Object-Oriented Database Systems, September 23-26, 1986, 
 Asilomar Conference center, Pacific Grove, California, USA. pp. 171-182.

 Alfons Kemper, Guido Moerkotte.
 Access Support Relations: An Indexing Method for Object Bases, (Online),
 Information Systems 17(2), 117-145, 1992.

 Martin Erwig and Udo W. Lipeck.
 A Functional DBPL Revealing High Level Optimizations, (On Reserve), 
 In Paris Kanellakis, Joachim W. Schmidt (Eds.), 
 Database Programming Languages: Bulk Types and Persistent 
 Data. 3rd International Workshop, August 27-30, 1991, Nafplion, Greece, 
 Proceedings. Morgan Kaufmann, San Mateo, CA. pp. 306-321.

 Sridhar Ramaswamy and Paris C. Kanellakis.
 OODB Indexing by Class-Division.   In Michael J. Carey, Donovan A. Schneider (Eds.), 
 Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, 
 San Jose, California, May 22-25, 1995. SIGMOD Record 24(2), June 1995, pp. 139-150.



Cost Models

 Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie and Thomas G. Price. 
 Access Path Selection in a Relational Database Management System, (Handed Out In Class),
 In Philip A. Bernstein (Ed.), Proceedings of the 1979 ACM SIGMOD International 
 Conference on Management of Data, Boston, Massachusetts, 
 May 30 - June 1, 1979. ACM, New York 1979. pp. 23-34.

 Peter J. Haas, Jeffrey F. Naughton, S. Seshadri and L. Stokes.
 Sampling-Based Estimation of the Number of Distinct Values of an Attribute, (On Reserve), 
 In 21st International Conference on Very Large Data Bases, 
 September 11-15, 1995, Zurich, Switzerland. Proceedings: Morgan Kaufmann. 

 Alberto Belussi and Christos Faloutsos.
 Estimating the Selectivity of Spatial Queries Using the 'Correlation' 
 Fractal Dimension, (Online),
 In 21st International Conference on Very Large Data Bases, 
 September 11-15, 1995, Zurich, Switzerland. Proceedings: Morgan Kaufmann. 
 
 Georges Gardarin, Jean-Robert Gruser abd Zhao-Hui Tang.
 A Cost Model for Clustered Object-Oriented Databases, (On Reserve),
 In 21st International Conference on Very Large Data Bases, 
 September 11-15, 1995, Zurich, Switzerland. Proceedings: Morgan Kaufmann. 
 







Block 4: Optimizing Nested Queries and Aggregates
April 1, 3, 8, 10 (No class March 23 - 31) 

Readings:
  
Nested Queries

 M. Muralikrishna.
 Improved Unnesting Algorithms for Join Aggregate SQL Queries, (On Reserve),
 In Le-Yan Yuan (Ed.), 18th International Conference on Very Large Data Bases, August 23-27, 1992,
 Vancouver, Canada. Morgan Kaufmann, pp. 91-102.

 Richard A. Ganski, Harry K. T. Wong. 
 Optimization of Nested SQL Queries Revisited, (In Package),
 In Umeshwar Dayal, Irv Traiger (Eds.), Proceedings of 
 the Association for Computing Machinery Special Interest Group 
 on Management of Data 1987 Annual Conference, San Francisco, California, 
 May 27-29, 1987. SIGMOD Record 16(3), December 1987, pp. 23-33.

 Umeshwar Dayal.
 Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested 
 Subqueries, Aggregates, and Quantifiers, (TBA),
 In Peter M. Stocker, William Kent, Peter Hammersley (Eds.), 13th International
 Conference on Very Large Data Bases, September 1-4, 1987, 
 Brighton, England, Proceedings. Morgan Kaufmann, pp. 197-208.

 Sophie Cluet, Guido Moerkotte.
 Nested Queries in Object Bases, (Online), 
 In Catriel Beeri, Atsushi Ohori, Dennis E. Shasha (Eds.), 
 Database Programming Languages (DBPL-4), Proceedings of the Fourth International 
 Workshop on Database Programming Languages -
 Object Models and Languages, Manhattan, New York City, USA, 30 August - 1 September 1993. 
 Workshops in Computing, Springer 1994, pp. 226-242.  A longer, more detailed
 version is here.

 Mitch Cherniack and Stanley B. Zdonik.
 Rule Languages and Internal Algebras for Rule-Based Optimizers, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on Management of Data,
 Montreal, Canada, June 1996, To appear. 



Aggregates

 Venky Harinarayan, Jeff Ullman and Anand Rajaraman.
 Implementing Data Cubes Efficiently, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on 
 Management of Data, Montreal, Canada, June 1996, To appear. 

 Sophie Cluet and Guido Moerkotte.
 Efficient Evaluation of Aggregates on Bulk Types, (Online),
 In Database Programming Languages (DBPL-5), Proceedings of the Fifth International 
 Workshop on Database Programming Languages, Gubbio, Italy, September 1995.  To appear.

 Weipang P. Yan and Per-Ake Larson.
 Eager Aggregation and Lazy Aggregation, (On Reserve),
 In 21st International Conference on Very Large Data Bases, 
 September 11-15, 1995, Zurich, Switzerland. Proceedings: Morgan Kaufmann. 









Block 5: Alternative Bulk Types, Data and Queries
April 15, 17, 22, 24
 

Readings:
  

 Val Tannen, Peter Buneman, Shamim A. Naqvi. 
 Structural Recursion as a Query Language, (Online),
 In Paris Kanellakis, Joachim W. Schmidt, 
 Database Programming Languages: Bulk Types and Persistent Data. 
 3rd International Workshop, August 27-30, 1991, Nafplion, Greece, 
 Proceedings. Morgan Kaufmann, pp. 9 - 19.

 Leonidas Fegaras and David Maier. 
 Towards an Effective Calculus for Object Query Languages, (Online), 
 In Michael J. Carey, Donovan A. Schneider (Eds.), 
 Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, 
 San Jose, California, May 22-25, 1995. SIGMOD Record 24(2), June 1995, pp. 47-58.

 Catriel Beeri and Yoram Kornatzky.
 Algebraic Optimization of Object-Oriented Query Languages, (On Reserve),
 In S. Abiteboul, P. C. Kanellakis (Eds.), 
 ICDT'90, Third International Conference on Database Theory, Paris, France, December 12-14, 1990, 
 Proceedings. Lecture Notes in Computer Science, Vol. 470, Springer, 1990, pp. 72-88.

 Peter Buneman, Susan Davidson, Gerd Hillebrand and Dan Suciu.
 A Query Language and Optimization Techniques for Unstructured Data, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on Management of Data,
 Montreal, Canada, June 1996, To appear. 

 Leonid Libkin, Rona Machlin and Limsoon Wong.
 A Query Language for Multidimensional Arrays: 
 Design, Implementation and Optimization Techniques, (Online),
 In Proceedings of the ACM SIGMOD International Conferences on Management of Data,
 Montreal, Canada, June 1996, To appear. 

 Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg and Stanley B. Zdonik. 
 The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases, (Online),
 In P. S. Yu, A. L. P. Chen (Eds.), Proceedings of the Eleventh 
 International Conference on Data Engineering, March 6-10, 1995, 
 Taipei, Taiwan, pp. 80-89.

 Dallan Quass, Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman and Jennifer Widom. 
 Querying Semistructured Heterogeneous Information, (Online), 
 In Tok Wang Ling, Alberto O. Mendelzon, Laurent Vieille (Eds.), 
 Deductive and Object-Oriented Databases, 
 Fourth International Conference, DOOD'95, Singapore, 
 December 4-7, 1995, Proceedings. Lecture Notes in Computer Science,  
 Vol. 1013, Springer 1995. (pp. 319-344).

 D. Konopnicki and O. Schmueli
 W3QS: A Query System for the World-Wide Web, (TBA), 
 In 21st International Conference on Very Large Data Bases, 
 September 11-15, 1995, Zurich, Switzerland. Proceedings: Morgan Kaufmann. 

 TBA