sigmod_1994_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>Sleepers and workaholics: caching strategies in mobile environments</title><author><AuthorName>Daniel Barbar&amp;#225;</AuthorName><institute><InstituteName>Matsushita Information Technology Laboratory, 2 Research Way, 3rd Floor, Princeton, N.J</InstituteName><country></country></institute></author><author><AuthorName>Tomasz Imieli&amp;#324;ski</AuthorName><institute><InstituteName>Rutgers University, Department of Computer Science, New Brunswick, N.J</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>D. Barbarg and T. Imielifiski. Sleepers and Workaholica: Caching Strategies in Mobile Environments. Technical Report MITL-TR-58-93, MITL, June 1993.</name><name>D. Barbará , R. J. Lipton, A Class of Randomized Strategies for Low-Cost Comparison of File Copies, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.160-170, April 1991</name><name>H. Chernoff. A Meassure of Asymptotic Efficiency for Tests of a Hypotesis Based on the Sum of Observations. Annals of Mathemgtical Statistics, 23:493-509, 1952.</name><name>W.K. Fuchs, K. Wu, and J. Abraham. Low-Cost Comparison and Diagnosis of Large Remotely Located Files. In Proceedings of the Fifth Symposium on Reliability of Distributed Software and Database Syatems, January 1986.</name><name>Tomasz Imielinski , B. R. Badrinath, Querying in Highly Mobile Distributed Environments, Proceedings of the 18th International Conference on Very Large Data Bases, p.41-52, August 23-27, 1992</name><name>T. Imielinski, B.R. Badrinath, and S. Viswanathan. Data Dissemination in Wireless and Mobile Environments. Technical Report 59, WINLAB, Rutgers University, 3une 1993.</name><name>Tomasz Imielinski , S. Viswanathan , B. R. Badrinath, Energy efficient indexing on air, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.25-36, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>T. Madej. An Application of Group Testing to the File Comparison Problem. In Proceedings of the International Conference on Distributed Computing Systems, June 1989.</name><name>S. Rangarajan and D. Fussell. Rectifying Corrupted Files in Distributed File Systems. In Proceedings of the international Conference on Distributed Computing Systems, May 1991.</name><name>R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Desing and Implementation of the Sun Network Filesystem. In Proceedings of the USENIX Summer Conference, pages 119-130, 3une 1985.</name><name>M. Satyanarayanan, 3. H. Howard, D. N. Nichols, R. N Sidebotham, A. Z Spector, and M. J. West. The ITC Distributed File System" Principles and Design. In Proceedings of the l O#h A CM Symposium on Operating Systems Principles, pages 35-50, December 1985.</name></citation><abstract>In the mobile wireless computing environment of the future a large number of users equipped with low powered palm-top machines will query databases over the wireless communication channels. Palmtop based units will often be disconnected for prolonged periods of time due to the battery power saving measures; palmtops will also frequencly relocate between different cells and connect to different data servers at different times. Caching of frequently accessed data items will be an important technique that will reduce contention on the narrow bandwidth wireless channel. However, cache invalidation strategies will be severely affected by the disconnection and mobility of the clients. The server may no longer know which clients are currently residing under its cell and which of them are   currently on. We propose a taxonomy of different cache invalidation strategies and study the impact of client's disconnection times on their performance. We determine that for the units which are often disconnected (sleepers) the best cache invalidation strategy is based on signatures previously used for efficient file comparison. On the other hand, for units which are connected most of the time (workaholics), the best cache invalidation strategy is based on the periodic broadcast of changed data items.</abstract></paper><paper><title>Data replication for mobile computers</title><author><AuthorName>Yixiu Huang</AuthorName><institute><InstituteName>Electrical Engineering and Computer Science Department, University of Illinois, Chicago, Illinois</InstituteName><country></country></institute></author><author><AuthorName>Prasad Sistla</AuthorName><institute><InstituteName>Electrical Engineering and Computer Science Department, University of Illinois, Chicago, Illinois</InstituteName><country></country></institute></author><author><AuthorName>Ouri Wolfson</AuthorName><institute><InstituteName>Electrical Engineering and Computer Science Department, University of Illinois, Chicago, Illinois</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><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>A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States</name><name>Mustaque Ahamad , Mostafa H. Ammar , Shun Yan Cheung, Multidimensional voting, ACM Transactions on Computer Systems (TOCS), v.9 n.4, p.399-431, Nov. 1991</name><name>R. Alonso and S. Ganguly, "Query Optimization for Energy Efficiency in Mobile Enviroments', Proc. of the 1993 Inl'l Workshop on Foundalzons of Models and Languages for Data and Objects, Aigen, Austria</name><name>D. Agrawal , A. El Abbadi, The tree quorum protocol: an efficient approach for managing replicated data, Proceedings of the sixteenth international conference on Very large databases, p.243-254, September 1990, Brisbane, Australia</name><name>J.K. Bennett, J.B. Carter and W. Zwaenepoel, "Adaptive Software Cache Management for Distributed Shared Memory Architectures", Proc. of the 17-th Int'l Syrup. on Comp. Arch., Pages 148- 159, May 1990</name><name>J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles &amp; practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States</name><name>Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.39-50, May 04-06, 1992, Victoria, British Columbia, Canada</name><name>B. R. Badrinath and T. Imielinski, "Replication and Mobility", Proc. of the 2nd Workshop on the Management of Rephcated Data (WMRD-II), pp. 9-12, Monterey, CA.</name><name>Shun Yan Cheung , Mostafa H. Ammar , Mustaque Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, Proceedings of the Sixth International Conference on Data Engineering, p.438-445, February 05-09, 1990</name><name>Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States</name><name>Michael J. Carey , Miron Livny, Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication, Proceedings of the 14th International Conference on Very Large Data Bases, p.13-25, August 29-September 01, 1988</name><name>Lawrence W. Dowdy , Derrell V. Foster, Comparative Models of the File Assignment Problem, ACM Computing Surveys (CSUR), v.14 n.2, p.287-313, June 1982</name><name>S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.373-382, May 30-June 02, 1988, Honolulu, Hawaii, United States</name><name>S. J. Eggers , R. H. Katz, Evaluating the performance of four snooping cache coherency protocols, Proceedings of the 16th annual international symposium on Computer architecture, p.2-15, April 1989, Jerusalem, Israel</name><name>Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983</name><name>Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991</name><name>S. Ganguly and 1%. Alonso, "Query Optimization in Mobile Enviroments", Technical Report, December 1993</name><name>David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States</name><name>Yixiu Huang , Ouri Wolfson, A Competitive Dynamic Data Replication Algorithm, Proceedings of the Ninth International Conference on Data Engineering, p.310-317, April 19-23, 1993</name><name>Yixiu ttuang, Ouri Wolfson, "Dynamic Allocation in Distributed System and Mobile Computers", IEEE Proc. of l O-th Int'l Conf. on Data Engzneer- ,ng '94, pages 20-29, Houston, Texas.</name><name>Tomasz Imielinski , B. R. Badrinath, Querying in Highly Mobile Distributed Environments, Proceedings of the 18th International Conference on Very Large Data Bases, p.41-52, August 23-27, 1992</name><name>Kai Li, Shared virtual memory on loosely coupled multiprocessors, 1986</name><name>Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989</name><name>J. Lee and U. Ramachandram, "Synchronization with Multiprocessor Caches", Proc. of the 17-th Int'l Syrup. on Comp. Architecture, Pages 27-37, May 1990</name><name>A.R'. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator, "Competitive Snoopy Caching", Algorithmica (1988) 3:79-119</name><name>James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992</name><name>D.3. Makaroff and D.L. Eager, "Disk Cache Performance for Distributed Systems" Proc. of the 10- th Int'l Conf. on Dist. Computing Systems, Pages 212-219, May 1990</name><name>Mark Manasse , Lyle McGeoch , Daniel Sleator, Competitive algorithms for on-line problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.322-333, May 02-04, 1988, Chicago, Illinois, United States</name><name>Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990</name><name>Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979</name><name>Ouri Wolfson , Sushil Jajodia, Distributed algorithms for dynamic replication of data, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-163, June 02-05, 1992, San Diego, California, United States</name><name>Ouri Wolfson and Sushil J ajodia, "An Algorithm for Dynamic Data Distribution", Proc. of the 2nd Workshop on Management of Replicated Data (WMRD-II), 1992, pp. 62-65</name><name>Ouri Wolfson , Amir Milo, The multicast policy and its relationship to replicated data placement, ACM Transactions on Database Systems (TODS), v.16 n.1, p.181-205, March 1991</name><name>Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States</name></citation><abstract>Users of mobile computers will soon have online access to a large number of databases via wireless networks. Because of limited bandwidth, wireless communication is more expensive than wire communication. In this paper we present and analyze various static and dynamic data allocation methods. The objective is to optimize the communication cost between a mobile computer and the stationary computer that stores the online database. Analysis is performed in two cost models. One is connection (or time) based, as in cellular telephones, where the user is charged per minute of connection. The other is message based, as in packet radio networks, where the user is charged per message. Our analysis addresses both, the average case and the worst case for determining the best allocation method.</abstract></paper><paper><title>Energy efficient indexing on air</title><author><AuthorName>Tomasz Imielinski</AuthorName><institute><InstituteName>Department of Computer Science, Rutgers University, New Brunswick, NJ</InstituteName><country></country></institute></author><author><AuthorName>S. Viswanathan</AuthorName><institute><InstituteName>Department of Computer Science, Rutgers University, New Brunswick, NJ</InstituteName><country></country></institute></author><author><AuthorName>B. R. Badrinath</AuthorName><institute><InstituteName>Department of Computer Science, Rutgers University, New Brunswick, NJ</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>Rafael Alonso and Hank Korth, "Database issues in nomadic computing," MITL Technical Report, December 1992.</name><name>T. F. Bowen , G. Gopal , G. Herman , T. Hickey , K. C. Lee , W. H. Mansfield , J. Raitz , A. Weinrib, The Datacycle architecture, Communications of the ACM, v.35 n.12, p.71-81, Dec. 1992</name><name>David Cheriton, "Dissemination- Oriented Communication Systems," Stanford University, Tech. Rept. 1992.</name><name>David Gifford et. al., "The application of digital broadcast communication to large scale information systems," IEEE Journal on selected areas in communications, Vol 3, No. 3, May 1985, pp.457-467.</name><name>David a. Goodman, "Trends in Cellular and Cordless Communications," IEEE Communications Magazine, June 1991.</name><name>Gary Herman , K. C. Lee , Abel Weinrib, The datacycle architecture for very high throughput database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.97-103, May 27-29, 1987, San Francisco, California, United States</name><name>Tomasz Imielinski , B. R. Badrinath, Mobile wireless computing: challenges in data management, Communications of the ACM, v.37 n.10, p.18-28, Oct. 1994</name><name>T. Imieli&amp;#324;ski , S. Viswanathan , B. R. Badrinath, Power efficient filtering of data on air, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.245-258, May 1994, Cambridge, United Kingdom</name><name>T. Imielinski, S. Viswanathan and B. R. Badrinath, "Data on Air : Organization and Access," Submitted for publication.</name><name>Bob Ryan, Communications get personal, BYTE, v.18 n.2, p.169-176, Feb. 1993</name><name>Samuel Sheng, Ananth Chandrasekaran, and R. W. Broderson, "A portable multimedia terminal for personal communications," IEEE Communications Magazine, December 1992, pp. 64-75.</name><name>Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States</name></citation><abstract>We consider wireless broadcasting of data as a way of disseminating information to a massive number of users. Organizing and accessing information on wireless communication channels is different from the problem of organizing and accessing data on the disk. We describe two methods, (1,m) Indexing and Distributed Indexing, for organizing and accessing broadcast data. We demonstrate that the proposed algorithms lead to significant improvement of battery life, while retaining a low access time.</abstract></paper><paper><title>SIGMOD challenges paper: database issues in telecommunications network management</title><author><AuthorName>Ilsoo Ahn</AuthorName><institute><InstituteName>AT&amp;T Bell Laboratories, Columbus, Ohio</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>I. Ahn: SQL+T : a Temporal Query Language, Proceedings of the International Workshop on an Infrastructure for Temporal Databases, Jun. 1993.</name><name>American National Standard for Information Systems: Database Language - SQL, ANSI X3.135-1986, American National Institute, Inc., 1986.</name><name>American National Standard for Information Systems: Database Language - SQL with Integri# Enhancement, ANSI X3.135-1989, American National Institute, Inc., 1989.</name><name>CCITI' Recommendation M.3010: Principles for a Telecommunications Management Network, 1992.</name><name>CCITT Recommendation X.722, ISO/IEC 10165-4: Information Technology - Open #,stems lnterconnection - Structure of Management Information: Guidelines for the Definition of Managed Objects, 1992.</name><name>International Standards Organization: Information Processing Systems - Open Systems interconnection - Basic Reference Model, 1984.</name><name>S. Klever: The OSI Management Architecture: An Overview, IEEE Network, Mar. 1988.</name><name>S. Klever: System Management Information Modeling, IEEE Communications Magazine, May 1993.</name><name>J. Melton (editor): ISO-ANSI (Working Draft) Database Language SQL3, X3H2-93-091/YOK- 003, Feb. 1993.</name><name>OSI Network Management Forum: Object Specification Framework, Sep. 1989.</name><name>Roderick G. Cattell , Tom Atwood, Object Database Standard: ODMG-93, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993</name><name>OMNIPoint: Discovering OMNIPoint, Simon &amp; Schuster, 1993.</name><name>K. Ramamritham: Real-Time Databases, International Journal of Distributed and Parallel Databases, 1992.</name><name>Richard Snodgrass , Ilsoo Ahn, Temporal databases, Computer, v.19 n.9, p.35-41, Sept. 1986</name><name>Richard Snodgrass, Temporal databases status and research directions, ACM SIGMOD Record, v.19 n.4, p.83-89, Dec. 1990</name><name>Michael D. Soo, Bibliography on temporal databases, ACM SIGMOD Record, v.20 n.1, p.14-23, March 1991</name><name>&amp;#214;zg&amp;#252;r Ulusoy, Current research on real-time databases, ACM SIGMOD Record, v.21 n.4, p.16-21, Dec. 1992</name><name>Y. Yemini: The OSI Network Management Model, IEEE Communications Magazine, May 1993.</name></citation><abstract>Various types of computer systems are used behind the scenes in many parts of the telecommunications network to ensure its efficient and trouble-free operation. These systems are large, complex, and expensive real-time computer systems that are mission critical, and contains a database engine as a critical component. These systems share some of common database issues with conventional applications, but they also exhibit rather unique characteristics that present challenging database issues. Major DBMS issues for network management include choosing the right data model, handling two different kinds of data in terms of integrity and recovery constraints, supporting temporal queries, satisfying real-time performance and high availability requirements, and several miscellaneous issues. Some of these issues have been investigated in various areas of database researches, but most of them largely remain in the research stage. Advances in these areas that result in actual integrated implementations for data-intensive, real-time and temporal applications are eagerly awaited.</abstract></paper><paper><title>ASSET: a system for supporting extended transactions</title><author><AuthorName>A. Biliris</AuthorName><institute><InstituteName>AT&amp;T Bell Labs, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>S. Dar</AuthorName><institute><InstituteName>AT&amp;T Bell Labs, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>N. Gehani</AuthorName><institute><InstituteName>AT&amp;T Bell Labs, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>H. V. Jagadish</AuthorName><institute><InstituteName>AT&amp;T Bell Labs, Murray Hill, NJ</InstituteName><country></country></institute></author><author><AuthorName>K. Ramamritham</AuthorName><institute><InstituteName>University of Massachusetts, Amherst MA</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>R. Agrawal , N. H. Gehani, ODE (Object Database and Environment): the language and the data model, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.36-45, June 1989, Portland, Oregon, United States</name><name>Biliris A., N. Gehani, D. Lieuwen, E. Panagos, and T. Roycraft. Ode 2.0 User's Manual. AT&amp;T Bell Laboratories, 1993.</name><name>Alexandros Biliris , Euthimios Panagos, EOS: an extensible object store, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.517, May 24-27, 1994, Minneapolis, Minnesota, United States</name><name>B. R. Badrinath , Krithi Ramamritham, Semantics-based concurrency control: beyond commutativity, ACM Transactions on Database Systems (TODS), v.17 n.1, p.163-199, March 1992</name><name>Catriel Beeri , Hans-J&amp;#246;rg Schek , Gerhard Weikum, Multi-Level Transaction Management, Theoretical Art or Practical Need ?, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.134-154, March 14-18, 1988</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>Bukhres, O., A. Elmagarmid, and E. Kuhn. Implementation of the Flex Transaction Model. Bulletzn of the IEEE Technical Committee on Data Engsneerzng, 16(2):28-32, June 1993.</name><name>Panos K. Chrysanthis , Krithi Ramamritham, A Formalism for Extended Transaction Model, Proceedings of the 17th International Conference on Very Large Data Bases, p.103-112, September 03-06, 1991</name><name>Panos K. Chrysanthis , Krithi Ramamritham, Synthesis of extended transaction models using ACTA, ACM Transactions on Database Systems (TODS), v.19 n.3, p.450-491, Sept. 1994</name><name>Panos K. Chrysanthis , S. Raghuram , Krithi Ramamritham, Extracting concurrency from objects: a methodology, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.108-117, May 29-31, 1991, Denver, Colorado, United States</name><name>Umeshwar Dayal , Meichun Hsu , Rivka Ladin, Organizing long-running activities with triggers and transactions, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.204-214, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Ahmed K. Elmagarmid, Database transaction models for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>Hector Garcia-Molina , Kenneth Salem, Sagas, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.249-259, May 27-29, 1987, San Francisco, California, United States</name><name>Dimitrios Georgakopoulos , Mark F. Hornick , Piotr Krychniak , Frank Manola, Specification and Management of Extended Transactions in a Programmable Transaction Environment, Proceedings of the Tenth International Conference on Data Engineering, p.462-473, February 14-18, 1994</name><name>Henry F. Korth , Won Kim , Fran&amp;#231;ois Bancilhon, On long-duration CAD transactions, Information Sciences: an International Journal, v.46 n.1-2, p.73-107, Oct./Nov. 1988</name><name>Henry F. Korth , Eliezer levy , Abraham Silberschatz, A formal approach to recovery by compensating transactions, Proceedings of the sixteenth international conference on Very large databases, p.95-106, September 1990, Brisbane, Australia</name><name>Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983</name><name>J. E.B. Moss, Nested transactions:  an approach to reliable distributed computing, Massachusetts Institute of Technology, Cambridge, MA, 1985</name><name>Calton Pu , Gail E. Kaiser , Norman C. Hutchinson, Split-Transactions for Open-Ended Activities, Proceedings of the 14th International Conference on Very Large Data Bases, p.26-37, August 29-September 01, 1988</name><name>Ramamritham, K. and P. Chrysanthis. In Search of Acceptability Criteria: Database Consistency Requirements and Transaction Correctness Properties. Dis. tributed Object Management, Ozsu,Dayal, and Valduriez Ed., Morgan Kaufrnann, 1993.</name><name>Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990</name><name>Wachter, H. and A. Reuter. The ConTract Model. in [12].</name><name>Gerhard Weikum, Principles and realization strategies of multilevel transaction management, ACM Transactions on Database Systems (TODS), v.16 n.1, p.132-180, March 1991</name></citation><abstract>Extended transaction models in databases were motivated by the needs of complex applications such as CAD and software engineering. Transactions in such applications have diverse needs, for example, they may be long lived and they may need to cooperate. We describe ASSET, a system for supporting extended transactions. ASSET consists of a set of transaction primitives that allow users to define custom transaction semantics to match the needs of specific applications. We show how the transaction primitives can be used to specify a variety of transaction models, including nested transactions, split transactions, and sagas. Application-specific transaction models with relaxed correctness criteria, and computations involving workflows, can also be specified using the primitives. We describe the implementation of the ASSET primitives in the context of the Ode database.</abstract></paper><paper><title>ARIES/CSA: a method for database recovery in client-server architectures</title><author><AuthorName>C. Mohan</AuthorName><institute><InstituteName>Data Base Technology Institute, IBM Almaden Research Center, San Jose, CA</InstituteName><country></country></institute></author><author><AuthorName>Inderpal Narang</AuthorName><institute><InstituteName>Data Base Technology Institute, IBM Almaden Research Center, San Jose, CA</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>Michael J. Carey , Michael J. Franklin , Miron Livny , Eugene J. Shekita, Data caching tradeoffs in client-server DBMS architectures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.357-366, May 29-31, 1991, Denver, Colorado, United States</name><name>Crus, R. Data Recovery (n IBM Database 2, IBM Systems Journal, Vol. 23, No. 2, 1984.</name><name>O. Deux, The O2 system, Communications of the ACM, v.34 n.10, p.34-48, Oct. 1991</name><name>D. M. Dias , B. R. Iyer , John T. Robinson , P. S. Yu, Integrated Concurrency-Coherency Controls for Multisystem Data Sharing, IEEE Transactions on Software Engineering, v.15 n.4, p.437-448, April 1989</name><name>David J. DeWitt , Philippe Futtersack , David Maier , Fernando Velez, A study of three alternative workstation server architectures for object-oriented database systems, Proceedings of the sixteenth international conference on Very large databases, p.107-121, September 1990, Brisbane, Australia</name><name>Michael J. Franklin , Michael J. Carey , Miron Livny, Global Memory Management in Client-Server Database Architectures, Proceedings of the 18th International Conference on Very Large Data Bases, p.596-609, August 23-27, 1992</name><name>Michael J. Franklin , Michael J. Zwilling , C. K. Tan , Michael J. Carey , David J. DeWitt, Crash recovery in client-server EXODUS, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.165-174, June 02-05, 1992, San Diego, California, United States</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>Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978</name><name>Charles Lamb , Gordon Landis , Jack Orenstein , Dan Weinreb, The ObjectStore database system, Communications of the ACM, v.34 n.10, p.50-63, Oct. 1991</name><name>Lamer, D. Recovery for Shared Dlsk Systems Using Mult#pZe Redo Logs, Technical Report CRL 90/4, DEC Cambridge Research Laboratory, October 1990.</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, Commit-LSN: a novel and simple method for reducing locking and latching in transaction processing systems, Proceedings of the sixteenth international conference on Very large databases, p.406-418, September 1990, Brisbane, Australia</name><name>C. Mohan, ARIES/LHS: A Concurrency Control and Recovery Method Using Write-Ahead Logging for Linear Hashing with Separators, Proceedings of the Ninth International Conference on Data Engineering, p.243-252, April 19-23, 1993</name><name>C. Mohan, A Cost-Effective Method for Providing Improved Data Availability During DBMS Restart Recovery After a Failure, Proceedings of the 19th International Conference on Very Large Data Bases, p.368-379, August 24-27, 1993</name><name>Mohan, C, Dlsk Read-Wr# te Opttmtzatzons and Data Integrlty In Transaction Systems Us(ng Wr#te-Ahead Logglng, IBM Research Report RJ9741, IBM Almaden Research Center, March 1994.</name><name>Mohan, C. Concurrency ControZ and Recovery Methods for -Tree Indexes: ARIES/KVL and ARIES/IM, To appear in Performance of Con. currency Control Mechanisms in Centralized Database Systems, V. Kumar (Ed.), Prentice Hall, 1994. Also available as IBM Research Report Rj9715, IBM Almaden Research Center, March 1994.</name><name>C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.371-380, June 02-05, 1992, San Diego, California, United States</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>C. Mohan , Inderpal Narang, Efficient Locking and Caching of Data in the Multisystem Shard Disks Transaction Environment, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.453-468, March 23-27, 1992</name><name>Mohan, C., Narang, I. Date Base Recovery #n Shared D#sks and CI tent-Server Architectures, Proc. 12th International Conference on Distributed Computing Systems, Yokohama, June t992.</name><name>C. Mohan , Inderpal Narang, An efficient and flexible method for archiving a data base, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.139-146, May 25-28, 1993, Washington, D.C., United States</name><name>Mohan, C., Narang, I., Palmer, J. A Case Study of ProbZems #n M#grattng to D#str#buted Computzng. Page Recovery Using MuZtlple Logs in the Shared D#sks Environment, IBM Research Report RJ7343, IBM Almaden Research Center, March 1990.</name><name>Mohan, C., Narang, I., Silen, S. SoZuttons to Hot Spot Problems zn a Shared Dzsks Transaction Environment, Proc. 4th Interna. tlonal Workshop on High Performance Transaction Systems, Asilomar, September 1991.</name><name>C. Mohan , Hamid Pirahesh, ARIES-RRH: Restricted Repeating of History in the ARIES Transaction Recovery Method, Proceedings of the Seventh International Conference on Data Engineering, p.718-727, April 08-12, 1991</name><name>Rahm, E. Recovery Concepts for Data Sharing Systems, Proc. 21st International Symposium on Fault.Tolerant Computing, June 1991.</name><name>Rengarajan, T.K., Spiro, P., Wright, W. Htgh Avatlab#Z#ty Mechanisms of VAX DBMS Software, Digital Technical Journal, No. 8, February 1989.</name><name>K. Rothermel , C. Mohan, ARIES/NT: a recovery method based on write-ahead logging for nested transactions, Proceedings of the 15th international conference on Very large data bases, p.337-346, July 1989, Amsterdam, The Netherlands</name><name>Yongdong Wang , Lawrence A. Rowe, Cache consistency and concurrency control in a client/server DBMS architecture, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.367-376, May 29-31, 1991, Denver, Colorado, United States</name><name>Kevin Wilkinson , Marie-Anne Neitmat, Maintaining consistency of client-cached data, Proceedings of the sixteenth international conference on Very large databases, p.122-134, September 1990, Brisbane, Australia</name></citation><abstract>This paper presents an algorithm, called ARIES/CSA (Algorithm for Recovery and Isolation Exploiting Semantics for Client-Server Architectures), for performing recovery correctly in client-server (CS) architectures. In CS, the server manages the disk version of the database. The clients, after obtaining database pages from the server, cache them in their buffer pools. Clients perform their updates on the cached pages and produce log records. The log records are buffered locally in virtual storage and later sent to the single log at the server. ARIES/CSA supports a write-ahead logging (WAL), fine-granularity (e.g., record) locking, partial rollbacks and flexible buffer management policies like steal and no-force. It does not require   that the clocks on the clients and the server be synchronized. Checkpointing by the server and the clients allows for flexible and easier recovery.</abstract></paper><paper><title>Ensuring relaxed atomicity for flexible transactions in multidatabase systems</title><author><AuthorName>Aidong Zhang</AuthorName><institute><InstituteName>Department of Computer Science, Purdue University, West Lafayette, IN</InstituteName><country></country></institute></author><author><AuthorName>Marian Nodine</AuthorName><institute><InstituteName>Department of Computer Science, Brown University, Providence, RI</InstituteName><country></country></institute></author><author><AuthorName>Bharat Bhargava</AuthorName><institute><InstituteName>Department of Computer Science, Purdue University, West Lafayette, IN</InstituteName><country></country></institute></author><author><AuthorName>Omran Bukhres</AuthorName><institute><InstituteName>Department of Computer Science, Purdue University, West Lafayette, IN</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>Mansoor Ansari , Linda Ness , Marek Rusinkiewicz , Amit P. Sheth, Using Flexible Transactions to Support Multi-System Telecommunication Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.65-76, August 23-27, 1992</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>Yuri Breitbart , Avi Silberschatz , Glenn R. Thompson, Reliable transaction management in a multidatabase system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.215-224, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>A. Elmagarmid , Y. Leu , W. Litwin , Marek Rusinkiewicz, A multidatabase transaction model for InterBase, Proceedings of the sixteenth international conference on Very large databases, p.507-518, September 1990, Brisbane, Australia</name><name>Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983</name><name>Virgil Gligor , Radu Popescu-Zeletin, Transaction management in distributed heterogeneous database management systems, Information Systems, v.11 n.4, p.287-297, Oct. 1986</name><name>Henry F. Korth , Eliezer levy , Abraham Silberschatz, A formal approach to recovery by compensating transactions, Proceedings of the sixteenth international conference on Very large databases, p.95-106, September 1990, Brisbane, Australia</name><name>eva K&amp;#252;hn , Franz Puntigam , Ahmed K. Elmagarmid, An Execution Model for Distributed Database Transactions and Its Implementation in VPL, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.483-498, March 23-27, 1992</name><name>Eliezer Levy , Henry F. Korth , Abraham Silberschatz, An optimistic commit protocol for distributed transaction management, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.88-97, May 29-31, 1991, Denver, Colorado, United States</name><name>S. Mehrotra, R. Rastogi, H. F. Korth, and A. Silberschatz. A transaction model for multidatabase systems, in Proceedings of International Conference on Distributed Computing Systems, June 1992.</name><name>Peter Muth , Thomas C. Rakow, Atomic Commitment for Integrated Database Systems, Proceedings of the Seventh International Conference on Data Engineering, p.296-304, April 08-12, 1991</name><name>Marian Hansen Nodine, Interactions: multidatabase support for planning applications, Brown University, Providence, RI, 1993</name><name>M. H. Nodine and S. B. Zdonik. Automating compensation in a multidatabase. In Proceedings of the 27th Hawaii International Conference on System Sciences, 1994.</name><name>William Perrizo , Joseph Rajkumar , Prabhu Ram, HYDRO: a heterogeneous distributed database system, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.32-39, May 29-31, 1991, Denver, Colorado, United States</name><name>Avi Silberschatz , Michael Stonebraker , Jeff Ullman, Database systems: achievements and opportunities, Communications of the ACM, v.34 n.10, p.110-120, Oct. 1991</name><name>Nandit Soparka , Henry F. Korth , Abraham Silberschatz, Failure-Resilient Transaction Management in Multidatabase, Computer, v.24 n.12, p.28-36, December 1991</name><name>Jari Veijalainen , Frank Eliassen , Berhard Holtkamp, The S-transaction model, Database transaction models for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992</name><name>A. Wolski and J. Veijalainen. 2PC Agent method: Achieving serializability in presence of failures in a heterogeneous multidatabase. In Proceedings of PARBASE-90, Miami Beach, Florida, 1990.</name><name>A. Zhang and B. Bhargava. Scheduling with Compensation in Multidatabase Systems. Technical Report CSD-TR-93-063, Purdue University, October 1993.</name></citation><abstract>Global transaction management requires cooperation from local sites to ensure the consistent and reliable execution of global transactions in a distributed database system. In a heterogeneous distributed database (or multidatabase) environment, various local sites make conflicting assertions of autonomy over the execution of global transactions. A flexible transaction model for the specification of global transactions makes it possible to deal robustly with these conflicting requirements. This paper presents an approach that preserves the semi-atomicity (a weaker form of atomicity) of flexible transactions, allowing local sites to autonomously maintain serializability and recoverability. We offer a fundamental characterization of the flexible transaction model and precisely define the semi-atomicity. We investigate the commit dependencies among the subtransactions of a flexible transaction. These dependencies are used to control the commitment order of the subtransactions. We next identify those restrictions that must be placed upon a flexible transaction to ensure the maintenance of its semi-atomicity. As atomicity is a restrictive criterion, semi-atomicity enhances the class of executable global transactions.</abstract></paper><paper><title>Staggered striping in multimedia information systems</title><author><AuthorName>Steven Berson</AuthorName><institute><InstituteName>USC Information sciences Institute and UCLA Computer Science Department</InstituteName><country></country></institute></author><author><AuthorName>Shahram Ghandeharizadeh</AuthorName><institute><InstituteName>USC Computer Science Department</InstituteName><country></country></institute></author><author><AuthorName>Richard Muntz</AuthorName><institute><InstituteName>UCLA Computer Science Department</InstituteName><country></country></institute></author><author><AuthorName>Xiangyu Ju</AuthorName><institute><InstituteName>USC Computer Science Department</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><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>Jeff Dozier, Keynote address: access to data in NASA's Earth observing system, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.1, June 02-05, 1992, San Diego, California, United States</name><name>Edward A. Fox, Advances in Interactive Digital Multimedia Systems, Computer, v.24 n.10, p.9-21, October 1991</name><name>Shahram Ghandeharizadeh , David J. DeWitt, A Multiuser Performance Analysis of Alternative Declustering Strategies, Proceedings of the Sixth International Conference on Data Engineering, p.466-475, February 05-09, 1990</name><name>S. Ghandeharizadeh , L. Ramos, Continuous Retrieval of Multimedia Data Using Parallelism, IEEE Transactions on Knowledge and Data Engineering, v.5 n.4, p.658-669, August 1993</name><name>Shahram Ghandeharizadeh , Luis Ramos , Zubair Asad , Waheed Qureshi, Object Placement in Parallel Hypermedia Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.243-254, September 03-06, 1991</name><name>Shahram Ghandeharizadeh , Cyrus Shahabi, Management of Physical Replicas in Parallel Multimedia in Information Systems, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.51-68, October 13-15, 1993</name><name>HASKELL, B. International standards activities in image data compression. In Proceedings of Scientific Data Compression Workshop (1989), pp. 439-449. NASA conference Pub 3025, NASA Office of Management, Scientific and technical information division.</name><name>Miron Livny , Setrag Khoshafian , Haran Boral, Multi-disk management algorithms, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.69-77, May 11-14, 1987, Banff, Alberta, Canada</name><name>David Maier , Jonathan Walpole , Richard Staehli, Storage System Architectures for Continuous Media Data, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.1-18, October 13-15, 1993</name><name>David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States</name><name>RIES, D., AND EPSTEIN, R. Evaluation of distribution criteria for distributed database systems. UCB/ERL Technical Report M78/22, UC Berkeley, May 1978.</name><name>SABaE INC. IMPRIMIS Sabre E,ght Inch Module Drove User's MaT#ual, 1990.</name><name>Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986</name><name>SCHWETMAN, H. CSIM: A C-Based Process- Oriented Simulation Language. Technical Report PP-080-85, Microelectronics and Computer Technology Corporation, 1985.</name><name>Michael Stonebraker , Rakesh Agrawal , Umeshwar Dayal , Erich J. Neuhold , Andreas Reuter, DBMS Research at a Crossroads: The Vienna Update, Proceedings of the 19th International Conference on Very Large Data Bases, p.688-692, August 24-27, 1993</name><name>STONEBaAKER, M. R. The cause for Shared- Nothing. In Proceedzngs of Data Engtneer#ng '86.</name><name>TEaADATA. DBC/1012 database computer system manual release 2.0, 1985.</name></citation><abstract>Multimedia information systems have emerged as an essential component of many application domains ranging from library information systems to entertainment technology. However, most implementations of these systems cannot support the continuous display of multimedia objects and suffer from frequent disruptions and delays termed hiccups. This is due to the low I/O bandwidth of the current disk technology, the high bandwidth requirement of multimedia objects, and the large size of these objects that almost always requires them to be disk resident. One approach to resolve this limitation is to decluster a multimedia object across multiple disk drives in order to employ the aggregate bandwidth of several disks to support the continuous retrieval (and display) of objects.  This paper describes staggered striping as a novel technique to provide effective support for multiple users accessing the different objects in the database. Detailed simulations confirm the superiority of staggered striping.</abstract></paper><paper><title>Data modeling of time-based media</title><author><AuthorName>Simon Gibbs</AuthorName><institute><InstituteName>Universit&amp;#233; de Gen&amp;#232;ve</InstituteName><country></country></institute></author><author><AuthorName>Christian Breiteneder</AuthorName><institute><InstituteName>Universitaet Wien</InstituteName><country></country></institute></author><author><AuthorName>Dennis Tsichritzis</AuthorName><institute><InstituteName>Universit&amp;#233; de Gen&amp;#232;ve and GMD Bonn</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>David P. Anderson , George Homsy, A Continuous Media I/O Server and Its Synchronization Mechanism, Computer, v.24 n.10, p.51-57, October 1991</name><name>Elisa Bertino , Fausto Rabbiti , Simon Gibbs, Query processing in a multimedia document system, ACM Transactions on Information Systems (TOIS), v.6 n.1, p.1-41, Jan. 1988</name><name>Michael J. Carey , David J. DeWitt , Joel F. Richardson , Eugene J. Shekita, Storage management for objects in EXODUS, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989</name><name>S. Christodoulakis , M. Theodoridou , F. Ho , M. Papa , A. Pathria, Multimedia document presentation, information extraction, and document formation in MINOS: a model and a system, ACM Transactions on Information Systems (TOIS), v.4 n.4, p.345-383, Oct. 1986</name><name>Simon J. Gibbs , Christian Breiteneder , Dennis Tsichritzis, Audio/Video Databases: An Object-Oriented Approach, Proceedings of the Ninth International Conference on Data Engineering, p.381-390, April 19-23, 1993</name><name>Eric Hoffert , Mark Krueger , Lee Mighdoll , Michael Mills , Jonathan Cohen , Doug Camplejohn , Bruce Leak , Jim Batson , David Van Brink , Dean Blackketter , Michael Arent , Rich Williams , Chris Thorman , Mitch Yawitz , Ken Doyle , Sean Callahan, QuickTime: an extensible standard for digital multimedia, Proceedings of the thirty-seventh international conference on COMPCON, p.15-20, January 1992, San Francisco, California, United States</name><name>T. J. Lehman , B. G. Lindsay, The Starburst long field manager, Proceedings of the fifteenth international conference on Very large data bases, p.375-383, July 1989, Amsterdam, The Netherlands</name><name>Wolfgang Klas , Erich J. Neuhold , Michael Schrefl, Using an object-oriented approach to model multimedia data, Computer Communications, v.13 n.4, p.204-216, May 1990</name><name>Didier Le Gall, MPEG: a video compression standard for multimedia applications, Communications of the ACM, v.34 n.4, p.46-58, April 1991</name><name>Andrew Lippman, Feature sets for interactive images, Communications of the ACM, v.34 n.4, p.92-102, April 1991</name><name>Thomas D. C. Little , Arif Ghafoor, Spatio-Temporal Composition of Distributed Multimedia Objects for Value-Added Networks, Computer, v.24 n.10, p.42-50, October 1991</name><name>MacroMind inc. Director Studio Manual, Version 3.0, 1991.</name><name>Masunaga, Y. Multimedia Databases: A Formal Framework, Proc. IEEE CS Office Automation Symposium (Gaithersburg, MD, April 1987), IEEE CS Press, Washington, pp. 36-45.</name><name>CORPORATE Microsoft Corp., Microsoft Windows multimedia programmer's workbook, Microsoft Press, Redmond, WA, 1991</name><name>Preston, J.M. (Ed.) Compact-Disc Interactive: A Designer's Overview, Kluwer, Deventer NL, 1987.</name><name>T. K. Rengarajan, Rdb/VMS support for multi-media databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.287-287, June 02-05, 1992, San Diego, California, United States</name><name>G. David Ripley, DVI&amp;mdash;a digital multimedia technology, Communications of the ACM, v.32 n.7, p.811-822, July 1989</name><name>Lawrence A. Rowe , Brian C. Smith, A Continuous Media Player, Proceedings of the Third International Workshop on Network and Operating System Support for Digital Audio and Video, p.376-386, November 12-13, 1992</name><name>Arie Segev , Arie Shoshani, Logical modeling of temporal data, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.454-466, May 27-29, 1987, San Francisco, California, United States</name><name>Gregory K. Wallace, The JPEG still picture compression standard, Communications of the ACM, v.34 n.4, p.30-44, April 1991</name><name>Darrell Woelk , Won Kim , Willis Luther, An object-oriented approach to multimedia databases, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.311-325, May 28-30, 1986, Washington, D.C., United States</name><name>Darrell Woelk , Won Kim, Multimedia Information Management in an Object-Oriented Database System, Proceedings of the 13th International Conference on Very Large Data Bases, p.319-329, September 01-04, 1987</name></citation><abstract>Many aspects of time-based media&amp;mdash;complex data encoding, compression, &amp;ldquo;quality factors,&amp;rdquo; timing&amp;mdash;appear problematic from a data modeling standpoint. This paper proposes timed streams as the basic abstraction for modeling time-based media. Several media-independent structuring mechanisms are introduced and a data model is presented which, rather than leaving the interpretation of multimedia data to applications, addresses the complex organization and relationships present in multimedia.</abstract></paper><paper><title>Implementation of magic-sets in a relational database system</title><author><AuthorName>Inderpal Singh Mumick</AuthorName><institute><InstituteName>AT&amp;T Bell Laboratories and IBM Almaden Research Center and Stanford University</InstituteName><country></country></institute></author><author><AuthorName>Hamid Pirahesh</AuthorName><institute><InstituteName>IBM Almaden Research Center</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States</name><name>Catriel Beeri , Raghu Ramakrishnan, On the power of magic, Journal of Logic Programming, v.10 n.3-4, p.255-299, April/May 1991</name><name>Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987</name><name>Marcia A. Derr , Shinichi Morishita , Geoffrey Phipps, Design and implementation of the glue-nail database system, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.147-156, May 25-28, 1993, Washington, D.C., United States</name><name>J. Fessy and B. Finance. Early experience with recursion optimization in an extensible rewriter. In Proceedings of the Fourth Australian Database Conference (ADC), 1993.</name><name>Ashish Gupta , Inderpal Singh Mumick, Magic-sets transformation in nonrecursive systems, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.354-367, June 02-05, 1992, San Diego, California, United States</name><name>Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States</name><name>L. M. Haas , W. Chang , G. M. Lohman , J. McPherson , P. F. Wilms , G. Lapis , B. Lindsay , H. Pirahesh , M. J. Carey , E. Shekita, Starburst Mid-Flight: As the Dust Clears, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.143-160, March 1990</name><name>Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982</name><name>Guy M. Lohman, Grammar-like functional rules for representing query optimization alternatives, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.18-27, June 01-03, 1988, Chicago, Illinois, United States</name><name>I. S. Mumick , S. J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic is relevant, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.247-258, May 23-26, 1990, Atlantic City, New Jersey, 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>K. Morris, J. Naughton, Y. Saraiya, J. Ullman, and A. Van Gelder. YAWN! (Yet Another Window on Nail!). In Data Engineering 10:4, 1987.</name><name>Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia</name><name>I. Mumick, H. Pirahesh, and R. Ramakrishnan. Adornments in database programs. To appear in Computers and AI, 1994. Preliminary version appeaxed in Proceedings of the International Workshop on Deductive Databa#e#, International Conference on Logic Programming, 1993.</name><name>Inderpal Singh Mumick, Query optimization in deductive and relational databases, Stanford University, Stanford, CA, 1992</name><name>M. Muralikrishna, Improved Unnesting Algorithms for Join Aggregate SQL Queries, Proceedings of the 18th International Conference on Very Large Data Bases, p.91-102, August 23-27, 1992</name><name>S. Naqvi , S. Tsur, A logical language for data and knowledge bases, Computer Science Press, Inc., New York, NY, 1989</name><name>Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States</name><name>R, Ramakrishnan. Magic templates: A spellbinding approach to logic programs. In Proceedings of the Fifth International Conference and Symposium on Logic Programming, 1988.</name><name>Raghu Ramakrishnan , Divesh Srivastava , S. Sudarshan, CORAL - Control, Relations and Logic, Proceedings of the 18th International Conference on Very Large Data Bases, p.238-250, August 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>F. Raab. TPC-D Working Draft 6.5. In Preparation. Transaction Processing Performance Council. February 1994.</name><name>Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988</name><name>Jayen Vaghani , Kotagiri Ramamohanarao , David Kemp , Zoltan Somogyi , Peter Stuckey , Tim Leask , James Harland, Status of the Aditi deductive database system, Proceedings of the tenth international conference on logic programming on Logic programming, p.851, August 1993, Budapest, Hungary</name></citation><abstract>We describe the implementation of the magic-sets transformation in the Starburst extensible relational database system. To our knowledge this is the first implementation of the magic-sets transformation in a relational database system. The Starburst implementation has many novel features that make our implementation especially interesting to database practitioners (in addition to database researchers). (1) We use a cost-based heuristic for determining join orders (sips) before applying magic. (2) We push all equality and non-equality predicates using magic, replacing traditional predicate pushdown optimizations. (3) We apply magic to full SQL with duplicates, aggregation, null values, and subqueries. (4) We integrate magic with other relational optimization techniques. (5) The implementation is extensible.Our implementation demonstrates the feasibility of the magic-sets transformation for commercial relational systems, and provides a mechanism to implement magic as an integral part of a new database system, or as an add-on to an existing database system.</abstract></paper><paper><title>Combinatorial pattern discovery for scientific data: some preliminary results</title><author><AuthorName>Jason Tsong-Li Wang</AuthorName><institute><InstituteName>Computer and Information Science, New Jersey Institute of Technology, Newark, NJ</InstituteName><country></country></institute></author><author><AuthorName>Gung-Wei Chirn</AuthorName><institute><InstituteName>Computer and Information Science, New Jersey Institute of Technology, Newark, NJ</InstituteName><country></country></institute></author><author><AuthorName>Thomas G. Marr</AuthorName><institute><InstituteName>Cold Spring Harbor Laboratory, 100 Bungtown Rodad, Cold Spring Harbor, NY</InstituteName><country></country></institute></author><author><AuthorName>Bruce Shapiro</AuthorName><institute><InstituteName>Image Processing Section, Laboratory of Mathematical Biology, Division of Cancer Biology and Diagnosis, National Cancer, Institute, National Institutes of Health, Frederick, MD</InstituteName><country></country></institute></author><author><AuthorName>Dennis Shasha</AuthorName><institute><InstituteName>Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY</InstituteName><country></country></institute></author><author><AuthorName>Kaizhong Zhang</AuthorName><institute><InstituteName>Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7</InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992</name><name>Rakesh Agrawal , Tomasz Imieli&amp;#324;ski , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States</name><name>D. J. Bacon and W. J. Anderson. Multiple sequence alignment. Journal of Molecular Biology, 191:153- 161, 1986.</name><name>A. Bairoeh. PROSITE: A dictionary of sites and patterns in proteins. Nucleic Acids Research, 20:2013-2018, 1992.</name><name>A. Bairoch and B. Boeekmann. The SWISS- PROT protein sequence data bank. Nucleic Acidn Research, 20:2019-2022, 1992.</name><name>W. Buntine and M. D. Alto, editors. Collected Notes on the Workshop for Patfern Discover# in Large Databases. Technical Report FIA-91- 07, NASA Ames Research Center, Mof['ett Field, California, April 1991.</name><name>Andrea Califano , Isidore Rigoutsos, FLASH: A Fast Look-Up Algorithm for String Homology, Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology, p.56-64, July 01, 1993</name><name>W. G. Cochran. Sampling Techniques. Wiley, 1977.</name><name>V. Dhar , A. Tuzhilin, Abstract-Driven Pattern Discovery in Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.926-938, December 1993</name><name>W. J. Frawley, G. Piatetsky-Shapiro, and C. J. Matheus. Knowledge discovery in databases: An overview. In G. Piatetsky-Shapiro and W. J. Frawley, editors, Knowledge Discovery in Databases, pages 1-27. AAAI/MIT Press, 1991.</name><name>Karen A. Frenkel, The human genome project and informatics, Communications of the ACM, v.34 n.11, p.40-51, Nov. 1991</name><name>G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991</name><name>Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States</name><name>Jiawei Han , Yandong Cai , Nick Cercone, Knowledge Discovery in Databases: An Attribute-Oriented Approach, Proceedings of the 18th International Conference on Very Large Data Bases, p.547-559, August 23-27, 1992</name><name>S. Henikoff and J. G. Henikoff. Automated assembly of protein blocks for database searching. Nucleic Acids Research, 19(23):6565-6572, 1991.</name><name>Wen-Chi Hou , Gultekin Ozsoyoglu, Statistical estimators for aggregate relational algebra queries, ACM Transactions on Database Systems (TODS), v.16 n.4, p.600-654, Dec. 1991</name><name>Lucas Chi Kwong Hui, Color Set Size Problem with Application to String Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.230-243, April 29-May 01, 1992</name><name>Lawrence Hunter, Artificial intelligence and molecular biology, American Association for Artificial Intelligence, Menlo Park, CA, 1993</name><name>Nabil Kamel , M. Delobel , Thomas G. Marr , Robert Robbins , Jean Thierry-Mieg , Akira Tsugita, Data and Knowledge Bases for Genome Mapping: What Lies Ahead? (Panel), Proceedings of the 17th International Conference on Very Large Data Bases, p.309, September 03-06, 1991</name><name>G. M. Landau , U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, v.10 n.2, p.157-169, June 1989</name><name>R. J. Lipton, T. G. Marr, and J. D. Welsh. Computational approaches to discovering semantics in molecular biology. Proceedings of the IEEE, 77(7):1056-1060, July 1989.</name><name>Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States</name><name>Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976</name><name>Donald R. Morrison, PATRICIA&amp;mdash;Practical Algorithm To Retrieve Information Coded in A