Wen-Syan LI Yi-Leh WU Junho SHIM Kyoji HIRATA Sougata MUKHERJEA Divyakant AGRAWAL Yoshinori HARA Reiko ITO Yutaka KIMURA Kazuyuki SHIMAZU Yukiyoshi SAITO
The Web is a collection of multimedia documents in the form of HTML pages connected through hyperlinks. Unlike most search engines, which focus on information retrieval based on keywords, WebDB aims at supporting database-like comprehensive query functionalities as well navigation, and document generation functionalities with customizability. To support hypermedia database functionalities, we augment the traditional concepts of tables in relational databases and classes in object-oriented databases with notions of document formats and navigation. We design WQL (Web Query Language) as an HTML document manipulation language. WQL language statements contain two parts: SELECT. . . FROM. . . WHERE clauses for specifying retrieval of data contents from hypermedia databases and CREATE. . . AS. . . clauses for specifying the output HTML format and navigation of the query results. This paper presents the architecture of WebDB and its functionalities. The extension to SQL for hypermedia document manipulation, query, and navigation and implementation on NEC PERCIO OODBMS are described in detail.
Hideo MATSUDA Takashi IMAI Michio NAKANISHI Akihiro HASHIMOTO
In this paper, we propose a method for querying heterogeneous molecular biology databases. Since molecular biology data are distributed into multiple databases that represent different biological domains, it is highly desirable to integrate data together with the correlations between the domains. However, since the total amount of such databases is very large and the data contained are frequently updated, it is difficult to maintain the integration of the entire contents of the databases. Thus, we propose a method for dynamic integration based on user demand, which is expressed with an OQL-based query language. By restricting search space according to user demand, the cost of integration can be reduced considerably. Multiple databases also exhibit much heterogeneity, such as semantic mismatching between the database schemas. For example, many databases employ their own independent terminology. For this reason, it is usually required that the task for integrating data based on a user demand should be carried out transitively; first search each database for data that satisfy the demand, then repeatedly retrieve other data that match the previously found data across every database. To cope with this issue, we introduce two types of agents; a database agent and a user agent, which reside at each database and at a user, respectively. The integration task is performed by the agents; user agents generate demands for retrieving data based on the previous search results by database agents, and database agents search their databases for data that satisfy the demands received from the user agents. We have developed a prototype system on a network of workstations. The system integrates four databases; GenBank (a DNA nucleotide database), SWISS-PROT, PIR (protein amino-acid sequence databases), and PDB (a protein three-dimensional structure database). Although the sizes of GenBank and PDB are each over one billion bytes, the system achieved good performance in searching such very large heterogeneous databases.
Toshiyuki AMAGASA Masayoshi ARITSUGI Yoshinari KANAMORI
This paper describes a way of implementing a conceptual model for temporal data on a commercial object database system. The implemented version is provided as a class library. The library enables applications to handle temporal data. Any application can employ the library because it does not depend on specific applications. Furthermore, we propose an enhanced version of Time Index. The index efficiently processes event queries in particular. These queries search time intervals in which given events are all valid. We also investigate the effectiveness of the enhanced Time Index.
Masatoshi ARIKAWA Shinji SHIMOJO Akira AMANO Kaori MAEDA Reiji AIBARA Kouji NISHIMURA Kaduo HIRAKI Kazutoshi FUJIKAWA
This paper proposes a new framework of managing virtual spaces based on spatial databases as an extension of VRML-based systems. The framework is suitable for treating continuous virtual spaces and for managing the quality of service (QoS) of the virtual spaces depending on user's operations and situations of computer resources. Levels of detail (LoD) of 3D objects is the most important rule for rendering scenes dynamically while managing the QoS. This paper describes a method of managing the QoS depending on the LoD in the form of spatial queries. An advantage of the framework is that spatial databases can incrementally construct virtual spaces in clients using differential descriptions based on VRML, that is, DVRML, proposed in this paper. Dynamic spatial data such as avatar's movement and real-time multimedia data such as videos should be shared by all participants in a virtual space in real time. Our framework can also handle dynamic spatial data by means of real-time updating of some spatial objects in spatial databases as well as static spatial data. We developed some experimental applications based on the framework in order to prove that it is feasible for networked virtual spaces with video components.
The goal of this paper is to present algorithms for creating an optimized query plan for retrieving maximum information from multiple relations, using outerjoins. Especially we focus on conjunctive queries in the presence of predicates and foreign functions. We show first with examples that retrieving maximum information by integrating multiple relations requires outerjoin operators. The outerjoin is essential to prevent information loss that would be caused by the inner join. We also show that predicates and foreign functions are useful to mediate the discrepancy among the relations and to create arbitrary views. Outerjoins and foreign functions, together with predicates, make it difficult to create query processing plans since they impose restrictions on the order of query processing. The rest of this paper describes algorithms for creating such query processing plans for conjunctive queries expressed in extended Datalog. First, we show simple algorithms for creating query plans with outerjoins, but without predicates and foreign functions. We use the hypergraph representation of the relations to explain an optimized algorithm. Then, we show a more complex algorithm that works for query plans with predicates and foreign functions. In our algorithm, we create an initial expression graph whose nodes represent query processing units, including outerjoin, predicate and foreign function operators. Then, we convert the initial expression graph into an executable, optimized expression tree. This algorithm is implemented and deployed in a mediation system that integrates heterogeneous information sources.
Development of large-scale software is usually conducted through a project to unite a work force. In addition, no matter what kind of life cycle model is employed, a development plan is required for a software development project in order for the united work force to function effectively. For the project to be successful, it is also necessary to set management objectives based on this plan and confirm that they are achieved. This method is considered to be effective, but actually making a software development project and following the achievement of the management objectives at each step is not easy because predicting the necessary work amount and risks that the project involves is difficult in software development. Therefore, it is necessary to develop a system to support software project management so that the project manager can manage the entire project and the work load is reduced. This paper proposes a meta-model of work structure of software development projects for project management by using an object-oriented database with constraints as well as a framework for software project management systems based on this meta-model. Also proven, through an example of a system that analyzes repercussions on progress of a software development project, is that the meta-model and framework are effective in software project management.
Shuichiro YAMAMOTO Ryuji KAWASAKI Toshihiro MOTODA Koji TOKUMARU
There is increasing demand for corporate information systems that have a simple human interface and are easy to access via WWW browsers. This paper proposes WebBASE, which integrates the WWW and relational databases. Experimental evaluation shows that WebBASE offers superior performance compared to existing products. Field studies of actual WebBASE applications show that it can improve the productivity of software developers for intranet application development.
Tae-Jong SON Kyu-Young WHANG Won-Young KIM Il-Yeol SONG
Many object-oriented database systems have used the notion of implicit authorization to avoid the overhead caused by explicitly storing all authorizations for each object. In implicit authorization, it is very important to detect efficiently conflicts between existing authorizations and new authorizations to be added. In this article we propose a conflict detection mechanism in the OODBMSs using implicit authorization with the notion of intention type authorization. When we grant an authorization on a node n in the database granularity hierarchy, the existing method is inefficient in determining the conflicts since it needs to examine all authorizations on the descendants of the node n. In contrast, our mechanism has the advantage of detecting the conflicts at the node n where an explicit authorization is to be granted without examining any authorizations below the node n. Thus, the proposed mechanism can detect a conflict with the average time complexity of O(d), which is smaller than O(md) of existing methods, where m is the number of children nodes at an arbitrary level and d is the difference of levels between the node with an existing explicit authorization and the higher node where an explicit authorization is to be granted. We also show that the additional storage overhead of storing all authorizations is negligible when compared with the total number of all explicit authorizations.
Dongwook KIM Myoung Ho KIM Yoon Joon LEE
Complex rule conditions are commonly required to describe complicated business semantics. In these cases, 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 the processing based on the exact calculation of the condition expression. In this paper we propose a new filtering technique that effectively identifies 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 vector representations of database states, database operations, and complex condition expressions. Then, we propose a filtering method based on the properties of a vector space, called the sphere containment test. 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.
Akiko NAKANIWA Hiroyuki EBARA Hiromi OKADA
In this paper, we study the optimal allocation of multimedia files in distributed network systems. In these systems, the files are shared by users connected with different servers geographically separated, and each file must be stored in at least one of servers. Users can access any files stored in any servers connected with high-speed communication networks. Copies of the files accessed frequently are to be stored in several servers that have databases. So, it is one of the most important problems how to assign the files to servers in view of costs and delays. Considering these problems in heterogeneous network environments, we present a new system model that covers wide range of multimedia network applications like VOD, CALS, and so on. In these systems, it is obvious that there is trading-off relationship between costs and delays. Our objective is to find the optimal file allocation such that the total cost is minimized subject to the total delay. We introduce a 0-1 integer programming formulation for the optimization problem, and find the optimal file allocation by solving these formulae.
Toshiyuki MORITA Yasunori ISHIHARA Hiroyuki SEKI Minoru ITO
Access control is a key technology for providing data security in database management systems (DBMSs). Recently, various authorization models for object-oriented databases (OODBs) have been proposed since authorization models for relational databases are insufficient for OODBs because of the characteristics of OODBs, such as class hierarchies, inheritance, and encapsulation. Generally, an authorization is modeled as a set of rights, where a right consists of at least three components s, o, t and means that subject s is authorized to perform operation t on object o. In specifying authorizations implicitly, inference rules are useful for deriving rights along the class hierarchies on subjects, objects, and operations. An access request req=(s,o,t) is permitted if a right corresponding to req is given explicitly or implicitly. In this paper, we define an authorization model independent of any specific database schemas and authorization policies, and also define an authorization specification language which is powerful enough to specify authorization policies proposed in the literature. Furthermore, we propose an efficient access control method for an authorization specified by the proposed language, and evaluate the proposed method by simulation.
Jiahong WANG Jie LI Hisao KAMEDA
Parallel Transaction Processing (TP) systems have great potential to serve the ever-increasing demands for high transaction processing rate. This potential, however, may not be reached due to the data contention and the widely-used two-phase locking (2PL) Concurrency Control (CC) method. In this paper, a distributed locking-based CC policy called LWDC (Local Wait-Depth Control) was proposed for dealing with this problem for the shared-nothing parallel TP system. On the basis of the LWDC policy, an algorithm called LWDCk was designed. Using simulation LWDCk was compared with the 2PL and the base-line Distributed Wait-Depth Limited (DWDL) CC methods. Simulation studies show that the new algorithm offers better system performance than those compared.
Toru MURASE Masahiko TSUKAMOTO Shojiro NISHIO
In recent years, the rapid advancements of wireless communication technology and computer down-sizing technology have enabled users to utilize computing resources anywhere in the computer network. New applications constructed on the mobile database system are becoming popular. However, the current database systems do not provide special facilities for specific update operations in a mobile computing environment. Moreover, due to the lack of a common data handling method and a mutual communication mechanism, varieties in implementations may cause applications to be incompatible with each other. In this paper, we take up the issue of data handling, in a mobile computing environment, and propose an active mobile database system (AMDS) to solve this issue. First, we review the difficulties of dynamic update of databases in a mobile computing environment, and provide a basic concept of AMDS as a solution for these difficulties. In order to construct an AMDS, we focus on asynchronous events such as the appearance and disappearance of a mobile computer in a wireless communication cell. Then we provide a facility to specify the behavior of each system in Event-Condition-Action(ECA) rules in the same way as normal active database systems. Moreover, we show the architecture and the design of our implementation of AMDS. And, finally AMDS can be easily implemented as a common database infrastructure and work well on heterogeneous systems through indoor experiments.
Masayoshi ARITSUGI Kan YAMAMOTO Akifumi MAKINOUCHI
When a set of objects is shared among several applications, multiple implementations for the set are required in order to suit each application as much as possible. Furthermore, if a set of objects could have multiple implementations, the following issues arise: (1) how to select the best implementation when processing queries on the set, and (2) how to propagate updates on an implementation of the set to the others. In this paper we propose a mechanism of multiple implementations for a set, and also give a solution for the latter issue. In the proposal a set can be of multiple types, and each of the types corresponds to an implementation already contained within the set. Update propagation can be achieved by a rewriting technique at compilation time. We also present a performance study in which the feasibility and effectiveness of our proposal were examined.
Shin-Mu TSENG Y. H. CHIN Wei-Pang YANG
We present a new scheduling policy named Value-based Processor Allocation (VPA-k) for scheduling value-based transactions in a multiprocessor real-time database system. The value of a transaction represents the profit the transaction contributes to the system if it is completed before its deadline. Using VPA-k policy, the transactions with higher values are given higher priorities to execute first, while at most k percentage of the total processors are allocated to the urgent transactions dynamically. Through simulation experiments, VPA-k policy is shown to outperform other scheduling policies substantially in both maximizing the totally obtained values and minimizing the number of missed transactions.
Budiarto Kaname HARUMOTO Masahiko TSUKAMOTO Shojiro NISHIO Tetsuya TAKINE
Mobile databases will play an important role in mobile computing environment, to provide data storing and data retrieval functionalities which are needed by most applications. In mobile computing environment, the wireless communication poses some problems, which require us to minimize its use. Replication is a database technique that is commonly used to fulfill the requirement in minimizing network usage. In this paper, we propose two replica allocation strategies, called primary-copy tracking replica allocation (PTRA) and user majority replica allocation (UMRA), which are better suited to the mobile computing environment. Their proposals are intended to cope with cost performance issues in data replication due to user mobility in mobile computing environment. To investigate their effectiveness, we provide access cost analysis and comparison on these strategies and the static replica allocation (SRA) strategy. We show that our proposed strategies outperform the SRA strategy when user mobility (inter-cell movement) is relatively low as compared with data access rate.
Tadashi DOHI Takashi AOKI Naoto KAIO Shunji OSAKI
This paper considers a probabilistic model for a database recovery action with checkpoint generations when system failures occur according to a renewal process whose renewal density depends on the cumulative operation period since the last checkpoint. Necessary and sufficient conditions on the existence of the optimal checkpoint interval which maximizes the ergodic availability are analytically derived, and solvable examples are given for the well-known failure time distributions. Further, several methods to be needed for numerical calculations are proposed when the information on system failures is not sufficient. We use four analytical/tractable approximation methods to calculate the optimal checkpoint schedule. Finally, it is shown through numerical comparisons that the gamma approximation method is the best to seek the approximate solution precisely.
This paper proposes the signaling network deployment for mobile networks with a goal of reducing the signaling cost and time to set up calls. In this deployment, we solve the heavy concentration of signaling traffic resulting from the centralized database used in current mobile networks. The solution exploits the features of the distributed databases, data partition, locality of mobile users, and Common Channel Signaling System No.7 (CCSS No.7) network architectures. We assume the area served by the mobile network is partitioned into a few zones. There is a database associated with each zone. A numbering database strategy is proposed in this paper for the mobiles to register at some specific nearby databases according to their mobile identification numbers. Thus, a calling party can directly locate the called party by the mobile identification number he/she dialed. This method can reduce over 95% of the location-updating cost and 70% of the location-tracking cost under a general sumulation model. We also present the implementation considerations of this strategy. This implementation is an enhancement of the routing function of the Signaling Connection Control Part in CCSS No.7 protocol stacks. With few modifications on current mobile networks, the proposed strategy can obtain very excellent results.
Osamu MIZUNO Akira SHIBATA Toshiya OKAMOTO Yoshihiro NIITSU
An advanced intelligent network (IN) provides service management along with telecommunication services, and has a two-layer architecture, i.e., a transmission layer and an intelligent layer. An advanced IN's programmability is achieved by a service-independent platform of nodes in the intelligent layer, and service-dependent software called logic programs. In contrast to telecommunication services, models for service management have not yet been established. This paper presents both execution and specification models for service management. The execution model is composed of three hierarchies that apply to various kinds of management operation. The specification model has the capability to define the details of data items. The specification language for service management is also proposed. Simulation on dynamic SQL based DBMS solved that; (1) Logic programs for service management can be made small size on the model, and (2) To provide efficient database operation, programmability must be enhanced if service management includes table with variable number of field operation.
Xiaoyong DU Zhibin LIU Naohiro ISHII
This paper discusses the relationships of two important program classes of linearly recursive programs, that is, decomposable programs and rule commutative programs. We prove that the decomposable programs are always rule commutative. Furthermore, the rule commutative programs that satisfy certain conditions are decomposable. These results are meaningful for integrating the related specified optimization algorithms.