sigmod_1995_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>A critique of ANSI SQL isolation levels</title><author><AuthorName>Hal Berenson</AuthorName><institute><InstituteName>Microsoft Corp.</InstituteName><country></country></institute></author><author><AuthorName>Phil Bernstein</AuthorName><institute><InstituteName>Microsoft Corp.</InstituteName><country></country></institute></author><author><AuthorName>Jim Gray</AuthorName><institute><InstituteName>U.C. Berkeley</InstituteName><country></country></institute></author><author><AuthorName>Jim Melton</AuthorName><institute><InstituteName>Sybase Corp.</InstituteName><country></country></institute></author><author><AuthorName>Elizabeth O'Neil</AuthorName><institute><InstituteName>UMss/Boston</InstituteName><country></country></institute></author><author><AuthorName>Patrick O'Neil</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>ANSI X3.135-1992, American National Standard for Information Systems -- Database Language -- SQL, November, 1992</name><name>V. Atluri, E. Bertino, S. Jajodia, "A Theoretical Formulation for Degrees of Isolation in Databases," Technical Report, George Mason University, Fairfax, VA, 1995</name><name>Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987</name><name>C. J. Date, An introduction to database systems: vol. 1 (5th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>C.J. Date and C. J. White, "A Guide to DB2," Third Edition, Addison-Wesley, 1989.</name><name>K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976</name><name>J. N. Gray , R. A. Lorie , G. R. Putzolu , I. L. Traiger, Granularity of locks and degrees of consistency in a shared data base, Readings in database systems (3rd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998</name><name>Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Lilian Hobbs , Ken England, Rdb/VMS: a comprehensive guide, Digital Press, Newton, MA, 1991</name><name>Illustra Information Technologies, "Illustra User's Guide," , Illustra information Technologies, Oakland, CA. 1994.</name><name>Jim Melton , Alan R. Simon, Understanding the new SQL: a complete guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993</name><name>P. O'Neil, E. O'Neil, H. Berenson, P. Bemstein, J. Gray, J. Melton, "An Investigation of Transactional Isolation Levels," UMass/Boston Dept. of Math &amp; C.S. Preprint.</name><name>"'PL/SQL User's Guide and Reference, Version 1.0," Part. 800-V 1.0, Oracle Corp., 1989.</name><name>Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986</name><name>Patrick O'Neil, Database systems: principles, programming, performance, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994</name><name>David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983</name><name>Michael Stonebraker, The design of the POSTGRES storage system, Readings in database systems (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994</name><name>M. Thakaar, "Transaction Models in InterBase 4," Proceedings of the Borland international Conference, June 1994.</name></citation><abstract>ANSI SQL-92 [MS, ANSI] defines Isolation Levels in terms of phenomena: Dirty Reads, Non-Repeatable Reads, and Phantoms. This paper shows that these phenomena and the ANSI SQL definitions fail to properly characterize several popular isolation levels, including the standard locking implementations of the levels covered. Ambiguity in the statement of the phenomena is investigated and a more formal statement is arrived at; in addition new phenomena that better characterize isolation types are introduced. Finally, an important multiversion isolation type, called Snapshot Isolation, is defined.</abstract></paper><paper><title>Recovery protocols for shared memory database systems</title><author><AuthorName>Lory D. Molesky</AuthorName><institute><InstituteName>Department of Computer Science, University of Massachusetts, Amherst, MA</InstituteName><country></country></institute></author><author><AuthorName>Krithi Ramamritham</AuthorName><institute><InstituteName>Department of Computer Science, University of Massachusetts, Amherst, MA</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Panel Discussion on Shared Nothing, Shared Disk, and Shared Memory Database Systems. Proceedings of the 1994 ACM SIGMOD international Conference on Management of Data, 23, May 1994.</name><name>James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986</name><name>Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987</name><name>Anupam Bhide, An Analysis of Three Transaction Processing Architectures, Proceedings of the 14th International Conference on Very Large Data Bases, p.339-350, August 29-September 01, 1988</name><name>Anupam Bhide , Michael Stonebraker, A Performance Comparison of Two Architectures for Fast Transaction Processing, Proceedings of the Fourth International Conference on Data Engineering, p.536-545, February 01-05, 1988</name><name>J. Chapin. Personal Communication. 1995.</name><name>Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983</name><name>Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States</name><name>D. Johnson and W. Zwaenepoel. Sender-Based Message Logging. Proceedings of the 17th International Symposium on Fault-Tolerant Computing, pages 14-19, 1987.</name><name>Nancy P. Kronenberg , Henry M. Levy , William D. Strecker, VAXcluster: a closely-coupled distributed system, ACM Transactions on Computer Systems (TOCS), v.4 n.2, p.130-146, May 1986</name><name>J. Kuskin , D. Ofelt , M. Heinrich , J. Heinlein , R. Simoni , K. Gharachorloo , J. Chapin , D. Nakahira , J. Baxter , M. Horowitz , A. Gupta , M. Rosenblum , J. Hennessy, The Stanford FLASH multiprocessor, Proceedings of the 21ST annual international symposium on Computer architecture, p.302-313, April 18-21, 1994, Chicago, Illinois, United States</name><name>David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993</name><name>Barbara Liskov , Robert Scheifler, Guardians and actions: linguistic support for robust, distributed programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.7-19, January 25-27, 1982, Albuquerque, Mexico</name><name>David Lomet , Betty Salzberg, Access method concurrency with recovery, ACM SIGMOD Record, v.21 n.2, p.351-360, June 1, 1992</name><name>C. Mohan , Don Haderle, Algorithms for flexible space management in transaction systems supporting fine-granularity locking, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.131-144, May 1994, Cambridge, United Kingdom</name><name>C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992</name><name>C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, ACM SIGMOD Record, v.21 n.2, p.371-380, June 1, 1992</name><name>C. Mohan , Inderpal Narang, Recovery and Coherency-Control Protocols for Fast Intersystem Page Transfer and Fine-Granularity Locking in a Shared Disks Transaction Environment, Proceedings of the 17th International Conference on Very Large Data Bases, p.193-207, September 03-06, 1991</name><name>Lory D. Molesky , Krithi Ramamritham, Efficient Locking for Shared Memory Database Systems, University of Massachusetts, Amherst, MA, 1994</name><name>E. Rahm. Concurrency and Coherency Control in Database Sharing Systems. Technical Report, University of KaisersIautern, Germany, December 1991.</name><name>E. Rahm. Use of Global Extended Memory for Distributed Transaction Processing. Proceedings of the 4th Int. Workshop on High Performance Transaction Systems, AsiIomar, CA., September 1991.</name><name>T. Rengarajan, P. Spiro, and W. Wright. High Availability Mechanisms of VAX DBMS Software. Digital Technical Journal, (8):88-98, February 1989.</name><name>Kendall Square Research. KSR1 Principles of Operation. KSR Research. Waltham, Mass., 1992.</name><name>W. Snaman and D. Thiel. The VAX/VMS Distributed Lock Manager. Digital Technical Journal, (5):29-44, September 1987.</name><name>R. Strom, D. Bacon, and S. Yemini. Volatile Logging in n- Fault-Tolerant Distributed Systems. Proceedings of the 18th International Symposium on Fault-Tolerant Computing, pages 44-49, 1988.</name><name>S. Thakkar and M. Sweiger. Performance of an OLTP Application on Symmetry Multiprocessor System. Proceedings of the 17th International Symposium on Computer Architecture, pages 228-238, May 1990.</name><name>P. S. Yu , A. Dan, Performance Evaluation of Transaction Processing Coupling Architectures for Handling System Dynamics, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.139-153, February 1994</name></citation><abstract>Significant performance advantages can be gained by implementing a database system on a cache-coherent shared memory multiprocessor. However, problems arise when failures occur. A single node (where a node refers to a processor/memory pair) crash may require a reboot of the entire shared memory system. Fortunately, shared memory multiprocessors that isolate individual node failures are currently being developed. Even with these, because of the side effects of the cache coherency protocol, a transaction executing strictly on a single node may become dependent on the validity of the memory of many nodes thereby inducing unnecessary transaction aborts. This happens when database objects, such as records, and database support structures, such as index structures and shared lock tables, are stored in shared memory.In this paper, we propose crash recovery protocols for shared memory database systems which avoid the unnecessary transaction aborts induced by the effects of using shared physical memory. Our recovery protocols guarantee that if one or more nodes crash, all the effects of active transactions running on the crashed nodes will be undone, and no effects of transactions running on nodes which did not crash will be undone. In order to show the practicality of our protocols, we discuss how existing features of cache-coherent multiprocessors can be utilized to implement these recovery protocols. Specifically, we demonstrate that (1) for many types of database objects and support structures, volatile (in-memory) logging is sufficient to avoid unnecessary transaction aborts, and (2) a very low overhead implementation of this strategy can be achieved with existing multiprocessor features.</abstract></paper><paper><title>Efficient optimistic concurrency control using loosely synchronized clocks</title><author><AuthorName>Atul Adya</AuthorName><institute><InstituteName>Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA</InstituteName><country></country></institute></author><author><AuthorName>Robert Gruber</AuthorName><institute><InstituteName>Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA</InstituteName><country></country></institute></author><author><AuthorName>Barbara Liskov</AuthorName><institute><InstituteName>Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA</InstituteName><country></country></institute></author><author><AuthorName>Umesh Maheshwari</AuthorName><institute><InstituteName>Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Adya, A, Transaction Management for Mobile Objects Using Optimistic Concurrency Control, Massachusetts Institute of Technology, Cambridge, MA, 1994</name><name>D. Agrawal, A. J. Bemstein, P. Gupta, and S. Sengupta. Distributed Multi-version Optimistic Concurrency Control with Reduced Rollback. Distributed Computing, 2(1), 1987.</name><name>Paul Butterworth , Allen Otis , Jacob Stein, The GemStone object database management system, Communications of the ACM, v.34 n.10, p.64-77, Oct. 1991</name><name>Michael J. Carey , Michael J. Franklin , Markos Zaharioudakis, Fine-grained sharing in a page server OODBMS, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.359-370, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>Michael J. Carey , David J. DeWitt , Jeffrey F. Naughton, The 007 Benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.12-21, May 25-28, 1993, Washington, D.C., United States</name><name>S. Ceil and S. Owicki. On the Use of Optimistic Methods for Concurrency Control in Distributed Databases. In Proceedings of the 6th Berkeley Workshop, 1982.</name><name>Mark Stuart Day , Barbara Liskov, Client cache management in a distributed object database, 1995</name><name>K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976</name><name>Michael Jay Franklin, Caching and memory management in client-server database systems, University of Wisconsin at Madison, Madison, WI, 1993</name><name>M. Franklin and M. Carey. Client-Server Caching Revisited. In Proc. Int'l Workshop on Distributed Object Management, Edmonton, Canada, August 1992.</name><name>S. Ghemawat. Main-Memory Log: A Simple Solution to the Disk Bottleneck. PhD thesis, Massachusetts Institute of Technology, Forthcoming.</name><name>D. K. Gifford. Information Storage in a Decentralized Computer System. Tech. Report CSL-81-8, Xerox Parc, 1983.</name><name>Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978</name><name>R. E. Gruber, OPTIMISTIC CONCURRENCY CONTROL FOR NESTED DISTRIBUTED TRANSACTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1989</name><name>R. E. Gruber. Temperature-Based Concurrency Control. in Third IWO00S, pages 230-232, Asheville, December 1993.</name><name>R. E. Gruber. Temperature-Based Concurrency Control. PhD thesis, Massachusetts Institute of Technology, Forthcoming.</name><name>Theo H&amp;#228;rder, Observations on optimistic concurrency control schemes, Information Systems, v.9 n.2, p.111-120, 1984</name><name>H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981</name><name>Ming-Yee Lai , W. Kevin Wilkinson, Distributed Transaction Management in Jasmin, Proceedings of the 10th International Conference on Very Large Data Bases, p.466-470, August 27-31, 1984</name><name>Barbara Liskov, Practical uses of synchronized clocks in distributed systems, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.1-9, August 19-21, 1991, Montreal, Quebec, Canada</name><name>B. Liskov. Preliminary Design of the Thor Object-Oriented Database System. Programming Methodology Memo 74, MIT Lab. for Computer Science, March 1992.</name><name>B. Liskov, R. Gmber, E Johnson, and L. Shrira. A Highly- Available Object Repository for use in a Heterogeneous Distributed System. In Proc. of the 4th lnt'l Workshop on Persistent Object Systems, pages 255-266, September 1990.</name><name>Umesh Maheshwari , Barbara H. Liskov, Fault-tolerant distributed garbage collection in a client-server object-oriented database, Proceedings of the third international conference on on Parallel and distributed information systems, p.239-248, October 1994, Autin, Texas, United States</name><name>D. L. Mills. Network Time Protocol: Specification and implementation. DARPA-Intemet Report RFC 1059, DARPA, July 1988.</name><name>E. Rahm and A. Thomasian. A New Distributed Optimistic Concurrency Control Method and a Comparison of its Performance with Two-Phase Locking. In Proceedings of Tenth ICDCS, 1990.</name><name>J. W. Stamos. A Low-Cost Atomic Commit Protocol. Tech. Report RJ7185, IBM Almaden, CA, December 1989.</name></citation><abstract>This paper describes an efficient optimistic concurrency control scheme for use in distributed database systems in which objects are cached and manipulated at client machines while persistent storage and transactional support are provided by servers. The scheme provides both serializability and external consistency for committed transactions; it uses loosely synchronized clocks to achieve global serialization. It stores only a single version of each object, and avoids maintaining any concurrency control information on a per-object basis; instead, it tracks recent invalidations on a per-client basis, an approach that has low in-memory space overhead and no per-object disk overhead. In addition to its low space overheads, the scheme also performs well. The paper presents a simulation study that compares the scheme to adaptive callback locking, the best concurrency control scheme for client-server object-oriented database systems studied to date. The study shows that our scheme outperforms adaptive callback locking for low to moderate contention workloads, and scales better with the number of clients. For high contention workloads, optimism can result in a high abort rate; the scheme presented here is a first step toward a hybrid scheme that we expect to perform well across the full range of workloads.</abstract></paper><paper><title>The LyriC language: querying constraint objects</title><author><AuthorName>Alexander Brodsky</AuthorName><institute><InstituteName>George Mason University</InstituteName><country></country></institute></author><author><AuthorName>Yoram Kornatzky</AuthorName><institute><InstituteName>University of Toronto</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Alexander Brodsky , Joxan Jaffar , Michael J. Maher, Toward Practical Constraint Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.567-580, August 24-27, 1993</name><name>M. Benjamin, T. Viana, K. Corbett, A. Silva, Satisfying Multiple Rated- Constraints in a Knowledge Based Decision Aid, Proc. IEEE Conf. on Artificial Intelligence Applications, Orlando, 1993.</name><name>M. Dincbas, P. Van Hentenryck, H. Simnis, A. Aggoun, T. Graf, F. Berthier, The Constraint Logic Programming Language CHIP, Proc. Fifth Generation Computer Systems, Tokyo, Japan, 1988.</name><name>W. Chen, M. Kifer, and D.S. Warren, HiLog: A First Order Semantics for Higher-Order Logic Programming Constructs, In 2-nd lntl. Workshop on Database Programming Languages, Morgan-Kaufmann, June 1989.</name><name>H.B. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972.</name><name>R. H. G&amp;#252;ting, Gral: an extensible relational database system for geometric applications, Proceedings of the 15th international conference on Very large data bases, p.33-44, July 1989, Amsterdam, The Netherlands</name><name>Laura M. Haas , William F. Cody, Exploiting Extensible DBMS in Integrated Geographic Information Systems, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.423-450, August 28-30, 1991</name><name>M. R. Hansen , B. S. Hansen , P. Lucas , P. van Emde Boas, Integrating relational databases and constraint languages, Computer Languages, v.14 n.2, p.63-82, Aug. 1989</name><name>J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany</name><name>J. Jaffar, M.J. Maher, P.J. Stuckey R.H.C. Yap, Output in CLP(T~.), Proc. Int. Conf. on F~flh Generatzon Computer Systems 1992, Tokyo, Japan, Vol. 2, 1992, 987-995.</name><name>Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995</name><name>Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States</name><name>Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995</name><name>D. Kemp, P. Stuckey, Bottom Up Constraint Logic Programming Without Constraint Solving, Technical Report, Dept. of Computer Science, University of Melbourne, 1992.</name><name>J.-L. Lassez, K. McAloon, A Canonical Form for Generalized Linear Constraints, J. Symbolic Computation, to appear.</name><name>Alon Levy , Yehoshua Sagiv, Constraints and redundancy in datalog, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.67-80, June 02-05, 1992, San Diego, California, United States</name><name>Inderpal Singh Mumick , Sheldon J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic conditions, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.314-330, April 02-04, 1990, Nashville, Tennessee, United States</name><name>J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988</name><name>Alain Colmerauer, An introduction to Prolog III, Communications of the ACM, v.33 n.7, p.69-90, July 1990</name><name>Alexandeer Schrijver, Theory of linear and integer programming, John Wiley &amp; Sons, Inc., New York, NY, 1986</name><name>D. Srivastava, Subsumption and Indexing in Constraint Query Languages with Linear Arithmetic Constraints, Annals of Mathematics and Artificial Intelligence, to appear.</name><name>Divesh Srivastava , Raghu Ramakrishnan, Pushing constraint selections, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.301-315, June 02-05, 1992, San Diego, California, United States</name><name>Divesh Srivastava , Raghu Ramakrishnan , Peter Z. Revesz, Constraint Objects, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.218-228, May 02-04, 1994</name></citation><abstract>We propose a novel data model and its language for querying object-oriented databases where objects may hold spatial, temporal or constraint data, conceptually represented by linear equality and inequality constraints. The proposed LyriC language is designed to provide a uniform and flexible framework for diverse application realms such as (1) constraint-based design in two-, three-, or higher-dimensional space, (2) large-scale optimization and analysis, based mostly on linear programming techniques, and (3) spatial and geographic databases. LyriC extends flat constraint query languages, especially those for linear constraint databases, to structurally complex objects. The extension is based on the object-oriented paradigm, where constraints are treated as first-class objects that are organized in classes. The query language is an extension of the language XSQL, and is built around the idea of extended path expressions. Path expressions in a query traverse nested structures in one sweep. Constraints are used in a query to filter stored constraints and to create new constraint objects.</abstract></paper><paper><title>Towards an effective calculus for object query languages</title><author><AuthorName>Leonidas Fegaras</AuthorName><institute><InstituteName>Department of Computer Science and Engineering, Oregon Graduate Institute of Science &amp; Technology, 20000 N.W. Walker Road P.O. Box 91000, Portland, OR</InstituteName><country></country></institute></author><author><AuthorName>David Maier</AuthorName><institute><InstituteName>Department of Computer Science and Engineering, Oregon Graduate Institute of Science &amp; Technology, 20000 N.W. Walker Road P.O. Box 91000, Portland, OR</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>S. Abiteboul and C. Beeri. On the Power of Languages for the Manipulation of Complex Objects. In International Workshop on Theory and Applicatzons of Nested Relations and Complex Objects, Darmstadt, 1987.</name><name>David Beech, Collections of Objects in SQL3, Proceedings of the 19th International Conference on Very Large Data Bases, p.244-255, August 24-27, 1993</name><name>Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Proceedings of the third international conference on database theory on Database theory, p.72-88, November 1990, Paris, France</name><name>Val Breazu-Tannen , Peter Buneman , Shamim Naqvi, Structural recursion as a query language, Proceedings of the third international workshop on Database programming languages : bulk types &amp; persistent data: bulk types &amp; persistent data, p.9-19, April 1992, Nafplion, Greece</name><name>Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992</name><name>Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain</name><name>P. Buneman. The Fast Fourier Transform as a Database Query. Technical report, University of Pennsylvania, March 1993. MS-CIS-93-37/L&amp;C 60.</name><name>Peter Buneman , Leonid Libkin , Dan Suciu , Val Tannen , Limsoon Wong, Comprehension syntax, ACM SIGMOD Record, v.23 n.1, p.87-96, March 1994</name><name>R. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1994.</name><name>Daniel K. C. Chan , Philip W. Trinder, Object Comprehensions: A Query Notation for Object-Oriented Databases, Proceedings of the 12th British National Conference on Databases: Directions in Databases, p.55-72, July 06-08, 1994</name><name>Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States</name><name>P. Dadam , K. Kuespert , F. Andersen , H. Blanken , R. Erbe, A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.356-367, May 28-30, 1986, Washington, D.C., United States</name><name>S. Danforth , P. Valduriez, A FAD for Data Intensive Applications, IEEE Transactions on Knowledge and Data Engineering, v.4 n.1, p.34-51, February 1992</name><name>Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California</name><name>O. Deux et al., The Story of O2, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.91-108, March 1990</name><name>L. Fegaras. A Uniform Calculus for Collection Types. Oregon Graduate Institute Technical Report 94-030. Available by anonymous ftp from cse. ogi. edu:/pub/crml/tapos, ps. Z.</name><name>L. Fegaras and D. Maier. An Algebraic Framework for Physical OODB Design. Available by anonymous ftp from cse. ogi. edu:/pub/crml/oodb-design.ps. Z.</name><name>Shashi K. Gadia, A homogeneous relational model and query languages for temporal databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.418-448, Dec. 1988</name><name>Neil Immerman , Sushant Patnaik , David Stemple, The expressiveness of a family of finite set languages, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-52, May 29-31, 1991, Denver, Colorado, United States</name><name>Alfons Kemper , Guido Moerkotte, Advanced query processing in object bases using access support relations, Proceedings of the sixteenth international conference on Very large databases, p.290-301, September 1990, Brisbane, Australia</name><name>Theodore W. Leung , Gail Mitchell , Bharathi Subramanian , Bennet Vance , Scott L. Vandenberg , Stanley B. Zdonik, The AQUA Data Model and Algebra, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.157-175, August 30-September 01, 1993</name><name>David Maier , Bennet Vance, A call to order, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-16, May 25-28, 1993, Washington, D.C., United States</name><name>Atushi Ohori, Representing object identity in a pure functional language, Proceedings of the third international conference on database theory on Database theory, p.41-55, November 1990, Paris, France</name><name>G. &amp;#214;zsoyo&amp;#287;lu , Z. M. &amp;#214;zsoyo&amp;#287;lu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987</name><name>P Pistor , R Traunmueller, A database language for sets, lists and tables, Information Systems, v.11 n.4, p.323-336, Oct. 1986</name><name>Phil Trinder, Comprehensions, a query notation for DBPLs, Proceedings of the third international workshop on Database programming languages : bulk types &amp; persistent data: bulk types &amp; persistent data, p.55-68, April 1992, Nafplion, Greece</name><name>P. Trinder and P. Wadler. improving List Comprehension Database Queries. In in Proceedings of TEN- CON'89, Bombay, india, pp 186-192, November 1989.</name><name>Scott L. Vandenberg , David J. DeWitt, Algebraic support for complex objects with arrays, identity, and inheritance, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.158-167, May 29-31, 1991, Denver, Colorado, United States</name><name>Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France</name><name>Limsoon Wong, Normal forms and conservative properties for query languages over collection types, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-36, May 25-28, 1993, Washington, D.C., United States</name></citation><abstract>We define a standard of effectiveness for a database calculus relative to a query language. Effectiveness judges suitability to serve as a processing framework for the query language, and comprises aspects of coverage, manipulability and efficient evaluation. We present the monoid calculus, and argue its effectiveness for object-oriented query languages, exemplified by OQL of ODMG-93. The monoid calculus readily captures such features as multiple collection types, aggregations, arbitrary composition of type constructors and nested query expressions. We also show how to extend the monoid calculus to deal with vectors and arrays in more expressive ways than current query languages do, and illustrate how it can handle identity and updates.</abstract></paper><paper><title>OFL: a functional execution model for object query languages</title><author><AuthorName>Georges Gardarin</AuthorName><institute><InstituteName>PRISM Laboratory, University of Versailles/Saint-Quentin, 45, Avenue des Etats-Unis, 78035 VERSAILLES Cedex, France and Projet Rodin, INRIA, Rocquencourt, France</InstituteName><country></country></institute></author><author><AuthorName>Fernando Machuca</AuthorName><institute><InstituteName>PRISM Laboratory, University of Versailles/Saint-Quentin, 45, Avenue des Etats-Unis, 78035 VERSAILLES Cedex, France and EDS International (France) SA, Guillaumet, 060 Avenue du pr&amp;#233;sident Wilson, 92800 Puteaux</InstituteName><country></country></institute></author><author><AuthorName>Philippe Pucheral</AuthorName><institute><InstituteName>PRISM Laboratory, University of Versailles/Saint-Quentin, 45, Avenue des Etats-Unis, 78035 VERSAILLES Cedex, France</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986</name><name>Amman A., Hanrahan M., and Knshnamurthy R, "Design of a Memory Resident DBMS", IEEE COMPCON, San Francisco, California, February 1985.</name><name>Bernd Amann , Michel Scholl, Gram: a graph data model and query languages, Proceedings of the ACM conference on Hypertext, p.201-211, November 30-December 04, 1992, Milan, Italy</name><name>Bakus J., "Function Level Program as Mathematical Objects," ACM Transactions on Database Systems, 6(1), October 1981.</name><name>Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States</name><name>Fran&amp;#231;ois Bancilhon , Ted Briggs , Setrag Khoshafian , Patrick Valduriez, FAD, a Powerful and Simple Database Language, Proceedings of the 13th International Conference on Very Large Data Bases, p.97-105, September 01-04, 1987</name><name>D. S. Batory , T. Y. Leung , T. E. Wise, Implementation concepts for an extensible data model and data language, ACM Transactions on Database Systems (TODS), v.13 n.3, p.231-262, Sept. 1988</name><name>Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Proceedings of the third international conference on database theory on Database theory, p.72-88, November 1990, Paris, France</name><name>Dina Bitton , Carolyn Turbyfill, Performance Evaluation of Main Memory Database Systems, Cornell University, Ithaca, NY, 1986</name><name>Jos&amp;#233; A. Blakeley , William J. McKenna , Goetz Graefe, Experiences building the open OODB query optimizer, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.287-296, May 25-28, 1993, Washington, D.C., United States</name><name>Peter Buneman , Robert E. Frankel, FQL: a functional query language, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts</name><name>Michael J. Carey , David J. DeWitt, A data model and query language for EXODUS, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.413-423, June 01-03, 1988, Chicago, Illinois, United States</name><name>Cattell R.G.G. Ed., "Object Databases: The ODMG-93 Standard", Book, Morgan &amp; Kaufman, 1993.</name><name>Sophie Cluet , Claude Delobel, A general framework for the optimization of object-oriented queries, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.383-392, June 02-05, 1992, San Diego, California, United States</name><name>Cruz, I.F., "Domains of Application for the G+ Query Language", Office and Database Systems Research, ed. F.H. Lochovsky, CSRI, Univ. of Toronto, 1988.</name><name>Shaul Dar , Rakesh Agrawal , H. V. Jagadish, Optimization of Generalized Transitive Closure Queries, Proceedings of the Seventh International Conference on Data Engineering, p.345-354, April 08-12, 1991</name><name>Delobel, C., Lecluse C., Richard P., "Bases de Donn6es : des Systtmes Relationels aux Systtmes h Objects," Book, InterEditions, Paris.</name><name>Field, A., Harrison P., "Functional Programming," chapter 11 and 12, Book, Addison Wesley 1988.</name><name>B&amp;#233;atrice Finance , Georges Gardarin, A rule-based query optimizer with multiple search strategies, Data &amp; Knowledge Engineering, v.13 n.1, p.1-29, Aug. 1994</name><name>J&amp;#252;rgen Frohn , Georg Lausen , Heinz Uphoff, Access to Objects by Path Expressions and Rules, Proceedings of the 20th International Conference on Very Large Data Bases, p.273-284, September 12-15, 1994</name><name>Georges Gardarin , Patrick Valduriez, ESQL2: An Object-Oriented SQL with F-Logic Semantics, Proceedings of the Eighth International Conference on Data Engineering, p.320-327, February 03-07, 1992</name><name>Georges Gardarin , Rosana S. G. Lanzelotte, Optimizing Object-Oriented Datbase Queries using Cost-Controlled Rewriting, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.534-549, March 23-27, 1992</name><name>Gardarin G,, Machuca F., Pucheral P,, "A Functional Traversal Graph Optimization Strategy for OQL-hke Query Optimizers", Technical Report, PRISM Laboratory, (submitted for rpublication), 1994.</name><name>B. Paul Jenq , Darrell Woelk , Won Kim , Wan-Lik Lee, Query processing in distributed ORION, Proceedings of the international conference on extending database technology on Advances in database technology, p.169-187, March 1990, Venice, Italy</name><name>Alfons Kemper , Guido Moerkotte, Advanced query processing in object bases using access support relations, Proceedings of the sixteenth international conference on Very large databases, p.290-301, September 1990, Brisbane, Australia</name><name>Christoph Kilger , Guido Moerkotte, Indexing Multiple Sets, Proceedings of the 20th International Conference on Very Large Data Bases, p.180-191, September 12-15, 1994</name><name>Won Kim , Kyung-Chang Kim , Alfred Dale, Indexing techniques for object-oriented databases, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989</name><name>Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States</name><name>Lanzelotte R., Cheiney J.P., "Vers une nouvelle g~n~ration d'optimiseurs pour les SGBD orient, s objet," Tecnique et Science Informatique~, Volume 12(4), 1993.</name><name>Tobin J. Lehman , Michael J. Carey, Query processing in main memory database management systems, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.239-250, May 28-30, 1986, Washington, D.C., United States</name><name>Machuca F., Gardarin G., Pucherat P., "A Functional Execution Model for Complex Object Algebras," Technical Report, PRISM Laboratory, University of Versailles Saint-Quentin, Versailles, France, February, 1994.</name><name>Michie D., "Memo Functions and Machine Learning," Nature, (218), 1968. pp. 19-22,</name><name>Jack Orenstein , Sam Haradhvala , Benson Margulies , Don Sakahara, Query processing in the ObjectStore database system, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.403-412, June 02-05, 1992, San Diego, California, United States</name><name>Philippe Pucheral , Jean-Marc Th&amp;#233;venin, Pipelined Query Processing in the DBGraph Storage Model, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.516-533, March 23-27, 1992</name><name>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</name><name>Shaw G., Zdonik S., "A Query Algebra for Object- Oriented Databases," in IEEE, 1990.</name><name>David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981</name><name>Eugene J. Shekita , Michael J. Carey, A performance evaluation of pointer-based joins, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.300-311, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>B. Sreenath , S. Seshadri, The hcC-tree: An Efficient Index Structure for Object Oriented Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.203-213, September 12-15, 1994</name><name>Hennie J. Steenhagen , Peter M. G. Apers , Henk M. Blanken , Rolf A. de By, From Nested-Loop to Join Queries in OODB, Proceedings of the 20th International Conference on Very Large Data Bases, p.618-629, September 12-15, 1994</name><name>Straube D., Ozsu T, "Queries and Query Processing m Object-Oriented Database Systems,"Technical Report, Departement of computing science, university of Alberta, Edmonton, Alberta, Canada, 1990.</name><name>Patrick Valduriez , Setrag Khoshafian , George P. Copeland, Implementation Techniques of Complex Objects, Proceedings of the 12th International Conference on Very Large Data Bases, p.101-110, August 25-28, 1986</name><name>Valdunez P., Lanzelotte R,, Ziane M, and Chelney J.P., "Optimization of non Recursive Queries in OODB," In Proc. DOOD, Munich, Germany, 1991.</name></citation><abstract>We present a functional paradigm for querying efficiently abstract collections of complex objects. Abstract collections are used to model class extents, multivalued attributes as well as indexes or hashing tables. Our paradigm includes a functional language called OFL (Object Functional Language) and a supporting execution model based on graph traversals. OFL is able to support any complex object algebra with recursion as macros. It is an appropriate target language for OQL-like query compilers. The execution model provides various strategies including set-oriented and pipelined traversals. OFL has been implemented on top of an object manager. Measures of a typical query extracted from a geographical benchmark show the value of hybrid strategies integrating pipelined and set-oriented evaluations. They also show the potential of function result memorization, a typical optimization approach known as "Memoization" 2 in functional languages.</abstract></paper><paper><title>Nearest neighbor queries</title><author><AuthorName>Nick Roussopoulos</AuthorName><institute><InstituteName>Department of Computer Science, University of Maryland, College Park, MD</InstituteName><country></country></institute></author><author><AuthorName>Stephen Kelley</AuthorName><institute><InstituteName>Department of Computer Science, University of Maryland, College Park, MD</InstituteName><country></country></institute></author><author><AuthorName>Fr&amp;#233;d&amp;#233;ric Vincent</AuthorName><institute><InstituteName>Department of Computer Science, University of Maryland, College Park, MD</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States</name><name>Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977</name><name>Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman &amp; Co., New York, NY, 1978</name><name>H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994</name><name>Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States</name><name>Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987</name><name>Sproull, R.F., "Refinements to Nearest- Neighbor Searching in k-Dimensional Trees," A1- gorithmica, 6, 1987, pp. 579-589.</name></citation><abstract>A frequently encountered type of query in Geographic Information Systems is to find the k nearest neighbor objects to a given point in space. Processing such queries requires substantially different search algorithms than those for location or range queries. In this paper we present an efficient branch-and-bound R-tree traversal algorithm to find the nearest neighbor object to a point, and then generalize it to finding the k nearest neighbors. We also discuss metrics for an optimistic and a pessimistic search ordering strategy as well as for pruning. Finally, we present the results of several experiments obtained using the implementation of our algorithm and examine the behavior of the metrics and the scalability of the algorithm.</abstract></paper><paper><title>A general solution of the n-dimensional B-tree problem</title><author><AuthorName>Michael Freeston</AuthorName><institute><InstituteName>European Computer-Industry Research Centre (ECRC), Arabellastr. 17, D-81925 Munich, Germany</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975</name><name>J.L.Bentley. Multidimensional Binary Search Trees in Database Applications. IEEE Trans. on Soft. Eng., Vol. SE-5, No. 4, July 1979.</name><name>R.Bayer and E.McCreight. Organisation and maintenance of large ordered indexes. Acta lnformatica Vol. 1, No. 3, 1972.</name><name>Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977</name><name>Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979</name><name>Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States</name><name>M. W. Forreston, Advances in the design of the BANG file, 3rd International Conference, FODO 1989 on Foundations of Data Organization and Algorithms, p.322-338, July 1989, Paris, France</name><name>M. W. Freeston, A well-behaved file structure for the storage of spatial objects, Proceedings of the first symposium on Design and implementation of large spatial databases, p.287-300, February 1990, Santa Barbara, California, United States</name><name>M.Freeston. A general solution of the ndimensional B-tree problem. ECRC Technical Report No. ECRC-94-40.</name><name>Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands</name><name>H. -P. Kriegel , M. Schiwietz , R. Schneider , B. Seeger, Performance comparison of point and spatial access methods, Proceedings of the first symposium on Design and implementation of large spatial databases, p.89-114, February 1990, Santa Barbara, California, United States</name><name>David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990</name><name>Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States</name><name>John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan</name><name>Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>Bernhard Seeger , Hans-Peter Kriegel, The buddy tree: an efficient and robust access method for spatial data base, Proceedings of the sixteenth international conference on Very large databases, p.590-601, September 1990, Brisbane, Australia</name><name>Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987</name></citation><abstract>We present a generic solution to a problem which lies at the heart of the unpredictable worst-case performance characteristics of a wide class of multi-dimensional index designs: those which employ a recursive partitioning of the data space. We then show how this solution can produce modified designs with fully predictable and controllable worst-case characteristics. In particular, we show how the recursive partitioning of an n-dimensional dataspace can be represented in such a way that the characteristics of the one-dimensional B-tree are preserved in n dimensions, as far as is topologically possible i.e. a representation guaranteeing logarithmic access and update time, while also guaranteeing a one-third minimum occupancy of both data and index nodes.</abstract></paper><paper><title>Topological relations in the world of minimum bounding rectangles: a study with R-trees</title><author><AuthorName>Dimitris Papadias</AuthorName><institute><InstituteName>Department of Computer Science and Engineering, University of California, San Diego, CA</InstituteName><country></country></institute></author><author><AuthorName>Timos Sellis</AuthorName><institute><InstituteName>Department of Electrical and Computer Engineering, National Technical University of Athens, Greece 15773</InstituteName><country></country></institute></author><author><AuthorName>Yannis Theodoridis</AuthorName><institute><InstituteName>Department of Electrical and Computer Engineering, National Technical University of Athens, Greece 15773</InstituteName><country></country></institute></author><author><AuthorName>Max J. Egenhofer</AuthorName><institute><InstituteName>National Center for Geographic Information and Analysis, University of Maine, Orono, ME</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983</name><name>Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider, Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.40-49, April 19-23, 1993</name><name>Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>Clementini, E., Sharma, J., Egenhofer, M. (1995) Modeling Topological Spatial Relations: Strategies for Query Processing. To appear in the International Journal of Computer and Graphics.</name><name>Max J. Egenhofer, Reasoning about Binary Topological Relations, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.143-160, August 28-30, 1991</name><name>Egenhofer, M. (1993) Definition of Line-Line Relations for Geographic Databases. Data Engineering, Vol 16(6), pp. 40-45.</name><name>M. J. Egenhofer, Spatial SQL: A Query and Presentation Language, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.86-95, February 1994</name><name>Max J. Egenhofer , Khaled K. Al-Taha, Reasoning about Gradual Changes of Topological Relationships, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.196-219, September 21-23, 1992</name><name>Frank, A. U. (1995) Qualitative Spatial Reasoning: Cardinal Directions as an Example. To appear in the International Journal of Geographic Information Systems.</name><name>Christian Freksa, Temporal reasoning based on semi-intervals, Artificial Intelligence, v.54 n.1-2, p.199-227, March 1992</name><name>Glasgow, J.I., Papadias, D. (1992) Computational Imagery. Cognitive Science, Vol 16, pp. 355-394.</name><name>Diane Greene, An Implementation and Performance Analysis of Spatial Data Access Methods, Proceedings of the Fifth International Conference on Data Engineering, p.606-615, February 06-10, 1989</name><name>Grigni M., Papadias, D., Papadimitriou, C. (1995) Topological Inference. Submitted.</name><name>Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts</name><name>Thanasis Hadzilacos , Nectaria Tryfona, A Model for Expressing topological Integrity Constraints in Geographic Databases, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.252-268, September 21-23, 1992</name><name>Keighan, E. (1993) Managing Spatial Data within the Framework of the Relational Model. Technical Report, Oracle Corporation, Canada.</name><name>Mark, D., Egenhofer, M. (1994) Calibrating the Meaning of Spatial Predicates from Natural Language: Line Region Relations. In the Proceedings of the 6th International Symposium on Spatial Data Handling. Taylor Francis.</name><name>Mark, D., Xia, F. (1994) Determining Spatial Relations between Lines and Regions in Arc/Info using the 9- Intersection Model. In ESRI User Conference.</name><name>MGE (1993) MGE Analyst Reference Manual. Intergraph Corporation.</name><name>Dimitris Papadias , Timos Sellis, Qualitative representation of spatial knowledge in two-dimensional space, The VLDB Journal &amp;mdash; The International Journal on Very Large Data Bases, v.3 n.4, October 1994</name><name>Papadias, D., Theodoridis, Y. (1994) Spatial Relations, Minimum Bounding Rectangles and Spatial Data Structures. Technical Report, KDBSLAB-TR-94-06, National Technical University of Athens, Greece.</name><name>Dimitris Papadias , Yannis Theodoridis , Timos K. Sellis, The Retrieval of Direction Relations using R-trees, Proceedings of the 5th International Conference on Database and Expert Systems Applications, p.173-182, September 07-09, 1994</name><name>Papadias, D., Sellis, T. (1995) A Pictorial Query-By-Example Language. To appear in the Journal of Visual Languages and Computing, Special Issue on Visual Query Systems, March 95.</name><name>Randell, D. A., Cui, Z., Cohn., A., (1992) A Spatial Logic Based on Regions and Connection. in the Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann.</name><name>Nick Roussopoulos , Stephen Kelley , Fr&amp;#233;d&amp;#233;ric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States</name><name>Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987</name><name>A. Prasad Sistla , Clement T. Yu , R. Haddad, Reasoning About Spatial Relationships in Picture Retrieval Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.570-581, September 12-15, 1994</name></citation><abstract>Recent developments in spatial relations have led to their use in numerous applications involving spatial databases. This paper is concerned with the retrieval of topological relations in Minimum Bounding Rectangle-based data structures. We study the topological information that Minimum Bounding Rectangles convey about the actual objects they enclose, using the concept of projections. Then we apply the results to R-trees and their variations, R+-trees and R*-trees in order to minimise disk accesses for queries involving topological relations. We also investigate queries that involve complex spatial conditions in the form of disjunctions and conjunctions and we discuss possible extensions.</abstract></paper><paper><title>Adaptive parallel aggregation algorithms</title><author><AuthorName>Ambuj Shatdal</AuthorName><institute><InstituteName>Computer Sciences Department, University of Wisconsin-Madison</InstituteName><country></country></institute></author><author><AuthorName>Jeffrey F. Naughton</AuthorName><institute><InstituteName>Computer Sciences Department, University of Wisconsin-Madison</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983</name><name>Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993</name><name>J. Bunge and M. Fitzpatrick. Estimating the Number of Species: A Review. Journal of the Amemcan Statistical Association, 88(421), March 1993.</name><name>D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990</name><name>R. Epstein. Techniques for Processing of Aggregates in Relational Database Systems. Memo UCB/ERL M79/8, E.R.L., College of Eng., Univ. of Calif., Berkeley, Feb. 1979.</name><name>P. Erd5s and A. R~nyi. On a Classical Problem of Probability Theory. MTA Mat. Kut. Int. KSzl, 6A, 1961. Also in Selected Papers of A. Rfinyi, v. 2, Akademiai Kiado, Budapest.</name><name>Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993</name><name>Oak Ridge National Lab. P VM 3 User's Guide and Reference Manual, May 1993.</name><name>S. Seshadri, Probabilistic methods in query processing, University of Wisconsin at Madison, Madison, WI, 1992</name><name>Stanley Y. W. Su , Krishna P. Mikkilineni, Parallel Algorithms and Their Implementation in MICRONET, Proceedings of the 8th International Conference on Very Large Data Bases, p.310-324, September 08-10, 1982</name><name>TPC. TPC BenchmarkTM D (Decision Support). Working draft 6.5, Transaction Processing Performance Council, Feb. 1994.</name><name>Christopher B. Walton , Alfred G. Dale , Roy M. Jenevein, A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins, Proceedings of the 17th International Conference on Very Large Data Bases, p.537-548, September 03-06, 1991</name></citation><abstract>Aggregation and duplicate removal are common in SQL queries. However, in the parallel query processing literature, aggregate processing has received surprisingly little attention; furthermore, for each of the traditional parallel aggregation algorithms, there is a range of grouping selectivities where the algorithm performs poorly. In this work, we propose new algorithms that dynamically adapt, at query evaluation time, in response to observed grouping selectivities. Performance analysis via analytical modeling and an implementation on a workstation-cluster shows that the proposed algorithms are able to perform well for all grouping selectivities. Finally, we study the effect of data skew and show that for certain data sets the proposed algorithms can even outperform the best of traditional approaches.</abstract></paper><paper><title>Parallel evaluation of multi-join queries</title><author><AuthorName>Annita N. Wilschut</AuthorName><institute><InstituteName>University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands</InstituteName><country></country></institute></author><author><AuthorName>Jan Flokstra</AuthorName><institute><InstituteName>University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands</InstituteName><country></country></institute></author><author><AuthorName>Peter M. G. Apers</AuthorName><institute><InstituteName>University of Twente, P.O. Box 217, 7500 AE Enschede, the Netherlands</InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Management of Data</conference><citation><name>R America, ed., Proc of the PRISMA workshop on parallel database systems, Springer-Verlag, New York- Heidelberg-Berlin, 1991.</name><name>P. M. G. Apers , C. A. van den Berg , J. Flokstra , P. W. P. J. Grefen , M. L. Kersten , A. N. Wilschut, PRISMA/DB: A Parallel, Main Memory Relational DBMS, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.541-554, December 1992</name><name>P. M. G. Apers &amp; A. N. Wilschut, "Understanding large scale parallelism for data management ," in Keynote at the 3rd PDIS Conf, Austin, Texas, USA, September 1994.</name><name>Dina Bitton , David J. DeWitt , Carolyn Turbyfill, Benchmarking Database Systems A Systematic Approach, Proceedings of the 9th International Conference on Very Large Data Bases, p.8-19, October 31-November 02, 1983</name><name>H. Boral , W. Alexander , L. Clay , G. Copeland , S. Danforth , M. Franklin