An object replication algorithm for real-time distributed databases

A real-time distributed database system (RTDDBS) must maintain the consistency constraints of objects and must also guarantee the time constraints imposed by each request arriving at the system. Such a time constraint of a request is usually defined as a deadline period, which means that the request must be serviced on or before its time constraint. Servicing these requests may incur I/O costs, control-message transferring costs or data-message transferring costs. As a result, in our work, we first present a mathematical model that considers all these costs. Using this cost model, our objective is to service all the requests on or before their respective deadline periods and minimize the total servicing cost. To this end, from theoretical standpoint, we design a dynamic object replication algorithm, referred to as Real-time distributed dynamic Window Mechanism (RDDWM), that adapts to the random patterns of read-write requests. Using competitive analysis, from practical perspective, we study the performance of RDDWM algorithm under two different extreme conditions, i.e., when the deadline period of each request is sufficiently long and when the deadline period of each request is very short. Several illustrative examples are provided for the ease of understanding. Recommended by: Ashfaq Khokhar     

A survey of parallel execution strategies for transitive closure and logic programs

An important feature of database technology of the nineties is the use of parallelism for speeding up the execution of complex queries. This technology is being tested in several experimental database architectures and a few commercial systems for conventional select-project-join queries. In particular, hash-based fragmentation is used to distribute data to disks under the control of different processors in order to perform selections and joins in parallel. With the development of new query languages, and in particular with the definition of transitive closure queries and of more general logic programming queries, the new dimension of recursion has been added to query processing. Recursive queries are complex; at the same time, their regular structure is particularly suited for parallel execution, and parallelism may give a high efficiency gain. We survey the approaches to parallel execution of recursive queries that have been presented in the recent literature. We observe that research on parallel execution of recursive queries is separated into two distinct subareas, one focused on the transitive closure of Relational Algebra expressions, the other one focused on optimization of more general Datalog queries. Though the subareas seem radically different because of the approach and formalism used, they have many common features. This is not surprising, because most typical Datalog queries can be solved by means of the transitive closure of simple algebraic expressions. We first analyze the relationship between the transitive closure of expressions in Relational Algebra and Datalog programs. We then review sequential methods for evaluating transitive closure, distinguishing iterative and direct methods. We address the parallelization of these methods, by discussing various forms of parallelization. Data fragmentation plays an important role in obtaining parallel execution; we describe hash-based and semantic fragmentation. Finally, we consider Datalog queries, and present general methods for parallel rule execution; we recognize the similarities between these methods and the methods reviewed previously, when the former are applied to linear Datalog queries. We also provide a quantitative analysis that shows the impact of the initial data distribution on the performance of methods. Recommended by: Patrick Valduriez     

A semantic modeling approach for image retrieval by content

We introduce a semantic data model to capture the hierarchical, spatial, temporal, and evolutionary semantics of images in pictorial databases. This model mimics the user's conceptual view of the image content, providing the framework and guidelines for preprocessing to extract image features. Based on the model constructs, a spatial evolutionary query language (SEQL), which provides direct image object manipulation capabilities, is presented. With semantic information captured in the model, spatial evolutionary queries are answered efficiently. Using an object-oriented platform, a prototype medical-image management system was implemented at UCLA to demonstrate the feasibility of the proposed approach.     

Object-oriented DBMS requirements

The requirements on an object-oriented DBMS for management of information in a large, complex enterprise are presented. These requirements aid in the achievement of an environment characterized by data sharing, open architectures, application and data portability, and assurance of data integrity. They were defined from the point of view of a user of the DBMS; therefore they describe the expected functionality of the DBMS and do not specify the method of implementation to achieve this functionality. They encompass requirements on the data model, query and data manipulation languages, the system architecure, interfaces to the system, change management, and transaction management.     

Object data MODEL = object-oriented + semantic models

The term ‘object-oriented database’ has been used to refer to different characteristics and mechanisms supported by semantic databases and (behaviorally) object-oriented ones. While this indicates the current confusion due to the lack of a common model, it also suggests the potential desirability of combining these two kinds of modeling facilities into the same nutshell. This paper summarizes from these two paradigms the features common to both, the features influenced/adopted by each other, and the features which are presented in one paradigm but missing from the other. After a brief analysis and discussion of these features, we conclude this paper by proposing our major theme: a complete object data model should take the union of the facilities offered by these two kinds of models.     

HiSQL: A Front-end Query System for Historical Relational Databases

The paper describes a prototype system called HiSQL (Historical SQL) which extends the functionality of SQL in manipulating historical data, by providing functions for spatial and temporal processing. Conceptually the paper is divided into three parts: the first part deals with the design and architecture of the system; the second part introduces a case study (the defters); and the third part describes specific functions for spatial and temporal processing of serial documents. The paper concludes with a comparison between HiSQL and SQL and suggestions for further work. This revised version was published online in August 2006 with corrections to the Cover Date.     

SQL语言中量词和空值的使用技术

在ＳＱＬ语言中可以引入全称量词符号ＦＯＲＡＬＬ，使ＳＱＬ语言使用更为自然，方便。本文讨论全称量词，存在量词和ＡＬＬ三种谓词之间的转换，联系和区别，以及空值存在时ＳＱＬ的使用技术。     

Harvesting small trees and forest residues

Eight countries collaborated and shared technical information on the harvesting of small trees and forest residues in a three year program. Proceedings and reports from workshops and reviews are summarized in a review of activities and harvesting systems of the participating countries. Four databases were developed for harvesting and transportation of these materials.     

Intelligent handling of data by integration of commonsense reasoning

Any intelligent problem solving system should be able, given the known data on a case, to decide whether some item of information is true, false or unknown. In this paper the way in which various forms of commonsense reasoning can be integrated to provide such decisions is described. To this end three structural types of knowledge defined over data, and four strategies for exploiting these structures, are identified. ‘Decide-Status’ integrates the reasoning strategies into a task frame. This frame structure not only integrates the reasoning but also affords the appropriate facilities for providing strategic justifications for its conclusions, if required.