Views as first-class citizens in object-oriented databases

Extensibility and dynamic schema evolution are among the attractive features that lead to the wide acceptance of the object-oriented paradigm. Not knowing all class hierarchy details should not prevent a user from introducing new classes when necessary. Naive or professional users may define new classes either by using class definition constructs or as views. However, improper placement of such classes leads to a flat hierarchy with many things duplicated. To overcome this problem, we automated the process in order to help the user find the most appropriate position with respect to her class in the hierarchy regardless of her knowledge of the hierarchy. The system must be responsible for the proper placement of new classes because only the system has complete knowledge of the details of the class hierarchy, especially in a dynamic environment where changes are very frequent. In other published work, we proved that to define a view it is enough to have the set of objects that qualify to be in a view in addition to having message expressions (possible paths) that lead to desired values within those objects. Here, we go further to map a view that is intended to be persistent into a class. Then we investigate the proper position of that class in the hierarchy. To achieve this, we consider current characteristics of a new class in order to derive its relationship with other existing classes in the hierarchy. Another advantage of the presented model is that views that generate new objects are still updatable simply because we based the creation of new objects on existing identities. In other words, an object participates inside view objects by its identity regardless of which particular values from that object are of interest to the view. Values are reachable via message expressions, not violating encapsulation. This way, actual values are present in only one place and can be updated.Received: 19 March 1999, Accepted: 26 December 2003, Published online: 8 April 2004Edited by: R. Topor.     

Support for modeling relationships in object-oriented databases

Modeling real-world applications typically consists of two parts: the representations of entities of interest, and the representations of relationships among the entities. Object-oriented data models support the first task. This paper argues through examples that the second modeling task is not well supported in current object-oriented database systems. An extended object-oriented data model that facilitates both modeling tasks is developed. This extension provides support for both the representation of complex relationships among entities and their manipulations (queries, updates). A prototype implemented on the ONTOS database management system is briefly described.     

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     

The study of indexing techniques on object oriented databases

An object-oriented database (OODB) has been becoming more important in recent years. It can deal with a large amount of complex objects and relationships that relational database (RDB) systems cannot handle well. However, the retrieval and update performance of an OODB depends on indexing techniques. In this paper, we study the indexing techniques on OODBs, based on an inheritance hierarchy and an aggregation hierarchy. Given the access probability and the size of each class, we propose a cost function to evaluate the gain of building an index on an inheritance hierarchy. For an aggregation hierarchy, we use a path-catenation technique to evaluate how to build index files on classes. Through some experiments, we found our methods have better retrieval performance than most ones proposed before.     

Cost-driven vertical class partitioning for methods in object oriented databases

In object-oriented databases (OODBs), a method encapsulated in a class typically accesses a few, but not all the instance variables defined in the class. It may thus be preferable to vertically partition the class for reducing irrelevant data (instance variables) accessed by the methods. Our prior work has shown that vertical class partitioning can result in a substantial decrease in the total number of disk accesses incurred for executing a set of applications, but coming up with an optimal vertical class partitioning scheme is a hard problem. In this paper, we present two algorithms for deriving optimal and near-optimal vertical class partitioning schemes. The cost-driven algorithm provides the optimal vertical class partitioning schemes by enumerating, exhaustively, all the schemes and calculating the number of disk accesses required to execute a given set of applications. For this, a cost model for executing a set of methods in an OODB system is developed. Since exhaustive enumeration is costly and only works for classes with a small number of instance variables, a hill-climbing heuristic algorithm (HCHA) is developed, which takes the solution provided by the affinity-based algorithm and improves it, thereby further reducing the total number of disk accesses incurred. We show that the HCHA algorithm provides a reasonable near-optimal vertical class partitioning scheme for executing a given set of applications.Received: 29 March 1999, Accepted: 11 March 2002, Published online: 3 April 2003This research has been supported, in part, by Hong Kong UGC Research Grants Council under grant CityU 733/96E and CityU 1119/99E.     

A formal approach to object-oriented databases

Object-oriented database systems are the focus of current research and development efforts. Yet, there is no commonly accepted object model, nor is it clear whether such a model can be developed. This paper reports on efforts to develop a formal framework that contains most features found in current object oriented database systems. The framework contains two parts. The first is a structural object model, including concepts such as structured objects, identity, and some form of inheritance. For this model, we explain the distinction between values and (abstract) objects, describe a system as a directed graph, and discuss declarative languages. The second part deals with higher-order concepts, such as classes and functions as data, methods, and inheritance. This part is a sketch, and leaves many issues unresolved. Throughout the paper, the emphasis is on logic-oriented modeling.     

A framework for distributing object-oriented designs

In response to the increasing demand of information processing, the object-oriented and client-server paradigms are becoming more pervasive. While implementation solutions integrating these two paradigms are widespread, there is minimal evidence that the merging of these two concepts has been considered at the design level. Specifically, object-oriented designs remain sequential in essence, and their mapping to a given distributed object-oriented programming language is left to the creativity and/or expertise of software engineers. In this paper, we propose a quantitative approach and a supporting tool to assist the designer in the distribution process. The metrics presented provide an easy way, but still consistent and reliable, to gauge the distribution suitability of various object-oriented design entities. Published online: 29 August 2002     

A taxonomy for moving object queries in spatial databases

In the past decade, many works have focused on the development of moving object database indexing and querying. Most of those works have concentrated on the common spatial queries which are used with static objects as well. However, moving objects have different features from static objects which may lead to a variety of queries. Therefore, it is important to understand the full spectrum of moving object queries, even before starting to build an index structure for such objects. The aim of this paper is to provide a complete picture of the capabilities of moving object queries. Thus motivated, in this paper we propose a taxonomy of moving object queries, comprising five perspectives: (i) Location perspective, (ii) Motion perspective, (iii) Object perspective, (vi) Temporal perspective and (v) Patterns perspective. These give an overall view of what moving object queries are about. In this work, each perspective is described and examples are given.     

A pattern-based object calculus

Several object-oriented database management systems have been implemented without an accompanying theoretical foundation for constraint, query specification, and processing. The pattern-based object calculus presented in this article provides such a theoretical foundation for describing and processing objectoriented databases. We view an object-oriented database as a network of interrelated classes (i.e., the intension) and a collection of time-varying object association patterns (i.e., the extension). The object calculus is based on first-order logic. It provides the formalism for interpreting precisely and uniformly the semantics of queries and integrity constraints in object-oriented databases. The power of the object calculus is shown in four aspects. First, associations among objects are expressed explicitly in an object-oriented database. Second, the nonassociation operator is included in the object calculus. Third, set-oriented operations can be performed on both homogeneous and heterogeneous object association patterns. Fourth, our approach does not assume a specific form of database schema. A proposed formalism is also applied to the design of high-level object-oriented query and constraint languages.     

Concurrent behavior: A construct to specify the external behavior of objects in object databases

We present a linguistic construct to define concurrency control for the objects of an object database. This construct, calledconcurrent behavior, allows to define a concurrency control specification for each object type in the database; in a sense, it can be seen as a type extension. The concurrent behavior is composed by two parts: the first one, calledcommutativity specification, is a set of conditional rules, by which the programmer specifies when two methods do not conflict each other. The second part, the constraint specification, is a set of guarded regular expressions, calledconstraints, by which the programmer defines the allowed sequences of method calls. At each time during an actual execution, a subset of constraints may be active so limiting the external behavior of the object. A constraint becomesactive when its guard is verified, where a guard is composed of the occurrence of some method callm along with the verification of a boolean expression on the object state and the actual parameters ofm. A constraint dies when a string of the language corresponding to the regular expression has been recognized. While the commutativity specification is devoted to specify the way in which the external behavior of an object is influenced by the existence of concurrent transactions in the system, the constraint specification defines the behavior of the object, independently from the transactions. Since the two parts of the concurrent behavior are syntactically distinct and, moreover, each of them consists of a set of independent rules, modularity in specifying the objects is enhanced, with respect to a unique specification. We outline an implementation of the construct, which is based on a look-ahead policy: at each method execution, we foresee the admissible successive behaviors of the object, instead of checking the admission of each request at the time it is actually made.     

A general shape context framework for object identification

A general shape context framework is proposed for object/image retrieval in occluded and cluttered environment with hundreds of models as the potential matches of an input. The approach is general since it does not require separation of input objects from complex background. It works by first extracting consistent and structurally unique local neighborhood information from inputs or models, and then voting on the optimal matches. Its performance degrades gracefully with respect to the amount of structural information that is being occluded or lost. The local neighborhood information applicable to the system can be shape, color, texture feature, etc. Currently, we employ shape information only. The mechanism of voting is based on a novel hyper cube based indexing structure, and driven by dynamic programming. The proposed concepts have been tested on database with thousands of images. Very encouraging results have been obtained.     

Clustering techniques in object bases: A survey

It is widely acknowledged that clustering is a cornerstone for the performance of database management systems. In particular, object-oriented databases have special properties which make clustering even more important for them than for conventional database models. In this paper, a survey is presented for the state of the art in the field of clustering in object bases. Several design dimensions are discussed and used as a basis for comparing different systems. Moreover, a set of selection guidelines and evaluation criteria are proposed and finally, open questions and future research directions are outlined.     

A semantical framework for supporting subjective and conditional probabilities in deductive databases

We present a theoretical basis for supporting subjective and conditional probabilities in deductive databases. We design a language that allows a user greater expressive power than classical logic programming. In particular, a user can express the fact thatA is possible (i.e.A has non-zero probability),B is possible, but (A B) as a whole is impossible. A user can also freely specify probability annotations that may contain variables. The focus of this paper is to study the semantics of programs written in such a language in relation to probability theory. Our model theory which is founded on the classical one captures the uncertainty described in a probabilistic program at the level of Herbrand interpretations. Furthermore, we develop a fixpoint theory and a proof procedure for such programs and present soundness and completeness results. Finally we characterize the relationships between probability theory and the fixpoint, model, and proof theory of our programs.     

A framework for semantic grouping in P2P databases

Sharing of structured data in decentralized environments is a challenging problem, especially in the absence of a global schema. Social network structures map network links to semantic relations between participants in order to assist in efficient resource discovery and information exchange. In this work, we propose a scheme that automates the process of creating schema synopses from semantic clusters of peers which own autonomous relational databases. The resulting mediated schemas can be used as global interfaces for relevant queries. Active nodes are able to initiate the group schema creation process, which produces a mediated schema representative of nodes with similar semantics. Group schemas are then propagated in the overlay and used as a single interface for relevant queries. This increases both the quality and the quantity of the retrieved answers and allows for fast discovery of interest groups by joining peers. As our experimental evaluations show, this method increases both the quality and the quantity of the retrieved answers and allows for faster discovery of semantic groups by joining peers.     

An object-oriented framework for finite element pavement analysis

In this study, we developed an object-oriented (OO) framework with interactive graphics to assist pavement studies using finite element analysis (FEA). FEA has been proven to be effective in studying various pavement failure problems; however, it is time consuming and error prone to manually generate the load sequences where non-regular tire footprints, non-uniform tire-pavement contact stresses, and transverse wheel wander distributions are used. After FEA, extracting the deformations for failure analysis is necessary but tedious. The OO framework developed in this study handles the preprocessing and postprocessing tasks for the FEA of pavements. It has a graphical user interface and is platform independent. It was successfully used in developing a new criterion for characterizing pavement failures that involved approximately four hundred different FEA simulations.     

CLIPS-OWL: A framework for providing object-oriented extensional ontology queries in a production rule engine

In this paper, we define a framework, namely CLIPS-OWL, for enabling the CLIPS production rule engine to represent the extensional results of DL reasoning on OWL ontologies in the form of Object-Oriented (OO) models. The purpose of this transformation is to allow CLIPS to use these OO models as static query models that are able to answer extensional ontology queries directly by the RETE reasoning engine during the development of custom CLIPS production rule programs, without interfacing at runtime the external DL reasoner. In that way, any CLIPS-based application may enhance its functionality by incorporating ontological knowledge without modifying the architecture of the CLIPS rule engine. CLIPS-OWL has been implemented using the Pellet DL reasoner and the CLIPS Object-Oriented Language (COOL).     

MPI framework for parallel searching in large biological databases

In this paper, we address the problem of searching huge biological databases on the scale of at least several gigabytes by utilizing parallel processing. Biological databases storing DNA sequences, protein sequences, or mass spectra are growing exponentially. Searches through these databases consume exponentially growing computational resources as well. We demonstrate herein a general use, MPI based, C++ framework for generically splitting databases amongst several computational nodes. The combined RAM of the nodes working in tandem is often sufficient to keep the entire database in memory, and therefore to search it efficiently without paging to disk. The framework runs as a persistent service, processing all submitted queries. This allows for query reordering and better utilization of the memory. Thereby, we achieve superlinear speedups compared to single processor implementations. We demonstrate the utility and speedup of the framework using a real biological database and an actual searching algorithm for mass spectrometry.