icde_2001_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>Conference Officers</title><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Tutorials Program</title><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>External Referees</title><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Exactly-Once Semantics in a Replicated Messaging System</title><author><AuthorName>Yongqiang Huang</AuthorName><institute><InstituteName>Stanford Universit</InstituteName><country></country></institute></author><author><AuthorName>Hector Garcia-Molina</AuthorName><institute><InstituteName>Stanford Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: A wide-area distributed message delivery system can use replication to improve performance and availability. However, without safeguards, replicated messages may be delivered to a mobile device more than once, making the device's user repeat actions (e.g., making unnecessary phone calls, firing weapons repeatedly). Alternatively, they may not be delivered at all, making the user miss important messages. In this paper we address the problem of exactly-once delivery to mobile clients when messages are replicated globally. We define exactly-once semantics and propose algorithms to guarantee it. We also propose and define a relaxed version of exactly-once semantics which is appropriate for limited capability mobile devices. We study the relative performance of our algorithms compared to weaker at-least-once semantics, and find that the performance overhead of exactly-once can be minimized in most cases by careful design of the system.</abstract></paper><paper><title>CORBA Notification Service: Design Challenges and Scalable Solutions</title><author><AuthorName>R.E. Gruber</AuthorName><institute><InstituteName>AT&amp;T Lab</InstituteName><country></country></institute></author><author><AuthorName>B. Krishnamurthy</AuthorName><institute><InstituteName>AT&amp;T Lab</InstituteName><country></country></institute></author><author><AuthorName>E. Panagos</AuthorName><institute><InstituteName>Voicemate Inc</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: In this paper, we present READY, a multi-threaded implementation of the CORBA Notification Service. The main contribution of our work is the design and development of scalable solutions for the implementation of the CORBA Notification Service. In particular, we present the overall architecture of READY, discuss the key design challenges and choices we made with respect to filter evaluation and event dispatching, and present the current implementation status. Finally, we present preliminary experimental results from our current implementation.</abstract></paper><paper><title>Measuring and Optimizing a System for Persistent Database Sessions</title><author><AuthorName>Roger S. Barga</AuthorName><institute><InstituteName>Microsoft Corporatio</InstituteName><country></country></institute></author><author><AuthorName>David B. Lomet</AuthorName><institute><InstituteName>Microsoft Corporatio</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: High availability for both data and applications is rapidly becoming a business requirement. While database systems support recovery, providing high database availability, applications may still lose work because of server outages. When a server crashes, volatile state associated with the application's database session is lost and the application may require operator-assisted restart. This exposes server failures end-users and always degrades application availability. Our Phoenix/ODBC system supports persistent database sessions that can survive a database crash without the application being aware of the outage, except for possible timing considerations. This improves application availability and eliminates application programming needed to cope with database crashes. Phoenix/ODBC requires no changes to database system, data access routines, or applications. Hence, it can be deployed any application that uses ODBC to access a database. Further, our generic approach can be exploited for a variety of data access protocols. In this paper, we describe the design Phoenix/ODBC and introduce an extension to optimize response time and reduce overhead for OLTP workloads. We present performance evaluation using TPC-C and TPC-H benchmarks that demonstrate Phoenix/ODBC's extra overhead is modest.</abstract></paper><paper><title>A Temporal Algebra for an ER-Based Temporal Data Model</title><author><AuthorName>Jae Young Lee</AuthorName><institute><InstituteName>University of North Florid</InstituteName><country></country></institute></author><author><AuthorName>Ramez A. Elmasri</AuthorName><institute><InstituteName>University of Texas at Arlingto</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: There were many temporal data models proposed in the literature. Most of them are based on relational models. Despite their popularity as design and analysis tools for information systems, ER-based temporal data models do not draw as much attention as those based on relational models did. One reason is that most ER-based temporal data models lack underlying formalism and algebra. If a conceptual model, along with an algebra, is formally defined, we can design a query language that operates on the conceptual model, not on the implementation model. Also, it can provide a basis for a user-friendly, visual query language. In this paper, we present a temporal algebra for an ER-based temporal data model called ITDM (Integrated Temporal Data Model). We define ten algebraic operations and ten temporal aggregate operations. We also define time-series specific operations.</abstract></paper><paper><title>A Split Operator for Now-Relative Bitemporal Databases</title><author><AuthorName>Mikkel Agesen</AuthorName><institute><InstituteName>Aalborg Universit</InstituteName><country></country></institute></author><author><AuthorName>Michael H. Bohlen</AuthorName><institute><InstituteName>Aalborg Universit</InstituteName><country></country></institute></author><author><AuthorName>Lasse O. Poulsen</AuthorName><institute><InstituteName>Aalborg Universit</InstituteName><country></country></institute></author><author><AuthorName>Kristian Torp</AuthorName><institute><InstituteName>Aalborg Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: The timestamps of now-relative bitemporal databases are modeled as growing, shrinking, or rectangular regions. The shape of these regions makes it a challenge to design bitemporal operators that a) are consistent with the point-based interpretation of a temporal database, b) preserve identity of the argument timestamps, c) ensure locality, and d) perform efficiently. We identify the bitemporal split operator as the basic primitive to implement a wide range advanced now-relative bitemporal operations. The bitemporal split operator splits each tuple of a bitemporal argument relation, such that equality and standard nontemporal algorithms can be used to implement the bitemporal counterparts with the aforementioned properties. Both a native database algorithm and an SQL implementation are provided. Our performance results show that the bitemporal split operator outperforms related approaches by orders magnitude and scales well.</abstract></paper><paper><title>Incremental Computation and Maintenance of Temporal Aggregates</title><author><AuthorName>Jun Yang</AuthorName><institute><InstituteName>Stanford Universit</InstituteName><country></country></institute></author><author><AuthorName>Jennifer Widom</AuthorName><institute><InstituteName>Stanford Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: We consider the problems of computing aggregation queries in temporal databases, and of maintaining materialized temporal aggregate views efficiently. The latter problem is particularly challenging since a single data update can cause aggregate results to change over the entire time line. We introduce a new index structure called the SB-tree, which incorporates features from both segment-trees and B-trees. SB-trees support fast lookup of aggregate results based on time, and can be maintained efficiently when the data changes. We also extend the basic SB-tree index to handle cumulative (also called moving-window)aggregates. For materialized aggregate views in a temporal database or warehouse, we propose building and maintaining SB-tree indices instead of the views themselves.</abstract></paper><paper><title>The Importance of Extensible Database Systems for e-Commerce</title><author><AuthorName>Samuel DeFazio</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Ramkumar Krishnan</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Jagannathan Srinivasan</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Saydean Zeldin</AuthorName><institute><InstituteName>Mercator Software, Inc</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Over the last decade, database system products have been extended to provide support for defining, storing, updating, indexing, and retrieving complex data with full transaction semantics. Oracle, IBM, Informix and others have used extensibility technology to build database system extensions for text, image, spatial, audio/video, chemical, genetic, and other types of complex data. Currently, we find database systems being deployed in support of e-Commerce. In many cases these e-Commerce database applications use only simple SQL data types to represent items such as office supplies, computers, books, and CDs. There is also a large and important set of e-Commerce applications that employ complex data formats such as EDI, SWIFT, and HL7. The database extensibility features initially developed to support text, spatial and similar forms of complex data are now being used to build e-Commerce applications. Thus, database extensibility technology is evolving into an important mechanism to enable development of e-Commerce systems.</abstract></paper><paper><title>E-Business Applications for Supply Chain Management: Challenges and Solutions</title><author><AuthorName>Fabio Casati</AuthorName><institute><InstituteName>Hewlett-Packard Lab</InstituteName><country></country></institute></author><author><AuthorName>Umesh Dayal</AuthorName><institute><InstituteName>Hewlett-Packard Lab</InstituteName><country></country></institute></author><author><AuthorName>Ming-Chien Shan</AuthorName><institute><InstituteName>Hewlett-Packard Lab</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Supply chain management is a crucial activity in every company. Surprisingly, today most of the supply chain activities are carried out manually, and IT support often limited to having a set of (disconnected) data repositories. In addition, B2B communications are performed via phone, fax, or email. Increasing operational efficiency of the supply chain results in huge savings, and is the key towards remaining competitive even gaining a competitive advantage. Furthermore, more efficient supply chain also enables revenue growth, which is often impossible to sustain with the current manual operations. In this paper we discuss the requirements and challenges for e-business applications that support supply chain management. Then, we propose an architecture that meets the requirements and enables solutions that deliver results quickly and evolve with the business and environment. Both the requirements and the architecture are the results of several different types of supply chain automation projects in which we have been involved.</abstract></paper><paper><title>Model-Based Mediation with Domain Maps</title><author><AuthorName>Bertram Ludascher</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Amarnath Gupta</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Maryann E. Martone</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: We propose an extension to current view-based mediator systems called model-based mediation, in which views are defined and executed at the level of conceptual models (CMs) rather than at the structural level. Structural integration and lifting of data to the conceptual level is &amp;quot;pushed down&amp;quot; from the mediator to wrappers which in our system export classes, associations, constraints, and query capabilities of a source. Another novel feature of our architecture is the use of domain maps, semantic nets of concepts and relationships that are used to mediate across sources from multiple worlds (i.e., whose data are related in indirect and often complex ways). As part of registering a source's CM with the mediator, the wrapper creates a &amp;quot;semantic index&amp;quot; of its data into the domain map. We show that these indexes not only semantically correlate the multiple worlds data and thereby support the definition of the integrated CM, but that they are also useful during query processing, for example, to select relevant sources. A first prototype of the system has been implemented for a complex Neuroscience mediation problem.</abstract></paper><paper><title>Processing Queries with Expensive Functions and Large Objects in Distributed Mediator Systems</title><author><AuthorName>Luc Bouganim</AuthorName><institute><InstituteName>INRIA Rocquencour</InstituteName><country></country></institute></author><author><AuthorName>Francoise Fabret</AuthorName><institute><InstituteName>PRiSM Laborator</InstituteName><country></country></institute></author><author><AuthorName>Fabio Porto</AuthorName><institute><InstituteName>PUC-Ri</InstituteName><country></country></institute></author><author><AuthorName>Patrick Valduriez</AuthorName><institute><InstituteName>University Paris</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: LeSelect is a mediator system which allows scientists to publish their resources (data and programs) so they can be transparently accessed. The scientists can typically issue queries which access distributed published data and involve the execution of expensive functions (corresponding to programs). Furthermore, the queries can involve large objects such as images (e.g., archived meteorological satellite data). In this context, the costs of transmitting large objects and invoking expensive functions are the dominant factors of execution time. In this paper, we first propose three query execution techniques which minimize these costs by taking full advantage of the distributed architecture of mediator systems like LeSelect. Then, we devise parallel processing strategies for queries including expensive functions. Based on experimentation, we show that it is hard to predict the optimal execution order when dealing with several functions. We propose a new hybrid parallel technique to solve this problem and give some experimental results.</abstract></paper><paper><title>Tuning an SQL-Based PDM System in a Worldwide Client/Server Environment</title><author><AuthorName>E. Muller</AuthorName><institute><InstituteName>University of Ul</InstituteName><country></country></institute></author><author><AuthorName>P. Dadam</AuthorName><institute><InstituteName>University of Ul</InstituteName><country></country></institute></author><author><AuthorName>J. Enderle</AuthorName><institute><InstituteName>University of Ul</InstituteName><country></country></institute></author><author><AuthorName>M. Feltes</AuthorName><institute><InstituteName>DaimlerChrysle</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: The management of product-related data in a uniform and consistent way is a big challenge for many manufacturing enterprises, especially the large ones like DaimlerChrysler. So-called Product Data Management systems (PDMS) are a promising way to achieve this goal. For various reasons PDMS often sit on-top of a relational DBMS using it (more or less) as a simple record manager. User interactions with the PDMS are translated into series of SQL queries. This does not cause too much harm when DBMS and PDMS are located in the same local-area network with high bandwidth and little latency times. The picture may change dramatically, however, if the users are working in geographically distributed environments. Response times may rise by orders of magnitude, e. g. from 1-2 minutes in the local context to 30 minutes and even more in the &amp;quot;intercontinental&amp;quot; context. The paper shows how a more sophisticated utilization of the (advanced) SQL features coming along with SQL:1999 can help to cut down response times significantly.</abstract></paper><paper><title>Bundles in Captivity: An Application of Superimposed Information</title><author><AuthorName>Lois Delcambre</AuthorName><institute><InstituteName>Oregon Graduate Institut</InstituteName><country></country></institute></author><author><AuthorName>David Maier</AuthorName><institute><InstituteName>Oregon Graduate Institut</InstituteName><country></country></institute></author><author><AuthorName>Shawn Bowers</AuthorName><institute><InstituteName>Oregon Graduate Institut</InstituteName><country></country></institute></author><author><AuthorName>Mathew Weaver</AuthorName><institute><InstituteName>Oregon Graduate Institut</InstituteName><country></country></institute></author><author><AuthorName>Longxing Deng</AuthorName><institute><InstituteName>Oregon Graduate Institut</InstituteName><country></country></institute></author><author><AuthorName>Paul Gorman</AuthorName><institute><InstituteName>Oregon Health Sciences Universit</InstituteName><country></country></institute></author><author><AuthorName>Joan Ash</AuthorName><institute><InstituteName>Oregon Health Sciences Universit</InstituteName><country></country></institute></author><author><AuthorName>Mary Lavelle</AuthorName><institute><InstituteName>Oregon Health Sciences Universit</InstituteName><country></country></institute></author><author><AuthorName>Jason A. Lyman</AuthorName><institute><InstituteName>Oregon Health Sciences Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: What do you do to make sense of a mass of information on a given topic? Paradoxically, you likely add yet more information to the pile: annotations, underlining, bookmarks, cross-references. We want to build digital information systems for managing such added or super-imposed information and support applications that create and manipulate it. We find that requirements for a superimposed information system can be quite different from those for a traditional database management system: a lightweight implementation, multi-model information structures, &amp;quot;schema-later&amp;quot; data entry, interacting with data that is &amp;quot;outside the box&amp;quot; (controlled by other applications), and support, rather than removal, of redundancy. We report here on SLIMPad, a superimposed application, which was inspired by the &amp;quot;bundling&amp;quot; of information elements from disparate sources we observed in a medical setting. We propose an architecture for superimposed applications and information management. Our prototype components to implement the architecture give flexibility in structuring superimposed information, and also encapsulate addressing, at a sub-document granularity, into a variety of base information sources.</abstract></paper><paper><title>High-Level Parallelisation in a Database Cluster: A Feasibility Study Using Document Services</title><author><AuthorName>Torsten Grabs</AuthorName><institute><InstituteName>Swiss Federal Institute of Technolog</InstituteName><country></country></institute></author><author><AuthorName>Klemens Bohm</AuthorName><institute><InstituteName>Swiss Federal Institute of Technolog</InstituteName><country></country></institute></author><author><AuthorName>Hans-Jorg Schek</AuthorName><institute><InstituteName>Swiss Federal Institute of Technolog</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Our concern is the design of a scalable infrastructure for complex application services. We want to find out if a cluster of commodity database systems is well-suited as such an infrastructure. To this end, we have carried out a feasibility study based on document services, e.g., document insertion and retrieval. We decompose a service request into short parallel database transactions. Our system, implemented as an extension of a transaction processing monitor, routes the short transactions to the appropriate database systems in the cluster. Routing depends on the data distribution that we have chosen. To avoid bottlenecks, we distribute document functionality such as term extraction over the cluster. Extensive experiments show the following: (1) A relatively small number of components--for example 8 components--already suffices to cope with high workloads of more than 100 concurrently active clients. (2) Speedup and throughput increase linearly for insertion operations when increasing the cluster size. These observations also hold when bundling service invocations into transactions at the semantic layer. A specialized coordinator component then implements semantic serializability and atomicity. Our experiments show that such a coordinator has minimal impact on CPU resource consumption and on response times.</abstract></paper><paper><title>Efficient Sequenced Temporal Integrity Checking</title><author><AuthorName>Wei Li</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Richard T. Snodgrass</AuthorName><institute><InstituteName>University of Arizon</InstituteName><country></country></institute></author><author><AuthorName>Shiyan Deng</AuthorName><institute><InstituteName>University of Arizon</InstituteName><country></country></institute></author><author><AuthorName>Aravindan Kasthurirangany</AuthorName><institute><InstituteName>University of Arizon</InstituteName><country></country></institute></author><author><AuthorName>Vineel K. Gattu</AuthorName><institute><InstituteName>Microsoft Corporatio</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Primary key and referential integrity are the most widely used integrity constraints in relational databases. Each has a sequenced analogue in temporal databases, in which the constraint must apply independently at every point in time. In this paper, we assume a stratum approach, which expresses the checking in conventional SQL, as triggers on period-stamped relations. We evaluate several novel approaches that exploit B+-tree indexes to enable efficient checking of sequenced primary key (SPK) and referential integrity (SRI) constraints. We start out with a brute force SPK algorithm, then adapt the Relational Interval-tree overlap algorithm. After that, we propose a new method, the Straight Traversal algorithm, which utilizes the B+-tree more directly to identify when multiple key values are present. Our evaluation, on two platforms, shows that Straight Traversal algorithm approaches the performance of built-in nontemporal primary key and referential integrity checking, with constant time per tuple.</abstract></paper><paper><title>XML Data and Object Databases: The Perfect Couple?</title><author><AuthorName>Andreas Renner</AuthorName><institute><InstituteName>POET Softwar</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: XML is increasingly gaining acceptance as a medium for exchanging data between applications. Given its text-based structure, XML can easily be distributed across any type of communication channel, including the Internet. This article provides an overview of an efficient way to store XML data inside an object-oriented database management system (OODBMS). It first discusses the difference between XML data and XML documents, and then introduces an approach to integrate XML data into the Java .programming language and programming model. This integration is combined with the transparent persistence of Java objects defined by the ODMG.</abstract></paper><paper><title>Tamino - A DBMS Designed for XML</title><author><AuthorName>Dr. Harald Schoning</AuthorName><institute><InstituteName>Software A</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Tamino is Software AG's XML database management system. In contrast to solutions of other DBMS vendors, Tamino is not just another layer on top of a database system designed to support the relational or an object-oriented data model. Rather, Tamino has been completely designed for XML. This paper gives a short overview of Tamino's architecture and then addresses some of the design considerations for Tamino. In particular, areas are presented where database design for XML was nontrivial, and where some issues are still open.</abstract></paper><paper><title>The Nimble XML Data Integration System</title><author><AuthorName>Denise Draper</AuthorName><institute><InstituteName>Nimble Technology, Inc</InstituteName><country></country></institute></author><author><AuthorName>Alon Y. HaLevy</AuthorName><institute><InstituteName>Nimble Technology, Inc</InstituteName><country></country></institute></author><author><AuthorName>Daniel S. Weld</AuthorName><institute><InstituteName>Nimble Technology, Inc</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: For better or for worse, XML has emerged as a de facto standard for data interchange. This consensus is likely to lead to increased demand for technology that allows users to integrate data from a variety of applications, repositories, and partners which are located across the corporate intranet or on the Internet. Nimble Technology has spent two years developing a product to service this market. Originally conceived after decades of person-years of research on data integration, the product is now being deployed at several Fortune-500 beta-customer sites. This abstract reports on the key challenges we faced in the design of our product and highlights some issues we think require more attention from the research community. In particular, we address architectural issues arising from designing a product to support XML as its core representation, choices in the design of the underlying algebra, on-the-fly data cleaning and caching and materialization policies.</abstract></paper><paper><title>High-Performance, Space-Efficient, Automated Object Locking</title><author><AuthorName>Laurent Daynes</AuthorName><institute><InstituteName>Sun Microsystems Laboratorie</InstituteName><country></country></institute></author><author><AuthorName>Grzegorz Czajkowski</AuthorName><institute><InstituteName>Sun Microsystems Laboratorie</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: The paper studies the impact of several lock manager designs on the overhead imposed to a persistent programming language by automated object locking. Our study reveals that a lock management method based on lock state sharing outperforms more traditional lock management designs. Lock state sharing is a novel lock management method that represents all lock data structures with equal values with a single shared data structure. Sharing the value of locks has numerous benefits: (i) it makes the space consumed by the lock manager small and independent of the number of locks acquired by transactions, (ii) it eliminates the need for expensive book-keeping of locks by transactions, and (iii) it enables the use of memoization techniques for whole locking operations. These advantages add up to make the release of locks practically free, and the processing of over 99% of lock requests between 8 to 14 RISC instructions.</abstract></paper><paper><title>Differential Logging: A Commutative and Associative Logging Scheme for Highly Parallel Main Memory Database</title><author><AuthorName>Juchang Lee</AuthorName><institute><InstituteName>Seoul National Universit</InstituteName><country></country></institute></author><author><AuthorName>Kihong Kim</AuthorName><institute><InstituteName>Seoul National Universit</InstituteName><country></country></institute></author><author><AuthorName>Sang K. Cha</AuthorName><institute><InstituteName>Seoul National Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: With a gigabyte of memory priced at less than $2,000, the main-memory DBMS (MMDBMS) is emerging as an economically viable alternative to the disk-resident DBMS (DRDBMS) in many problem domains. The MMDBMS can show significantly higher performance than the DRDBMS by reducing disk accesses to the sequential form of log writing and the occasional checkpointing. Upon the system crash, the recovery process begins by accessing the disk-resident log and checkpoint data to restore a consistent state. With the increasing CPU speed, however, such disk access is still the dominant bottleneck in the MMDBMS. To overcome this bottleneck, this paper explores alternatives of parallel logging and recovery. The major contribution of this paper is the so-called differential logging scheme that permits unrestricted parallelism in logging and recovery. Using the bit-wise XOR operation both to compute the differential log between the before and after images and to recover the consistent database state, this scheme offers the room for significant performance improvement in the MMDBMS. First, with logging done on the difference, the log volume is reduced to almost half compared with the conventional physical logging. Second, the commutativity and associativity of XOR enables processing of log records in an arbitrary order. This means that we can freely distribute log records to multiple disks to improve the logging performance. During the recovery time, we can do parallel restart independently for each log disk. This paper shows the superior performance of the differential logging comparatively with the physical logging in the shared-memory multiprocessor environment.</abstract></paper><paper><title>Efficient Bulk Deletes in Relational Databases</title><author><AuthorName>A. Gartner</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>A. Kemper</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>B. Zeller</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>D. Kossmann</AuthorName><institute><InstituteName>Technische Universit鋞 M黱che</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Many applications require that large amounts of data are deleted from the database - typically, such bulk deletes are carried out periodically and involve old or out-of-date data. If the data is not partitioned in such a way that bulk deletes can be carried out by simply deleting whole partitions, then most current database products execute such bulk delete operations very poorly. The reason is that every record is deleted from each index individually. This paper proposes and evaluates a new class of techniques to support bulk delete operations more efficiently. These techniques outperform the &amp;quot;record-at-a-time&amp;quot; approach implemented in many database products by about one order of magnitude.</abstract></paper><paper><title>On Dual Mining: From Patterns to Circumstances, and Back</title><author><AuthorName>Gosta Grahne</AuthorName><institute><InstituteName>Concordia Universit</InstituteName><country></country></institute></author><author><AuthorName>Xiaohong Wang</AuthorName><institute><InstituteName>Concordia Universit</InstituteName><country></country></institute></author><author><AuthorName>Ming Hao Xie</AuthorName><institute><InstituteName>Concordia Universit</InstituteName><country></country></institute></author><author><AuthorName>Laks V.S. Lakshmanan</AuthorName><institute><InstituteName>Concordia University and II</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Previous work on frequent itemset mining has focused on finding all itemsets that are frequent in a specified part of a database. In this paper, we motivate the dual question of finding under what circumstances a given itemset satisfies a pattern of interest (e.g., frequency) in a database. Circumstances form a lattice that generalizes the instance lattice associated with datacube. Exploiting this, we adapt known cube algorithms and propose our own, minCirc, for mining the strongest (e.g., minimal) circumstances under which an itemset satisfies a pattern. Our experiments show minCirc is competitive with the adapted algorithms. We motivate mining queries involving migration between itemset and circumstance lattices and propose the notion of Armstrong Basis as a structure that provides efficient support for such migration queries, as well as a simple algorithm for computing it.</abstract></paper><paper><title>Mining Partially Periodic Event Patterns with Unknown Periods</title><author><AuthorName>Sheng Ma</AuthorName><institute><InstituteName>IBM T.J. Watson Research Cente</InstituteName><country></country></institute></author><author><AuthorName>Joseph L. Hellerstein</AuthorName><institute><InstituteName>IBM T.J. Watson Research Cente</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Periodic behavior is common in real-world applications. However; in many cases, periodicities are partial in that they are present only intermittently. Herein, we study such intermittent patterns, which we refer to as p-pattems. Our formulation of p-patterns takes into account imprecise time information ( e.g., due to unsynchronized clocks in distributed environments), noisy data (e.g., due to extraneous events), and shifts in phase and/or periods. We structure mining for p-patterns as two sub-tasks: (1) finding the periods of p-patterns and (2) mining temporal associations. For (2), a level-wise algorithm is used. For (1), we develop a novel approach based on a chi-squared test, and study its performance in the presence of noise. Further; we develop two algorithms for mining p-patterns based on the order in which the aforementioned sub-tasks are performed: the period-first algorithm and the association-first algorithm. Our resuits show that the association-first algorithm has a higher tolerance to noise; the period-first algorithm is more computationally efficient and provides flexibility as to the specification of support levels. In addition, we apply the period-first algorithm to mining data collected from two production computer networks, a process that led to several actionable insights.</abstract></paper><paper><title>PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth</title><author><AuthorName>Jian Pei</AuthorName><institute><InstituteName>Simon Fraser Universit</InstituteName><country></country></institute></author><author><AuthorName>Jiawei Han</AuthorName><institute><InstituteName>Simon Fraser Universit</InstituteName><country></country></institute></author><author><AuthorName>Behzad Mortazavi-Asl</AuthorName><institute><InstituteName>Simon Fraser Universit</InstituteName><country></country></institute></author><author><AuthorName>Helen Pinto</AuthorName><institute><InstituteName>Simon Fraser Universit</InstituteName><country></country></institute></author><author><AuthorName>Qiming Chen</AuthorName><institute><InstituteName>Hewlett-Packard Labs</InstituteName><country></country></institute></author><author><AuthorName>Umeshwar Dayal</AuthorName><institute><InstituteName>Hewlett-Packard Labs</InstituteName><country></country></institute></author><author><AuthorName>Mei-Chun Hsu</AuthorName><institute><InstituteName>Hewlett-Packard Labs</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Sequential pattern mining is an important data mining problem with broad applications. It is challenging since one may need to examine a combinatorially explosive number of possible subsequence patterns. Most of the previously developed sequential pattern mining methods follow the methodology of Apriori which may substantially reduce the number of combinations to be examined. However, Apriori still encounters problems when a sequence database is large and/or when sequential patterns to be mined are numerous and/or long. In this paper, we propose a novel sequential pattern mining method, called PrefixSpan (i.e., Prefix-projected Sequential pattern mining), which explores prefix-projection in sequential pattern mining. PrefixSpan mines the complete set of patterns but greatly reduces the efforts of candidate subsequence generation. Moreover, prefix-projection substantially reduces the size of projected databases and leads to efficient processing. Our performance study shows that PrefixSpan outperforms both the Apriori-based GSP algorithm and another recently proposed method, FreeSpan, in mining large sequence databases.PrefixSpan</abstract></paper><paper><title>Mobile Data Management: Challenges of Wireless and Offline Data Access</title><author><AuthorName>Eric Giguere</AuthorName><institute><InstituteName>iAnywhere Solutions, Inc., a Sybase Compan</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Applications require access to database servers for many purposes. Mobile users, those who use their computing devices away from a traditional local area network, require access to data even when central database servers are unavailable. iAnywhere Solutions provides a number of solutions that address the challenges of offline and wireless data access. In this talk, we discuss those challenges and our solutions.</abstract></paper><paper><title>Microsoft Server Technology for Mobile and Wireless Applications</title><author><AuthorName>Praveen Seshadri</AuthorName><institute><InstituteName>Microsoft Corporatio</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Microsoft is building a number of server technologies that are targeted at mobile and wireless applications. These technologies cover a wide range of customer scenarios and application requirements. This presentation discusses some of these technologies in detail.</abstract></paper><paper><title>IBM DB2 Everyplace: A Small Footprint Relational Database System</title><author><AuthorName>Jonas S Karlsson</AuthorName><institute><InstituteName>IBM Silicon Valley Laborator</InstituteName><country></country></institute></author><author><AuthorName>Amrish Lal</AuthorName><institute><InstituteName>IBM Silicon Valley Laborator</InstituteName><country></country></institute></author><author><AuthorName>Cliff Leung</AuthorName><institute><InstituteName>IBM Silicon Valley Laborator</InstituteName><country></country></institute></author><author><AuthorName>Thanh Pham</AuthorName><institute><InstituteName>IBM Silicon Valley Laborator</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Handheld and embedded devices are becoming increasingly popular and their uses are more versatile. Applications on these devices often need storing, retrieving and synchronizing data. IBM DB2 Everyplace is a high performance small footprint DBMS that is targeted in this market segment. In this paper, we will describe the overall architecture, features and several design consideration.</abstract></paper><paper><title>Dependable Computing in Virtual Laboratories</title><author><AuthorName>G. Alonso</AuthorName><institute><InstituteName>Swiss Federal Institute of Technology (ETH</InstituteName><country></country></institute></author><author><AuthorName>W. Bausch</AuthorName><institute><InstituteName>Swiss Federal Institute of Technology (ETH</InstituteName><country></country></institute></author><author><AuthorName>C. Pautasso</AuthorName><institute><InstituteName>Swiss Federal Institute of Technology (ETH</InstituteName><country></country></institute></author><author><AuthorName>A. Kahn</AuthorName><institute><InstituteName>Swiss Federal Institute of Technology (ETH</InstituteName><country></country></institute></author><author><AuthorName>M. Hallett</AuthorName><institute><InstituteName>McGill Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Many scientific disciplines are shifting from in vitro to in silico research as more physical processes and natural phenomena are examined in a computer (in silico) instead of being observed (in vitro). In many of these virtual laboratories, the computations involved are very complex and long lived. Currently, users are required to manually handle almost all aspects of such computations, including their dependability. Not surprisingly, this is a major bottleneck and a significant source of inefficiencies. To address this issue, we have developed BioOpera, an extensible process support management system for virtual laboratories. In this paper, we briefly discuss the architecture and functionality of Bio-Opera and show how it can be used to efficiently manage long lived computations.</abstract></paper><paper><title>Workflow and Process Synchronization with Interaction Expressions and Graphs</title><author><AuthorName>Christian Heinlein</AuthorName><institute><InstituteName>University of Ul</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Current workflow management technology does not provide adequate means for inter-workflow coordination as concurrently executing workflows are considered completely independent. While this simplified view might suffice for one application domain or the other, there are many real-world application scenarios where workflows--though independently modeled in order to remain comprehensible and manageable--are semantically interrelated. As pragmatical approaches, like merging interdependent workflows or inter-workflow message passing, do not satisfactorily solve the inter-workflow coordination problem, interaction expressions and graphs are proposed as a simple yet powerful formalism for the specification and implementation of synchronization conditions in general and inter-workflow dependencies in particular. In addition to a graph-based semi-formal interpretation of the formalism, a precise formal semantics, an equivalent operational semantics, an efficient implementation of the latter, and detailed complexity analyses have been developed allowing the formalism to be actually applied to solve real-world problems like inter-workflow coordination.</abstract></paper><paper><title>Inter-Enterprise Collaborative Business Process Management</title><author><AuthorName>Qiming Chen</AuthorName><institute><InstituteName>HP Lab</InstituteName><country></country></institute></author><author><AuthorName>Meichun Hsu</AuthorName><institute><InstituteName>HP Lab</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Conventional workflow systems are primarily designed for intra-enterprise process management, and they are hardly used to handle processes with tasks and data separated by enterprise boundaries, for reasons such as security, privacy, sharability, firewalls, etc. Further the cooperation of multiple enterprises is often based on peer-to-peer interactions rather than centralized coordination. As a result, the conventional centralized process management architecture does not fit into the picture of inter-enterprise business-to-business E-Commerce. We have developed a Collaborative Process Manager (CPM) to support decentralized, peer-to-peer process management for inter-enterprise collaboration at the business process level. A collaborative process is not handled by a centralized workflow engine, but by multiple CPMs, each represents a player in the business process. Each CPM is used to schedule, dispatch and control the tasks of the process that the player is responsible for, and the CPMs interoperate through an inter-CPM messaging protocol. We have implemented CPM and embedded it into a dynamic software agent architecture, E-Carry, that we developed at HP Labs, to elevate multi-agent cooperation from the conversation level to the process level for mediating E-Commerce applications.</abstract></paper><paper><title>Duality-Based Subsequence Matching in Time-Series Databases</title><author><AuthorName>Yang-Sae Moon</AuthorName><institute><InstituteName>Korea Advanced Institute of Science and Technology (KAIST</InstituteName><country></country></institute></author><author><AuthorName>Kyu-Young Whang</AuthorName><institute><InstituteName>Korea Advanced Institute of Science and Technology (KAIST</InstituteName><country></country></institute></author><author><AuthorName>Woong-Kee Loh</AuthorName><institute><InstituteName>Korea Advanced Institute of Science and Technology (KAIST</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: In this paper, we propose a new subsequence matching method, Dual Match, which exploits duality in constructing windows and significantly improves performance. Dual Match divides data sequences into disjoint windows and the query sequence into sliding windows, and thus, is a dual approach of the one by Faloutsos et al. (FRM in short), which divides data sequences into sliding windows and the query sequence into disjoint windows. We formally prove that our dual approach is correct, i.e., it incurs no false dismissal. We also prove that, given the minimum query length, there is a maximum bound of the window size to guarantee correctness of Dual Match and discuss the effect of the window size on performance. FRM causes a lot of false alarms (i.e., candidates that do not qualify) by storing minimum bounding rectangles rather than individual points representing windows to avoid excessive storage space required for the index. Dual Match solves this problem by directly storing points, but without incurring excessive storage overhead. Experimental results show that, in most cases, Dual Match provides large improvement in both false alarms and performance over FRM, given the same amount of storage space. In particular, for low selectivities (less than 10^{-4}), Dual Match significantly improves performance up to 430-fold. On the other hand, for high selectivities (more than 10^{-2}), it shows a very minor degradation (less than 29%). For selectivities in between (10^{-4} \approx 10^{-2}), Dual Match shows performance slightly better than that of FRM. Dual Match is also 4.10 \approx 25.6 times faster than FRM in building indexes of approximately the same size. Overall, these results indicate that our approach provides a new paradigm in subsequence matching that improves performance significantly in large database applications.</abstract></paper><paper><title>Variable Length Queries for Time Series Data</title><author><AuthorName>Tamer Kahveci</AuthorName><institute><InstituteName>University of Californi</InstituteName><country></country></institute></author><author><AuthorName>Ambuj Singh</AuthorName><institute><InstituteName>University of Californi</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Finding similar patterns in a time sequence is a well-studied problem. Most of the current techniques work well for queries of a prespecified length, but not for variable length queries. We propose a new indexing technique that works well for variable length queries. The central idea is to store index structures at different resolutions for a given dataset. The resolutions are based on wavelets. For a given query, a number of subqueries at different resolutions are generated. The ranges of the subqueries are progressively refined based on results from previous subqueries. Our experiments show that the total cost for our method is 4 to 20 times less than the current techniques including Linear Scan. Because of the need to store information at multiple resolution levels, the storage requirement of our method could potentially be large. In the second part of the paper, we show how the index information can be compressed with minimal information loss. According to our experimental results, even after compressing the size of the index to one fifth, the total cost of our method is 3 to 15 times less than the current techniques.</abstract></paper><paper><title>TAR: Temporal Association Rules on Evolving Numerical Attributes</title><author><AuthorName>Wei Wang</AuthorName><institute><InstituteName>IB</InstituteName><country></country></institute></author><author><AuthorName>Jiong Yang</AuthorName><institute><InstituteName>IB</InstituteName><country></country></institute></author><author><AuthorName>Richard Muntz</AuthorName><institute><InstituteName>UCL</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Data mining has been an area of increasing interests during recent years. The association rule discovery problem in particular has been widely studied. However, there are still some unresolved problems. For example, research on mining patterns in the evolution of numerical attributes is still lacking. This is both a challenging problem and one with significant practical application in business, science, and medicine. In this paper, we present a temporal association rule model for evolving numerical attributes. Metrics for qualifying a temporal association rule include the familiar measures of support and strength used in the traditional association rule mining and a new metric called density. The density metric not only gives us a way to extract the rules that best represent the data, but also provides an effective mechanism to prune the search space. An efficient algorithm is devised for mining temporal association rules, which utilizes all three thresholds (especially the strength) to prune the search space drastically. Moreover, the resulting rules are represented in a concise manner via rule sets to reduce the output size. Experimental results on real and synthetic data sets demonstrate the efficiency of our algorithm.</abstract></paper><paper><title>Database Performance for Next Generation Telecommunications</title><author><AuthorName>Munir Cochinwala</AuthorName><institute><InstituteName>Telcordia Technologie</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Three important trends in telecommunications have received media attention for their potentially wide-ranging impacts. The first is increasing competition among telephone service providers, spurred in the United States by the Telecommunications Act of 1996. The second is the technological convergence between telephony and the Internet. The third is the ever-increasing number of mobile devices and users. In this paper we explore the effects of these trends on telecommunication network databases.</abstract></paper><paper><title>Data Management Support of Web Applications</title><author><AuthorName>Dan Fishman</AuthorName><institute><InstituteName>BEA Systems, Inc</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Automating the interactions between trusted business partners is a major goal of businesses today. This is often called &amp;quot;supply chain integration.&amp;quot; The intent is to make the businesses more responsive to customer needs, and more efficient in their business or manufacturing processes. This talk describes an infrastructure that facilitates the collaboration of trusted business partners to achieve common business goals.</abstract></paper><paper><title>An Automated Change-Detection Algorithm for HTML Documents Based on Semantic Hierarchies</title><author><AuthorName>Seung-Jin Lim</AuthorName><institute><InstituteName>Brigham Young Universit</InstituteName><country></country></institute></author><author><AuthorName>Yiu-Kai Ng</AuthorName><institute><InstituteName>Brigham Young Universit</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Data at many Web sites are changing rapidly, and a significant amount of these data are presented in HTML documents that consist of markups and data contents. Although XML is getting more popular in data exchange, the presentation of data contained in XML documents is given by and large in the HTML format using XSL(T). Since HTML was designed to &amp;quot;display&amp;quot; data from the human perspective, it is not trivial for a machine to detect (hierarchical) changes of data in an HTML document. In this paper, we propose a heuristic algorithm, called SCD, to detect semantic changes of hierarchical data contents in any two HTML documents automatically. Semantic changes differ from syntactic changes since the latter refer to changes of data contents with respect to markup structures according to the HTML grammar. SCD does not require preprocessing nor any knowledge of the internal structure of the source documents beforehand. The time complexity of SCD is O((\mid X \mid \times \mid Y\mid) log(\mid X\mid \times \mid Y\mid)), where \mid X \mid and \mid Y \mid are the number of unique branches in the syntactic hierarchies of any two given HTML documents, respectively.</abstract></paper><paper><title>An XML Indexing Structure with Relative Region Coordinate</title><author><AuthorName>Dao Dinh Kha</AuthorName><institute><InstituteName>Nara Institute of Science and Technolog</InstituteName><country></country></institute></author><author><AuthorName>Masatoshi Yoshikawa</AuthorName><institute><InstituteName>Nara Institute of Science and Technolog</InstituteName><country></country></institute></author><author><AuthorName>Shunsuke Uemura</AuthorName><institute><InstituteName>Nara Institute of Science and Technolog</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: For most index structures for XML data proposed so far, update is a problem because XML element's coordinates are expressed by absolute values. Due to the structural relationship among elements in XML documents, we have to re-compute these absolute values if the content of source data is updated. The reconstruction requires update of large portion of index files, which causes a serious problem especially when XML data content is frequently updated. In this paper, we propose an indexing structure scheme based on the Relative Region Coordinate that can effectively deal with the update problem. The main idea is that we express the coordinate of an XML element based on the region of its parent element. We present an algorithm to construct a tree-structured index in which related coordinates are stored together. In consequence, our indexing scheme requires update of only a small portion of index file in case of updating.</abstract></paper><paper><title>Querying XML Documents Made Easy: Nearest Concept Queries</title><author><AuthorName>Albrecht Schmidt</AuthorName><institute><InstituteName>CW</InstituteName><country></country></institute></author><author><AuthorName>Martin Kersten</AuthorName><institute><InstituteName>CW</InstituteName><country></country></institute></author><author><AuthorName>Menzo Windhouwer</AuthorName><institute><InstituteName>CW</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Due to the ubiquity and popularity of XML, users of-ten are in the following situation: they want to query XML documents which contain potentially interesting information but they are unaware of the mark-up structure that is used. For example, it is easy to guess the contents of an XML bibliography file whereas the mark-up depends on the methodological, cultural and personal background of the author(s). Nonetheless, it is this hierarchical structure that forms the basis of XML query languages. In this paper we exploit the tree structure of XML documents to equip users with a powerful tool, the meet operator, that lets them query databases with whose content they are familiar, but without requiring knowledge of tags and hierarchies. Our approach is based on computing the lowest common ancestor of nodes in the XML syntax tree: e.g., given two strings, we are looking for nodes whose offspring contains these two strings. The novelty of this approach is that the result type is unknown at query formulation time and dependent on the database instance. If the two strings are an author's name and a year, mainly publications of the author in this year are returned. If the two strings are numbers the result mostly consists of publications that have the numbers as year or page numbers. Because the result type of a query is not specified by the user we refer to the lowest common ancestor as nearest concept. We also present a running example taken from the bibliography domain, and demonstrate that the operator can be implemented efficiently.</abstract></paper><paper><title>A Graph-Based Approach for Extracting Terminological Properties of Elements of XML Documents</title><author><AuthorName>Luigi Palopoli</AuthorName><institute><InstituteName>Universita della Calabri</InstituteName><country></country></institute></author><author><AuthorName>Giorgio Terracina</AuthorName><institute><InstituteName>Universita della Calabri</InstituteName><country></country></institute></author><author><AuthorName>Domenico Ursino</AuthorName><institute><InstituteName>Universita della Calabri</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: XML is rapidly becoming a standard for information exchange over the Web. Web providers and applications using XML for representing and exchanging their data make their information available in such a way that interoperability can be easily reached. However, in order to guarantee both the exchange of XML documents and the interoperability between information providers, it is often needed to single out semantic similarity properties relating concepts of different XML documents. This paper gives a contribution in this framework by proposing a technique for extracting synonymies and homonymies. The derivation technique is based on a rich conceptual model (called SDR-Network) which is used to represent concepts expressed in XML documents as well as the semantic relationships holding among them.</abstract></paper><paper><title>B+-Tree Indexes with Hybrid Row Identifiers in Oracle8i</title><author><AuthorName>Eugene Inseok Chong</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Souripriya Das</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Chuck Freiwald</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Jagannathan Srinivasan</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Aravind Yalamanchi</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Mahesh Jagannath</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Anh-Tuan Tran</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><author><AuthorName>Ramkumar Krishnan</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><year>2001</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Abstract: Most commercial database systems support B+-tree indexes using either 1) physical row identifiers, for example, DB2 or 2) logical row identifiers, for example, NonStop SQL. Physical row identifiers provide fast access to data. However, unlike logical row identifiers, they need to be updated whenever the row moves. This paper describes an alternate approach where hybrid row identifiers are used. A hybrid row identifier consists of two components: 1) a logical component, namely, the primary key of the base table row, and 2) a physical component, namely, the Database Block Address (DBA) of the row. By treating the DBA as a guess regarding where the row may be found, performance comparable to physical B+-tree indexes is attained for valid guess-DBAs. This scheme retains the logical index advantage of avoiding an immediate index update when the base table row moves. Instead, an online utility can be used to lazily fix the invalid guess-DBAs. This scheme has been used to implement B+-tree indexes for Oracle8i index-organi