While the secure concurrency controllers (SCCs) in multilevel secure database systems (MLS/DBMSs) synchronize transactions cleared at different security levels, they must consider the problem of covert channel. We propose a new SCC, named Verified Order-based secure concurrency controller (VO) that founds on multiversion database. VO maintains elaborated information about ordering relationships among transactions in a way of actively investigating and renewing the ordering relationships whenever it receives operations. With the elaborated information, it becomes capable of aborting transactions selectively whose non-interfered executions definitely violate one-copy serializability and providing more recent data versions to read requests than the other multiversion-based SCCs. Therefore, it comes to reduce the abort ratio and provide data versions of improved trustworthiness to transactions. By virtue of the elaborated information, moreover, VO is able to distinguish worthful versions and worthful transactions from worthless ones, so that it is capable lightening the burdens of maintaining multiple versions and accumulated transaction ordering relationships. For the aborts that are inevitable for preserving one-copy serializability, VO achieves security by deriving the conflicts to occur between transactions that have been cleared at the same security level.

Recent developments in computer technology allow us to analyze all the data in a huge database. Data mining is to analyze all the data in such a database and to obtain useful information for database users. One of the well-studied problems in data mining is the search for meaningful association rules in a market basket database which contains massive amounts of transactions. One way to find meaningful association rules is to find all the large itemsets first, and then to find meaningful association rules from the large itemsets. Although a number of algorithms for computing all the large itemsets have been proposed, the computational complexity of them is scarcely disscussed. In this paper, we show that it is NP-complete to decide whether there exists a large itemset that has a given cardinality. Also, we propose subclasses of databases in which all the meaningful association rules can be computed in time polynomial of the size of a database.

This paper clarifies the appropriate traffic domains for combination between two database schemes (i. e. , HLR database scheme and VLR database scheme) and two call routing schemes (i. e. , Redirection Routing scheme and Look-a-head Routing scheme) in the Global Mobility Network (GLOMONET), which is able to provide global roaming service for the personal telecommunication user. The appropriate domains for combination between each scheme are shown to depend on user's mobility (i. e. the frequency of a user's access to a network where the user stays, the length of the period during which the user stays in the same network). Whether the appropriate domains for the HLR database scheme exist depends only on the frequency of the user's access to the network. When there are appropriate domains for the HLR database scheme, increasing the frequency of the user's access to the network, decreasing the length of the period the user stays in the user's home network, or increasing the length of the period the user stays in a network that isn't the user's home network widens the domains where the VLR database scheme is appropriate.

A service control node in the Advanced Intelligent Network (AIN) allocates data for customers among multiple modules and performs distributed processing of multiple transactions. In such a node, load can vary among the modules due to dispersion in the amount of traffic for each customer. It is therefore important to balance out this load variation and raise the utilization of each module in order to achieve an efficient distributed processing system. We first propose a method for balancing the load among modules by dynamically transferring customer data in units of records from high-load modules to low-load modules. Then, based on this method, a method for selecting records to be transferred between modules is also proposed. And we clarify the processor overhead for transferring records. The effect of the reduction of number of modules by load balancing is also evaluated. Based on the these results, it is shown that dynamic transferring of records is an effective scheme for balancing load among modules in a service control node of the AIN.

In a mobile computing environment, in which communication channels are limited and have low-bandwidths, mobile transactions are long-lived and frequently disconnected with their wireless network in processing. Such peculiarities of mobile transactions make existing transaction scheduling schemes inadequate and raise new challenging research problems. In this paper, we propose a new scheduling scheme called OTS/MT (Optimistic Timestamp Scheme for Mobile Transactions) for mobile transaction scheduling. OTS/MT is based on an optimistic approach that is suitable for low data contention, and prevents indefinite postponement and cascading delay which are major drawbacks of the existing optimistic concurrency control scheme and the timestamp ordering scheme. In addition, the OTS/MT algorithm is inherently a deadlock-free scheduling scheme. In order to schedule mobile transactions, OTS/MT postpones the detection of conflict between mobile transactions until transaction commit time to improve the performance deterioration of TO. In this paper, we attempt to show that this application of optimism to TO is justified by way of simulation.

Human faces convey various information, including that is specific to each individual person and that is part of mutual communication among persons. Information exhibited by a "face" is what is called "non-verbal information" and usually verbal media cannot easily describe such information appropriately. Recently, detailed studies on the processing of face images by a computer have been carried out in the engineering field for applications to communication media and human computer interaction as well as automatic identification of human faces. Two main technical topics are the recognition of human faces and the synthesis of face images. The objective of the former is to enable a computer to detect and identify users and further to recognize their facial expressions, while that of the latter is to provide a natural and impressive user interface on a computer in the form of a "face. " These studies have also been found to be useful in various non-engineering fields related to a face, such as psychology, anthropology, cosmetology and dentistry. Most of the studies in these different fields have been carried out independently up to now, although all of them deal with a "face. " Now in virtue of the progress in the above engineering technologies a common study tools and databases for facial information have become available. On the basis of these backgrounds, this paper surveys recent research trends in the processing of face images by a computer and its typical applications. Firstly, the various characteristics of faces are considered. Secondly, recent research activities in the recognition and synthesis of face images are outlined. Thirdly, the applications of digital processing methods of facial information are discussed from several standpoints: intelligent image coding, media handling, human computer interaction, caricature, facial impression, psychological and medical applications. The common tools and databases used in the studies of processing of facial information and some related topics are also described.

Recently, mobile computing has received much attention from database community. Sharing information among mobile users is one of the most challenging issues in mobile computing due to user mobility. Replication is a promising technique to this issue. However, adopting replication into mobile computing is a non-trivial task, since we are still facing other problems such as the lack in disk capacity and wireless network bandwidth used by mobile users. We have proposed a dynamic replica allocation strategy called User Majority Replica Allocation (UMRA) that is well suited to the modern architecture of mobile computing environment while avoiding such problems mentioned above. In this paper, we propose two relocation decision policies for UMRA and we provide a cost analysis for them. We also provide a cost analysis for another replica allocation strategy called Static Replica Allocation (SRA) for a comparison purpose.

Object-Oriented database systems (OODBMS) are well known for modeling complex and dynamic application domains. Typically OODBMS have to handle large and complex structured objects whose values and structures can change frequently. Consequently there is a high demand for systems which support temporal and versioning features in both objects (or database population) and schema. This paper presents a mechanism for accessing the temporal versioned objects stored in the database which supports schema versioning. The results shown here can be considered as a value-added extension of our model called TVOO described in detail in [1] and [2]. In contrast to conventional database models, in TVOO objects and classes are not physically discarded from the database after they are modified or deleted. They are time dependent and the history of the changes which occur on them are kept as Version hierarchies. Therefore our model enriches the database environment with temporal and versioning features. Also, an access mechanism which makes it possible to access any object under any schema version is defined in such a way that not only objects created under old versions of schema classes can be accessed from new versions, but also objects created by new schema class versions can be accessed from old versions of the respective class.

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.

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 advent of high-speed networks with quality of service guarantees, will enable the deployment of data-server distributed systems over wide-area networks. Most implementations of data-server systems have been over local area networks. Thus it is important, in this context, to study the performance of existing distributed data management protocols in the new networking environment, identify the performance bottlenecks and develop protocols that are capable of taking advantage of the high speed networking technology. In this paper, we examine and compare the scalability of the server-based two-phase locking protocol (s-2PL), and the group two-phase locking protocol (g-2PL). The s-2PL protocol is the most widely used concurrency control protocol, while the g-2PL protocol is an optimized version of the s-2PL protocol, tailored for high-speed wide-area network environments. The g-2PL protocol reduces the effect of the network latency by message grouping, client-end caching and data migration. Detailed simulation results indicate that g-2PL indeed scales better than s-2PL. For example, upto 28% improvement in response time is reported.

This paper introduces a material management system for newspapers that was developed for The Yomiuri Shimbun. Material transferred to the system is stored in a material database and sent to terminals located in the related sections. The material can be processed effectively just by checking information on the terminals. Special requirements for this system will be discussed first in the paper, then problem-solving will be explored.

Structured documents often contain character strings of which semantics can be naturally stored as database values or has direct correspondence with database values. By building bilateral logical links between character strings in documents and corresponding database values, semantically rich queries are made expressible. We have introduced a new ADT, named "paratext," to model text which has links with database values. Paratexts are logically viewed as consisting of two parallel layers; on the "appearance" layer, ordinary text (i. e. a linear sequence of character strings) is placed, while the "reference" layer holds an array of OIDs and literals. Each OID or literal on the reference layer is associated with a contiguous substring of the appearance layer text, and represents the semantics of the associated substring. We have also designed domain-specific functions for this document model. Using the functions, we can express queries which go back and forth between the two layers. In structured documents, such character strings can appear in the whole content of logical elements, or as phrases inside logical elements. We also present frameworks for the implementation of the paratext ADT, and discuss how traditional full-text indexing techniques can be extended to support paratext.

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.

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.

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.

In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical traffic information newly becomes available and the static geographical database of roads itself has grown up further, more flexible queries are required to realize a user-friendly interface meeting the current settings. One important query among them is a detour query which provides information about detours, say listing several candidates for useful detours. This paper first reviews algorithms for the shortest and k shortest paths, and discusses their extensions to detour queries. Algorithms for finding a realistic detour are given. The efficiency and property of the algorithms are examined through experiments on an actual road network.

This paper surveys recent research activities on three major areas of digital media information base, namely, video database systems as a typical example of temporal application, database systems for mixed reality as an instance of spatial application, and kansei management for digital media retrieval as a case of humanistic feelings application. Current research results by the project Advanced Database Systems for Integration of Media and User Environments are reported.

This paper focuses on the problems how to organize and retrieve video data in an effective manner. First we identify several issues to be solved for the problems. Next, we overview our current research results together with a brief survey in the research area of video databases. We especially describe the following research results obtained by the the Japanese Ministry of Education under Grant-in-Aid for Scientific Research on Priority Area: "Advanced Databases" concerned with organization and retrieval of video data: Instance-Based Video Annotation Models, Self-Organization of Video Data, and A Query Model for Fragmentally Indexed Video.

Support of collaborative work and management of spatio-temporal data has become one of the most interesting and important database applications, which is due to the tremendous progress of database and its surrounding technologies in the last decade. In this paper, we investigate the new generation database technologies that are needed to support such advanced applications. Because of the recent progress of virtual reality technology, virtual work spaces are now available. We examine a typical CSCW (Computer Supported Cooperative Work) fsystem to identify database problems that arise from it. We introduce typical approaches to database improvement based on the high-level view and the virtual reality technique. Also, in this paper, the following are introduced and discussed: the design and implementation of three- and four-dimensional spatio-temporal database systems, VRML (Virtual Reality Modeling Language) database systems, fast access methods to spatio-temporal data, and the interval-based approach to temporal multimedia databases.