Database Systems for Advanced Applications '97

The following sections are included:

• Preface

• Program Committee Chairs' Introduction

• Fifth International Conference on Database Systems for Advanced Applications

• Organizing Committee

• Program Committee

• Referees

• Table of Contents

In contrast to relational query processing, one of the most important extensions of query processing in object-oriented DBMSs (OODBMSs) is navigational access to objects. So far, optimization of this kind of access has been primarily supported by special access path structures or object clustering strategies. Parallelism, although an important topic in large relational systems, has not been explored comprehensively in OODBMSs. In order to evaluate parallel access strategies when collecting a set of objects, we present a cost model to estimate the necessary amount of page I/O. In contrast to others, our cost model covers parallel execution of navigational retrieval operations under a restricted number of available buffer frames. Finally, some measurements validate the cost model.

Vertical partitioning is a proven database design technique which increases the efficiency of query execution by reducing the irrelevant data accesses. In this paper, we develop a cost model to study the effectiveness of vertical partitioning in OODBs, in terms of reducing the number of disk accesses for executing a set of queries. Further, we compare and evaluate two different (namely, affinity-based, and cost-driven) partitioning approaches. We show that the cost-driven approach is more general and more effective in reducing number of irrelevant disk accesses accessed than the affinity-based approach.

We propose query optimization techniques that fully utilize the advantages of path indexes in object-oriented database systems. Although path indexes provide an efficient access to complex objects, little research has been done on query optimization that fully utilize path indexes. We first devise a generalized index intersection technique, adapted to the structure of the path index extended from conventional indexes, for utilizing multiple (path) indexes to access each class in a query. We then propose the query graph reduction algorithm that replaces the classes in the query graph with path index scans; we call the resultant query graph reduced query graph (RQG). We finally present the search algorithm that finds the least-cost evaluation plan from RQG based on a cost model. Proposed query optimization techniques enhance database performance by using path indexes instead of direct accesses to data in the evaluating queries.

This paper presents three broad classes of network architecture that support discovery of information sources. Relevant concepts such as query routing and the extraction, propagation, and retrieval of metadata are defined. Based on these concepts, different models of locating and querying relevant information sources are presented. Finally, we estimate several important characteristics of these models and classes as well as their expected scalability.

Keyword-based search services have become necessary tools for finding information resources on the Internet today. The rapid growth of information on the Internet renders centralized keyword index services incapable of collecting comprehensive resource meta-data in a timely manner. We argue that delegating the task of meta-data collection to local index servers is a more scalable approach. We propose a mechanism for integrating distributed autonomous index servers into a cooperative resource discovery system. Focusing on the retrieval effectiveness of the system, we propose a set of methods, called CVV-based methods, for ranking and selecting index servers with respect to a query, and merging the results returned by the index servers. Through experiments, we evaluate the effectiveness of the CVV-based methods, and compare our server ranking method with methods proposed by other researchers.

Paper proposes a method for automatic network map scaling. A map is composed of objects and links among objects. Scaling consists in synthesizing a map by keeping only "representative" objects according to user-defined conditions, links among "representative" objects can be calculated through a partial transitive closure computation.

To fully support distributed processing in any distributed system, it must be possible to perform remote executions. For maximum benefit, this should also be coupled with the movement of data and programs from sites other than those where the execution is to be performed. Such distributed processing requirements are considered in the context of a Virtual Enterprise which uses an Object-oriented Knowledge Base Management System (OOKBMS) to act not only as a trader, but also the repository for a global model and shared data. Here, the concept of objects causes us to reconsider remote execution and data movement as the more general problem of object migration. In this paper we identify, object migration consisting of the migration of three possible components: object definition, object instances, and object method executables and source. We describe in this paper an exhaustive list of thirteen execution and data location scenarios. The discussion in this paper on object method execution covers not only the migration of executable code between homogeneous systems, but also interpretive code, such as Java, and also compilable programs (source code). Given these considerations, this paper finishes with the definition for a migration protocol using KQML. These performatives provide the mechanisms to support a wide variety of migration policies and are shown to support the thirteen distributed execution operation scenarios.

In this paper we propose a new model for moving objects, aimed at handling video sequences in multimedia databases. The model integrates the representations of individual moving objects and the time-varying relationships between multiple moving objects in a scene. Several new query operators are defined within this model. Some examples illustrating the power of the model are provided.

Transactional workflows have been previously specified using commercially-available workflow management systems (WFMSs). WFMSs have facilitated this specification by providing task coordination and execution capabilities. However, these current WFMSs have limitations in terms of heterogeneous distributed system integration, non-proprietary cross-platform support, and flexible ACID property support. A key weakness is their lack of recovery support which is a critical requirement for most WFMSs.

This paper makes two contributions towards workflow management systems. First, CORBAflow (a CORBA-based architecture for transactional workflow management) is presented. Second, a minor modification to CORBA's Interface Definition Language (IDL) grammar is also presented. Through this modification compensating subtransactions in transactional workflows can be specified. A workflow example using Saga transactions is then presented which illustrates transactional workflow specification. This research shows how compensating subtransactions can be combined with CORBA's cross-platform support and heterogeneous system integration capability to resolve semantic failures in transactional workflows.

A graph model is presented to analyze the cost of a large join query in a uniprocessor environment. The information that is required to compute a join cost, such as cardinalities and tuple sizes of two join relations, is represented as graph parameters. All possible execution plans are representable in this graph. Each spanning tree of the graph stands for a query processing tree. On the basis of this graph, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods. Experiments show that the proposed algorithm is superior to the others under most circumstances.

In a previous paper [6], we introduced the notion of using machine learning techniques to solve the problem of query size estimation in database query optimisation. In this paper, we build on this work by describing a new generic algorithm to correct the training set of queries for our machine learning method in response to updates. The training set correction algorithm is not only useful in the context of our machine learning approach, but is also useful for improving existing query size estimation methods whose performance deteriorates in the presence of high update loads. A by-product of our correction algorithm is that training sets can be fixed-size, allowing the error-level to be set in advance. Experimental results show that our machine learning technique performs well (and better than alternative methods) after the correction algorithm is applied.

To make effective use of distributed systems acting together to form a virtual enterprise, global coordinated operations must be possible. Such operations may be mere queries or complex update operations. In this paper, we describe an existing system at the University of Florida which not only models a Virtual Enterprise using a common object-oriented semantic association model, but acts as a trader and repository for common information. The primary objective of this paper is to show how this existing system is being extended to handle complex global operations stated in the form of Object Query Language queries. These queries are then processed in a distributed manner, including any necessary object migrations. Problems addressed in this paper include: provision of support information in the meta-model, allocation of global object instance identifiers, issuing and coordination of subqueries to the legacy systems in the Virtual Enterprise, and the issuing and coordination of method executions.

Transformation-based optimizers that explore a search space exhaustively usually apply all possible transformation rules on each alternative, and stop when no new information is produced. In general, different sequences of transformation rules may end up deriving the same element. The optimizer must detect and discard these duplicate elements generated by multiple paths.

In this paper we consider two questions: How bad is the overhead of duplicate generation? And then, how can it be avoided? We use a restricted class of join reordering to illustrate the problem.

For the first question, our analysis shows that as queries get larger, the number of duplicates is several times that of the new elements. And even for small queries, duplicates are generated more often than new elements. For the second question, we describe a technique to avoid generating duplicates, based on keeping track of (a summary of) the derivation history of each element.

Documents consist of components such as sections, subsections and paragraphs. These components conform to hierarchical structures which can be explicitly encoded according to document representation standards such as SGML. The SCL (Simple Concordance Lists) query language provides a simple and effective way to express traditional boolean queries as well as queries specifying document structure in a database of structured documents such as SGML documents. This paper describes an indexing scheme which can support this query language and its implementation as a prototype. We describe how SCL queries are evaluated and show how query evaluation can be optimised. The performance results obtained show that structured queries at all levels of the document structure can be supported, and that our optimisation strategy can substantially reduce query processing costs.

The success of the World Wide Web is boosting the development of multimedia database systems and their integration into the internet. For the documents stored and exchanged in the Web there are many multimedia data formats differing in aspects such as resolution, sampling rate, and compression. Furthermore there is a large variety of Web browsers, the data formats they support, and their network access. Thus storage servers have to store and proxy servers have to transfer many different formats.

However, the data formats are not independent from each other but interrelated by conversion tools. There is a large number of alternatives for storage and proxy servers to store some formats or to transfer them via the network and to compute the remaining ones by applying conversion tools. To determine an optimal choice is a nontrivial optimization problem and is subject to changes of the parameters such as query profile, available disk storage, and network bandwidth. We examine the outlined optimization problem in the context of object-oriented databases and illustrate our approach by a practical real-world application.

Integration of heterogeneous information resources has been one of the most important issues in recent advanced application environments. In addition to conventional databases, structured documents have been recognized as important information resources recently. In this paper, we first present a data model named the NR/SD model as a basic data modeling framework for integration of structured documents and relational databases. Then, we discuss the query processing and optimization scheme for environments including structured document repositories and relational databases. The NR/SD model combines an abstract data type named the structured document type and the nested relational structures, and features operators named converters to dynamically convert structured documents into nested relational structures and vice versa. Therefore, we can manipulate information in either forms of structured documents and relations. This feature poses the following issues in query processing: (1) Utilization of the local query processing capability of the document repository and the relational database, and (2) Efficient manipulation of structured document data whose volume is potentially quite large. We discuss the query processing and optimization scheme mainly focusing on these issues.

This paper presents a persistent graph abstract data type which is suited to the implementation of repositories for CASE tools. It contains both deductive database and persistent graph representations of repositories for several CASE tools, in particular the entity-relationship-atttribute method for conceptual data modelling. It shows that while the deductive database approach is feasible, a PGADT implementation would be superior.

Existing work on demand-driven-based wireless environments has largely focused on energy-efficient caching strategies. While these schemes minimize the number of uplink requests (and hence conserve energy), they are still not adequate as clients must continue to monitor the broadcast for data that is not found in the cache or has been invalidated. Other work on disseminating data via periodic broadcasting of the data file has developed techniques that organize data to allow clients to selectively tune to the desired portion of the broadcast. Such schemes, unfortunately, cannot be applied to demand-driven-based context because demand-driven data cannot be predetermined. In this paper, we study the issue of selective tuning in a demand-driven-based environment. We propose and study three strategies that allow clients to repeatedly toggle between doze mode and active mode until the desired objects are obtained. One of the strategies is stateful-based in the sense that the server is aware of the schedule of doze-off/awake time determined by the clients. The other two strategies are stateless-based approaches where the clients' schedules of doze-off/awake time depend on cues broadcast by the server. We conducted a performance study and our results demonstrate that the proposed schemes are energy efficient without sacrificing on the average access times of object retrievals. Furthermore, our results show that none of the algorithms is superior in all cases.

Databases for software engineering environments (SEEs) store and manage the various software artifacts involved. Object oriented databases (OODBs) have been identified to be most suitable for meeting the needs of SEEs. To provide effective support, transaction models in these databases need to take into account specific characteristics of the long-duration tasks and uncertain activities in SEEs. In this paper we present a locking protocol that exploits the relationships among groups of users in SEEs to grant access for conflicting locks and achieve greater concurrency in long-lived SEE transactions. We also extend an existing semantic locking protocol for OODBs to incorporate our group-based locking protocol to obtain a comprehensive locking protocol for use in SEEs.

A more general incremental updating technique is developed for maintaining the association rules discovered in a database in the cases including insertion, deletion, and modification of transactions in the database. A previously proposed algorithm FUP can only handle the maintenance problem in the case of insertion. The proposed algorithm FUP₂ makes use of the previous mining result to cut down the cost of finding the new rules in an updated database. In the insertion only case, FUP₂ is equivalent to FUP In the deletion only case, FUP₂ is a complementary algorithm of FUP which is very efficient when the deleted transactions is a small part of the database, which is the most applicable case. In the general case, FUP₂ can efficiently update the discovered rules when new transactions are added to a transaction database, and obsolete transactions are removed from it. The proposed algorithm has been implemented and its performance is studied and compared with the best algorithms for mining association rules studied so far. The study shows that the new incremental algorithm is significantly faster than the traditional approach of mining the whole updated database.

Since the requirement of data warehouse is increasing, it is necessary to develop efficient mechanisms for data warehouses incorporating various kinds of database systems. Essentially, materialized views are used for data warehouses and various methods for relational databases have been developed. In this paper, we will first discuss a method to realize materialized views for object-oriented databases (OOBDs) using deputy objects. Since materialized views require to generate duplication of data, improvement of efficiency for update operations in important. We will handle this problem by the following two approaches: (1) reduction of duplicates by considering inheritance property, (2) speed-up update propagation by considering communication delay. Our approach allows objects to be updated at data warehouse sides. If a data object is updated, the effect of update propagation in the same data warehouse must be completed as soon as possible. If update information is transmitted to the original OODB and the induced update operations are transmitted from the OODB to the data warehouse, the delay required for update completion will be large due to the communication delay between the date warehouse and the OODB systems. We will try to avoid communication delays for update propagation in the same data warehouse.

We propose an information organizer for effective clustering and similarity-based retrieval of text and video data. Instead of giving keywords or authoring them, we use a vector space model and DCT image coding in order to extract characteristics of data. Data are clustered by Kohonen's self-organizing map, and the result is visualized in a 3D form. By this, similarity-based retrieval is achieved. We implemented a prototype system and report experimental results. We consider that our system effectively promotes reuse of distributed text and image data assets.

String hashing is a fundamental operation, used in countless applications where fast access to distinct strings is required. In this paper we describe a class of string hashing functions and explore its performance. In particular, using experiments with both small sets of keys and a large key set from a text database, we show that it is possible to achieve performance close to that theoretically predicted for hashing functions. We also consider criteria for choosing a hashing function and use them to compare our class of functions to other methods for string hashing. These results show that our class of hashing functions is reliable and efficient and is therefore an appropriate choice for general-purpose hashing.

Selection criteria in OODB refer to object properties as well as to type membership. The latter stimulated research on type hierarchy indexing, i.e, fast access to object sets based on type membership criteria.

A recent proposal in this context is the multikey type index. It is based on a symmetrical multikey search structure with n dimensions for n indexed object properties and one additional dimension for type membership. The domain of this type dimension is the type set of the indexed object. However, an important prerequisite for an efficient implementation of a multikey type index is an optimal linearization of the type set.

In this paper we show in how far the linearization affects the performance of the multikey type index and present the construction of optimal linearizations which is straightforward only in case of single inheritance. In case of multiple inheritance a recursive divide-and-conquer solution produces all existing optimal linearizations for a given type hierarchy.

The main contribution of this paper is a detailed outline of the corresponding algorithm for multiple inheritance type hierarchies. By using this algorithm, the multikey type index is an interesting alternative to the traditional approaches for type hierarchy indexing, which are almost exclusively based on B⁺-tree derivates.

Intra-query parallelism is important for achieving high performance in parallel processing environment. For processing a signature file in parallel, an effective declustering algorithm that must avoid data skew and execution skew is needed. The Linear Code Decomposition Method(LCDM) that is used for the Hamming filter may give a good performance, but it fails to evenly decluster a signature file when data is skewed. In addition, it has other problems such as limited scalability and non-determinism. In this paper we propose a new signature file declustering algorithm, called MIN-entropy that overcomes those problems in the LCDM. The MIN-entropy declusters a signature file based on a measure of execution load uniformity, called signature entropy, that is derived from the previously declustered signatures. Since the MIN-entropy uses dynamic information such as accumulated signatures, it provides high performance for a variety of workload and configurations. We show through the simulation experiments that the MIN-entropy outperforms the LCDM under various data distributions.

In order to integrate autonomous taxonomy databases in the presence of semantic heterogeneity, we developed and evaluated a new integration algorithm over international computer networks. Whole taxonomy databases in the real applications are encoded in the relational model. First, the algorithm requires users to assign priority according to order of belief for each one of the accessible taxonomy databases. Integration is achieved by increasing the kernel database, selected by the algorithm as the one with the highest priority among the databases. Complex problems are included to recognize consistent parts that can be incrementally added to the kernel databases in the remainder of the accessible taxonomy databases through the use of tree structures. The algorithm with relations operators, was proposed after considering both structural and cooperative constraints useful in managing single and multiple databases. In addition, we present a taxonomy database system including the useful algorithm. The system is also accessible from remote users through WWW (World-Wide Web) and is implemented in SQL programming and CGI (Common Gateway Interface) scripts of WWW.

Large data volumes, flexible drill-down analysis and short query response times, which are predominant characteristics of Scientific and Statistical Data Base (SSDB) applications, require new optimization techniques as compared to traditional DBMS. This paper describes formally an optimization approach in the SSDB domain which is based on the re-use of materialized results of former queries to process aggregate queries along a classification hierarchy. The description of the approach is embedded in the CROSS-DB model (which stands for Classification-oriented, Redundancy-based Optimization of Scientific and Statistical Data-Bases). It will be shown that the approach taken can improve query response time by orders of magnitude while adding tolerable storage and maintenance overhead to the database.

The "Cube-Query-Language" (CQL) is a new query language for flexible access to Multidimensional Database Systems. CQL provides a high level user interface for specifying queries in the context of multidimensional data analysis. The multidimensional view is widely accepted for typical decision support requirements like "Online Analytical Processing". CQL directly supports this view and circumvents the problems of formulating multiple groupby's and equijoins in a typical SQL-notation. Furthermore, in comparison to currently available OLAP-solutions, CQL provides a SQL like query interface, making it easy for an experienced SQL-programmer, to formulate decision support queries efficiently.

The paper details the two-step query processing found in the CQL approach: "data querying" and "data presentation". This description of the query language design is accompanied by a lot of examples, stemming from a joint research project with our industrial partner, thus showing the expressive power and flexibility of the query language design.

Distributed transaction processing requires many message exchanges over the networks, which can hinder the timely completion. It is necessary to reduce the number of intersite communications for real-time processing. To ensure the timeliness of transactions, the time constraints are specified and reflected in the transaction processing time. In addition, it must guarantee the correct completion of the transactions. So, we must satisfy both correct completion and timely completion in a distributed real-time transaction processing environment. In this paper, we suggest new language constructs for the distributed real-time transactions. The language constructs consists of three features as follows: the specification of the time constraints, the asynchronous remote processing, and handling the missed time constraints. These features will reduce the number of message exchanging, reflects the time constraints for the timeliness of transactions, and ensure the correctness of distributed transactions.

We demonstrate how a purely declarative language, with the help of strict typing, precise moding, and determinism declarations, can be used to concisely and declaratively express database transactions, including updates. We have begun incorporating transactions into the Aditi deductive database system using an extended form of Mercury as the database programming and query language.

Upon executing an update operation on a database, once the integrity constraints that are specified on the database are violated, the operation should be rejected. For preserving the atomicity of update operations of the SQL level, we propose the concept of mini-savepoint. A mini-savepoint is set up by the system before each of the update operations. Upon failure of the update operation, the transaction and the database are restored to the state that they have had right before the operation is executed by restoring cursors, nullifiying the information of files that are created and/or destroyed during the execution of the operation, undoing all the undoable logs that are recorded during the execution of the operation, releasing all the lock entries that are held during the execution of the operation and removing marks for the mini-savepoint. Upon successful completion of the update operation, the mini-savepoint is earsed by moving all the lock entries that are held during the execution of the operation to the latest savepoint and also by removing marks for the mini-savepoint. For the explanation and implementation details of the mini-savepoint that is implemented in BADA-II, the works that are done by the lock manager, log manager, buffer manager, cursor manager, file manager and transaction manager are given in detail.

Normalization in object-oriented design is much different from that in relational database design. Not only are the conceptual data model of object-oriented (o-o) models integrating richer structuring capabilities than that of relational models, but also the dependency constraints, attribute ranges and access paths in o-o models are more complex than that in relational models. In o-o models, inheritance semantics is expressed mainly by class hierarchy, and it is important to ensure and maintain an appropriate class hierarchy. In this paper, we propose a Boolean algebra approach for class hierarchy normalization. A class hierarchy normal form(CHNF) and an indexing model for class hierarchy are defined respectively. Some methods and algorithms, such as transformation from a non-CHNF class hierarchy to a CHNF one, are given.

In this paper, we propose a new security enforcement mechanism and demonstrate how this mechanism can enforce policies for both mandatory access control (MAC) and discretionary access control (DAC) in an object database system. Each class may have a security method that can block messages that leave instances of the class, and can block messages directed to instances of the class. Each superclass controls the invocation of security methods in its subclasses. A subclass cannot override the security methods in its superclasses, but the subclass can extend those security methods. The mandatory access control policy is enforced by a single security method along with other methods in the highest class in the class hierarchy. The discretionary access control policy is enforced by a single security method along with other methods a subclass of the highest class.

Object-oriented database management systems (OODBMS) are especially suited to model complex and highly dynamic application domains. In this paper, we propose a schema versioning approach which supports the dynamic change of an object-oriented database schema while it is used by running applications. Our mechanism allows to have applications working with different schema versions on top of the same single database in parallel. A flexible and parameterized approach is presented to make instances of the database accessible in different versions of a schema. In this way, it is no longer required to update all database applications at once whenever the schema is changed. Instead, the adaptation of old applications to a new schema version can be done later if this is considered advantageous.

Compared with conventional query languages, more factors should be considered in developing multimedia query languages because multimedia information is composed of large unformatted media data and also has multiple complex structures such as hyperlink networks and spatial/temporal layout structures, as well as logical structures. In this paper, we propose an object-oriented multimedia query language for handling multi-structure information. The query language is specified in compliance with the SQL3 standard, and the type hierarchy and query expressions are enriched to support various query types (i.e. attribute, content, structure, hyperlink queries) and all the structures (i.e. logical, spatial/temporal layout, hyperlink network structures).

This paper presents an approach to extend object-oriented data models, in which versions of an object are allowed to appear at different levels of an inheritance hierarchy, in contrast to the known approaches where they are admitted only at one level. This approach allows the design and instantiation of objects to become very natural, starting with the design of an object in a class and refining it, adding properties to the subclasses. Versions of objects can be defined in a subclass, having ascendant versions/objects associated to the superclasses. The paper also discusses how the extended model can be used to model engineering applications, fulfilling their requirements. The application is the STAR framework, which implements an innovative and flexible data model that allows the user to define an object schema for each design object. Design alternatives and views can be created during the design process and are represented in the object schema. Versioning appears in the STAR model not only for the real design data, but also for alternatives and views in the object schema. This requirement is not naturally modeled by the existing version models in object-oriented databases.

This paper presents a unified approach to modeling and implementing temporal multimedia objects. The approach is based on both the object-orientation and the time interval logic investigated by Allen [Alle83]. We regard every temporal multimedia data as a time interval. Then, by introducing null time-intervals, it is shown that every temporal relationship is represented using only the equals and the meets relationship. Accordingly, to manipulate heterogeneous temporal multimedia data in a unified manner, normal forms of composite temporal multimedia objects are introduced. The normal forms allow us to implement a multimedia player, where two synchronization schemes are necessary and sufficient to play back any composite temporal object; which are the individual and the start synchronization scheme. These schemes are implemented and evaluation results are shown in this paper. In general, audio-visual data are huge. We adopted MPEG-1 standard to compress video data. A suitable storage structure for MPEG-1 video data is also shown with a class hierarchy.

The bitemporal conceptual data model proposed for handling time within the framework of relational data model can be effectively represented using valid-time and transaction-time intervals as time-stamps on tuples. We observe that in many real-world applications, valid-time interval for a fact is not known completely while entering the fact in a temporal database. The model provides 'open' interval, from some valid time v to 'forever' for time-stamping such facts. However, updating temporal validity of such facts, which invariably will be required, is not handled efficiently by this representation. We propose an alternative representation which can reduce storage cost by upto 50% and which also results in less I/O during updates. We define the conventional and temporal algebra operations for this representation, and also add a few useful operators for processing open intervals. We propose extensions to temporal SQL to support open-ended valid time intervals.

A wide range of database applications manage time-varying data, and it is well-known that querying and correctly updating time-varying data is difficult and error-prone when using standard SQL. Temporal extensions of SQL offer substantial benefits over SQL when managing time-varying data.

The topic of this paper is the effective implementation of temporally extended SQL's. Traditionally, it has been assumed that a temporal DBMS must be built from scratch, utilizing new technologies for storage, indexing, query optimization, concurrency control, and recovery. In contrast, this paper explores the concepts and techniques involved in implementing a temporally enhanced SQL while maximally reusing the facilities of an existing SQL implementation. The topics covered span the choice of an adequate timestamp domain that includes the time variable "NOW," a comparison of query processing architectures, and transaction processing, the latter including how to ensure ACID properties and assign timestamps to updates.

We present a temporal object data model, query language and system that support temporal database applications. We then show how equivalent temporal constructs and operations could be provided in existing object-oriented database management systems (OODBMS) and describe how we did this in the O₂ system. A comparison of the two resulting systems highlights the current limitations to the notions of extensibility supported in existing OODBMS.

Outerjoin is one of the most frequently used operators for integrating semantically related entity types in a multidatabase environment. Efficient view maintenance involving outerjoin is a challenging problem. Unfortunately, most of the existing view maintenance algorithms only consider the views defined by select-project-join (known as SPJ) queries. Once outerjoin is used as the integration operator to create a view, those existing algorithms may fail in view maintenance. In this paper, we first expose an abnormal phenomenon (we called it dangling tuple problem) of view maintenance when outerjoin and data inconsistency are involved. We then propose a new view maintenance mechanism that can handle views involving outerjoin, regular join, and data inconsistency. It can also handle maintenance anomaly [19]. Moreover, our maintenance mechanism minimizes the number of the queries that need to be sent to the local database systems for view maintenance, which is an effective way to make the multidatabase system more efficient.

Although significant progress has been made in developing multidatabase systems that integrate component databases containing crisp data, little has been reported on integrating fuzzy databases in such systems. In this paper, we investigate the problem of integrating fuzzy relational databases in a multidatabase system. We identify new types of conflicts that may occur in schemas and data due to the inclusion of fuzzy relational databases. We propose a methodology that resolves these new types of conflicts in a procedural manner. In addition, the methodology puts the resolution of these new conflicts into the context of the resolution of other types of conflicts. A fuzzy–probabilistic data model is used to facilitate the integration.

The usual approaches to integrate schemata with class hierarchies are based on "upward inheritance". Thereby, restructuring schemata during schema integration is not possible. We present an algorithm for deriving a completely new class hierarchy from given object-oriented schemata. Our approach is based on an extensional and intension decomposition which transforms the schemata to be integrated into an intermediate representation. Based on that representation our algorithm composes an integrated schema with a new class hierarchy. The algorithm which we discuss in full detail is part of a more comprehensive integration framework for federated databases design.

It has been known that using different representations of a query retrieves different sets of documents. Recent work suggests that significant improvement in retrieval performance can be achieved by combining multiple representations of an information need. In this paper, we first investigate a fully automatic way of generating multiple query representations for a given information problem. We produce multiple query vectors by expanding an initial query vector with various relevance feedback methods. We then describe the effect of combining the multiple query vectors on retrieval effectiveness. Experimental results show that significant improvements can be obtained by the combination of multiple query vectors expanded with different relevance feedback methods.

With the growth of digital libraries and electronic publishing, many structured document sources are appearing and their effective mediation is an important research topic. In this paper, we propose a wrapping architecture for externally maintained structured document sources. Our wrapping target is information retrieval systems (IRSs) that provide access to structured documents. We describe a wrapper construction method for such IRSs with limited functionality. A constructed wrapper enhances retrieval facilities of the underlying IRS and provides an object database view to the mediator. We focus on determining whether the underlying IRS can support a given query. Then we discuss some research issues related to our wrapping architecture.

To support future digital library systems which draw information from different sources on the internet, we have to provide integrated queries to pre-existing database servers which contain structured, semi-structured and unstructured data. In this paper, we specifically examine the problem of querying both existing structured relational databases and bibliographic databases. By adopting the well-accepted Z39.50 standard protocol to access bibliographic databases in different legacy library systems, we have developed an extended SQL model, known as HarpSQL, to support integrated queries to both SQL databases and bibliographic databases. Using HarpSQL, one can not only query bibliographic databases in an SQL manner, but also perform join(s) between SQL and bibliographic databases. A distributed query processor supporting HarpSQL queries has been developed. We will present our query processing strategy that is based on client-server interaction model between the distributed query processor and the various remote database servers.

Efficient condition evaluation is crucial for high performance of active database systems. Most previous works used the incremental evaluation techniques, whose operations are relatively expensive due to computing exact values of the condition expression. In this paper we propose a new filtering technique that effectively indentifies false condition in an early stage of condition monitoring. Since the results of condition evaluation tend to be false in most practical cases, an efficient filtering method can highly facilitate fast condition evaluation. The proposed filtering technique is developed based on the new perspective of database state and database operations, i.e., a vector space model. We first present a vector representation of database state, database operations, and complex condition expressions. Then, we propose an optimization method based on the properties of a vector space. Our proposed method determines the truth value of the rule conditions only with the delta vectors maintained in main memory. We compare our method with a typical incremental evaluation method and show that the proposed method can give a significant performance enhancement.

With the proliferation of multimedia applications, even secondary storage systems do not have sufficient storage capacity to meet the demand, only tertiary storage systems can provide the necessary storage economically. We have been examining the feasibility of "scalable tape archiver" where any number of commodity 8mm based robotics can be connected to allow the development of arbitrary sized archives economically. 8mm tape based robotics which can mechanically exchange cassette tapes through a special transportation port were designed and built. By migrating the frequently accessed, HOT, cassettes evenly amongst the archivers in both the foreground and background, we can improve the performance of the system significantly compared with systems without the ability to migrate cassettes. In this paper, we analyze the migration activities on scalable tape archiver. When heat imbalance is detected, migration activities are invoked, which we examined in detail through simulations using the parameters taken from the real archivers. The case where a file is striped over several tapes is also carefully examined. In addition, in our system, even when some of the drives fail, the system can continue unaffected by dynamically migrating the cassettes to the archivers which have working drives. We examined the migration activities when drive failure occurs. Our simulation study clarified the effectiveness of the Scalable tape archiver.

This paper presents the implementation and performance evaluation of the Bucket Flattening Omega Network of the SDC-II, the Super Database Computer II. The SDC-II is a highly parallel relational database server, which consists of eight data processing modules interconnected by two networks. Parallelism in the parallel relational database processing on the shared nothing architecture would suffer from skewed data distribution and collisions in the interconnection networks. The network of the SDC-II was designed to offer an architectural support of the Bucket Spreading hash join algorithm, which enables the system to have linear performance scalability even with skewed data distributions. The additional functionality introduced into the network can generate a flat bucket distribution, which is essential to the algorithm, while providing almost conflict free routing. Each switching unit of the network is implemented on an FPGA chip, and its performance is evaluated to compare with an implementation without hardware support. The evaluation results show that the effective bandwidth of the latter implementation degrades to almost half of the ideal bandwidth, while little degradation is observed with the hardware support during all-to-all communication phase of the algorithm.

In a video-on-demand (VOD) environment, batching of requests is often applied to reduce the I/O demand and increase the availability of VOD services. This scheme, however, unfairly forces first comers to wait for subscribers arriving late at the batch. Some of these victims may become impatient and decide to renege. To address this issue, we introduce a chaining technique which allows a client station being served to forward its video data to other client stations, which requested the same video, at a slightly later time. The forwarding of data is done using the same store-and-forward mechanism of the multicast facility used in batching. With this new feature, requests arriving at a chain can be served immediately; yet they are allowed to share a single video stream. Thus, chaining enjoys the benefit of batching without its side effect of causing long access latencies. By combining batching and chaining, we also design a scheme called Virtual Batching. It extends the standard chaining mechanism to allow a client station on a chain to multicast video data to other client stations which are admitted as a batch. Our simulation results indicate that this hybrid approach offers significant performance improvement.

To support large scale video-on-demand services, video storage servers must exploit tertiary storage systems for them to be cost effective. In this paper, we study two aspects that should be considered in designing a video storage server with hierarchical storage. First, we propose a new admission control policy to determine when a request should be admitted to the tertiary storage component. A novel feature of the proposed algorithm is that it is adaptive and robust to the system load. Requests may be admitted without sacrificing the quality of service even when their bandwidth requirements are not met. Second, we study several disk management algorithms for managing the disk space that is assigned as cache for the videos stored in the tertiary storage. We conducted a simulation study and our results show the effectiveness of the proposed techniques in terms of throughput and average waiting time.

Although modification operations on multimedia data such as insertion and/or deletion of video clips are rare, they may cause significant degradation of disk I/O performance in disk-array-based video servers. This is because many existing disk-array-based video servers consider only video playback at normal speed and retrieval-oriented VCR-like operations such as fast-forward and rewind without considering relocation of video data. Most conventional video servers provide optimal performance using static placement of video data on multiple disks. In this paper, we propose a method called 'SRM (Segment Relocation Method)' which provides uniform load-balance of disks regardless of the dynamic modification of stored video objects. For modification operations, the segments belonging to the corresponding 'round' of disk placement are relocated so that the system guarantees uniform load-balance of multiple disks in all rounds. To justify the significance of the relocation scheme, we evaluate and compare the cost of retrieval in terms of the required buffer size and the number of admitted users.

This paper explains our approach for optimizing the execution of object-oriented database transactions. We provide for parallel execution of methods inside atomic transactions. Our approach enhances parallel method execution without user-defined control structures. Optimization is based on method compatibility which is automatically determined during the method compilation phase. Optimized execution plans are efficiently built when transactions are compiled. An execution plan is then used for generating new transaction code where compatible methods are scheduled for parallel execution.

Workflow processes involve the coordinated execution of tasks performed by (local or remote) workflow resources (e.g., a person, a computer-based application, a printer). Workflow resource management is concerned with keeping track of resource status and assigning available resources to workflow tasks. Traditional approaches either manage distributed resources globally at a central site incurring huge overhead to keep track of resource status, or manage resources locally resulting in long delays at run time resource assignment. In this paper, we describe a distributed resource management approach that addresses above problems. We introduce the concept of two-step resource assignment. Instead of doing resource assignment in one step either at a central site (in global management approach), or at remote sites (in local management approach), the proposed approach first checks at central site the availability of resource groups, and then selects at remote sites specific resources from the group. A resource group is a group of resources that all can perform certain tasks. It is much easier to keep track of the status of resource groups (e.g., at least some printers are available at a site) than that of individual resources. In the paper, we discuss specification of resource group and their relationships to individual resources. We also discuss propagation of individual resource status to resource groups at remote sites. We describe such an implementation in the context of HP OpenPM workflow management system.

A multidatabase system (MDBS) is a facility that allows users or applications to access data located in multiple local database systems (LDBSs), each of which is autonomously operated. Several practical MDBS concurrency control schemes have been proposed whilst maintaining global consistency without compromising local autonomy. However, they could degrade either local concurrency of local transactions or global concurrency of global transactions for the purpose of ensuring the global serializability. In this paper, we propose a new ticket-based global concurrency control scheme that employs multiple tickets at each site. The basic idea is that, with proper consideration of the potential cyclic global serialization orders, subtransactions with the possibility of the local indirect conflicts must access the same ticket at their sites, otherwise they are allowed to access the different tickets. This scheme alleviates the blockage on local resources, and, as a result, increases both global concurrency and local concurrency, whilst preserving the local autonomy.

The following sections are included:

• Author Index