A simple characterization of database dependency implication

A simple and elegant set-theoretic characterization is given as to when a given set of functional and multivalued dependencies logically implies a given functional or multivalued dependency. A simple proof of the characterization is given which makes use of a result of Sagiv, Delobel, Parker, and Fagin (1981).     

Domain-knowledge-guided schema evolution for accounting database systems

The static meta-data view of accounting database management is that the schema of a database is designed before the database is populated and remains relatively fixed over the life cycle of the system. However, the need to support accounting database evolution is clear: a static meta-data view of an accounting database cannot support next generation dynamic environment where system migration, organization reengineering, and heterogeneous system interoperation are essential. This paper presents a knowledge-based approach and mechanism to support dynamic accounting database schema evolution in an object-based data modeling context. When an accounting database schema does not meet the requirements of a firm, the schema must be changed. Such schema evolution can be realized via a sequence of evolution operators. As a result, this paper considers the question: what heuristics and knowledge are necessary to guide a system to choose a sequence of operators to complete a given evolution task for an accounting database? In particular, we first define a set of basic evolution schema operators, employing heuristics to guide the evolution process. Second, we explore how domain-specific knowledge can be used to guide the use of the operators to complete the evolution task. A well-known accounting data model, REA model, is used here to guide the schema evolution process. Third, we discuss a prototype system, REAtool, to demonstrate and test our approach.     

A unit test approach for database schema evolution

Context

The constant changes in today’s business requirements demand continuous database revisions. Hence, database structures, not unlike software applications, deteriorate during their lifespan and thus require refactoring in order to achieve a longer life span. Although unit tests support changes to application programs and refactoring, there is currently a lack of testing strategies for database schema evolution.

Objective

This work examines the challenges for database schema evolution and explores the possibility of using various testing strategies to assist with schema evolution. Specifically, the work proposes a novel unit test approach for the application code that accesses databases with the objective of proactively evaluating the code against the altered database.

Method

The approach was validated through the implementation of a testing framework in conjunction with a sample application and a relatively simple database schema. Although the database schema in this study was simple, it was nevertheless able to demonstrate the advantages of the proposed approach.

Results

After changes in the database schema, the proposed approach found all SELECT statements as well as the majority of other statements requiring modifications in the application code. Due to its efficiency with SELECT statements, the proposed approach is expected to be more successful with database warehouse applications where SELECT statements are dominant.

Conclusion

The unit test approach that accesses databases has proven to be successful in evaluating the application code against the evolved database. In particular, the approach is simple and straightforward to implement, which makes it easily adoptable in practice.     

Data schema evolution support in XML-relational database systems

Many XML-relational systems, i.e., the systems that use an XML schema as an external schema and a relational schema as an internal schema of the data application representation level, require modifications of the data schemas in the course of time. Schema evolution is one of the ways to support schema modifications for the application at the DBMS level. A number of schema evolution support systems for different data models have been suggested. Schema evolution can be applied to mapping-related evolving schemas (such as schemas of XML-relational systems), the transformation problem for which is also known as schema adaptation. In this paper, a survey of various approaches to solving the outlined problems is given.     

Object-oriented database management systems: evolution andperformance issues

Several research prototypes and commercial object-oriented database management systems (DBMSs) that emphasize the representation and manipulation of complex objects are reviewed. It is argued that clustering and buffering schemes tailored to typical complex object operations offer the best near-term means of improving the performance of databases and that research in clustering and buffering should address recent advances in disk technology: optical and parallel disks. The object-oriented DBMSs reviewed are Orion, Iris, GemStone, Encore, Ontos, Versant, and ObjectStore     

Conceptual database evolution through learning in object databases

Changes to the conceptual structure (meta-data) of a database are common in many application environments and are in general inadequately supported by existing database systems. An approach to supporting such meta-data evolution in a simple, extensible, object database environment is presented. Machine learning techniques are the basis for a cooperative user/system database design and evolution methodology. An experimental end-user database evolution tool based on this approach has been designed and implemented     

MeDEA: A database evolution architecture with traceability

One of the most important challenges that software engineers (designers, developers) still have to face in their everyday work is the evolution of working database systems. As a step for the solution of this problem in this paper we propose MeDEA, which stands for Metamodel-based Database Evolution Architecture. MeDEA is a generic evolution architecture that allows us to maintain the traceability between the different artifacts involved in any database development process. MeDEA is generic in the sense that it is independent of the particular modeling techniques being used. In order to achieve this, a metamodeling approach has been followed for the development of MeDEA. The other basic characteristic of the architecture is the inclusion of a specific component devoted to storing the translation of conceptual schemas to logical ones. This component, which is one of the most noteworthy contributions of our approach, enables any modification (evolution) realized on a conceptual schema to be traced to the corresponding logical schema, without having to regenerate this schema from scratch, and furthermore to be propagated to the physical and extensional levels.     

Robust pedestrian detection under deformation using simple boosted features

Many existing methods for pedestrian detection have the limited detection performance in case of deformation such as large appearance variations. To overcome this limitation, we propose a novel pedestrian detection method that uses two low-level boosted features to detect pedestrians despite the presence of deformations. One is a boosted max feature (BMF) that uses a max operation to aggregate a selected pair of features to make them invariant to deformation. Another is a boosted difference feature (BDF) that uses a difference operation between a selected pair of features to improve localization accuracy of pedestrian detection. We incorporate a spatial pyramid pool method that uses multiple sized blocks to increase the richness of boosted features in a local region and use a RealBoost method to train a tree-structured classifier for the proposed pedestrian detection method. We also apply a region-of-interest method to the detected results to remove false positives effectively. Our proposed detector achieved log-average miss rates of 19.95%, 10.39%, 36.12%, and 39.57% on the Caltech-USA, INRIA, ETH, and TUD-Brussels dataset, respectively, which are the lowest among those of all state-of-the-art pedestrian detectors.     

A characterization of database graphs admitting a simple locking protocol

Summary A simple locking protocol is presented for transactions executing concurrently in a database. The locking protocol is not two-phase, but each entity in the database may be locked at most once by any transaction. The database is modeled by a directed graph whose vertices correspond to the entities, and whose arcs correspond to certain locking restrictions. Necessary and sufficient conditions which assure serializability and deadlock-freedom in the absence of a concurrency control are derived.     

A language for simple interactive retrieval from a database system

Query interaction with a database system requires, in general, some understanding of the content and structure of the database, and knowledge of a suitable query language to encode the request for data. These factors impose barriers against access to a database on a casual or irregular basis. To overcome such restrictions we have investigated the use of a pseudo-intelligent front-end retrieval system. This system was designed to be independent of any specific database management system, although a relational database structure was considered to be the most appropriate. A prototype version of the system has been set up to run on top of Logica's relational database management system RAPPORT and the IBM relational database system SQL. As a result of this experience we have developed an adaptable language to facilitate intelligent interaction between an end user and a database management system.     

A feature-based database evolution approach in the design process

Design data are assigned in geometric and non-geometric form in order to meet design requirements. These data and information must be encapsulated in a data structure that has significance for design applications in each design process phase. The main goal of this research is to find design data groups that represent each mechanical design phase, which will be called phase's design signature. In addition, current data should be an evolution of the geometric and non-geometric information of the previous design phase. In this paper, the purpose is to identify and model a set of design features that encapsulate the design data and their transformations which occurred during the mechanical design phases. This database must capture the designer's intents that can be modeled and implemented using feature-based model in the conventional CAD systems, object-oriented modeling, and Java classes.     

Robust stability analysis of simple systems controlled over communication networks

There is increasing interest in controlling systems over communication networks. Using a simple method called dual-locus diagram, this communique proposes complete stability criteria for a mass-spring-damper system controlled over the network. The stability region is divided into a delay-dependent stability region and a delay-independent stability region, which offers a nice graphical view on the conservativeness of the delay-independent stability criteria.     

Schema evolution of an object-oriented real-time database systemfor manufacturing automation

Database schemata often experience considerable changes during the development and initial use phases of database systems for advanced applications such as manufacturing automation and computer-aided design. An automated schema evolution system can significantly reduce the amount of effort and potential errors related to schema changes. Although schema evolution for nonreal-time databases was the subject of previous research, its impact on real-time database systems remains unexplored. These advanced applications typically utilize object-oriented data models to handle complex data types. However, there exists no agreed-upon real-time object-oriented data model that can be used as a foundation to define a schema-evolution framework. Therefore, the authors first design a conceptual real-time object-oriented data model, called Real-time Object Model with Performance Polymorphism (ROMPP). It captures the key characteristics of real-time applications-namely, timing constraints and performance polymorphism-by utilizing specialization-dimension and letter-class hierarchy constructs, respectively. They then re-evaluate previous (nonreal-time) schema evolution support in the context of real-time databases. This results in modifications to the semantics of schema changes and to the needs of schema change resolution rules and schema invariants. Furthermore, they expand the schema change framework with new constructs-including new schema change operators, new resolution rules, and new invariants-necessary for handling the real-time characteristics of ROMPP     

Quantum search in structured database using local adiabatic evolution and spectral methods

Since Grover’s seminal work which provides a way to speed up combinatorial search, quantum search has been studied in great detail. We propose a new method for designing quantum search algorithms for finding a marked element in the state space of a graph. The algorithm is based on a local adiabatic evolution of the Hamiltonian associated with the graph. The main new idea is to apply some techniques such as Krylov subspace projection methods, Lanczos algorithm and spectral distribution methods. Indeed, using these techniques together with the second-order perturbation theory, we give a systematic method for calculating the approximate search time at which the marked state can be reached. That is, for any undirected regular connected graph which is considered as the state space of the database, the introduced algorithm provides a systematic and programmable way for evaluation of the search time, in terms of the corresponding graph polynomials.     

Robust heuristic algorithms for exploiting the common tasks of relational cloud database queries

Cloud computing enables a conventional relational database system's hardware to be adjusted dynamically according to query workload, performance and deadline constraints. One can rent a large amount of resources for a short duration in order to run complex queries efficiently on large-scale data with virtual machine clusters. Complex queries usually contain common subexpressions, either in a single query or among multiple queries that are submitted as a batch. The common subexpressions scan the same relations, compute the same tasks (join, sort, etc.), and/or ship the same data among virtual computers. The total time spent for the queries can be reduced by executing these common tasks only once. In this study, we build and use efficient sets of query execution plans to reduce the total execution time. This is an NP-Hard problem therefore, a set of robust heuristic algorithms, Branch-and-Bound, Genetic, Hill Climbing, and Hybrid Genetic-Hill Climbing, are proposed to find (near-) optimal query execution plans and maximize the benefits. The optimization time of each algorithm for identifying the query execution plans and the quality of these plans are analyzed by extensive experiments.