An automated entity–relationship clustering algorithm for conceptual database design

Entity–relationship (ER) modeling is a widely accepted technique for conceptual database design. However, the complexities inherent in large ER diagrams have restricted the effectiveness of their use in practice. It is often difficult for end-users, or even for well-trained database engineers and designers, to fully understand and properly manage large ER diagrams. Hence, to improve their understandability and manageability, large ER diagrams need to be decomposed into smaller modules by clustering closely related entities and relationships. Previous researchers have proposed many manual and semi-automatic approaches for such clustering. However, most of them call for intuitive and subjective judgment from “experts” at various stages of their implementation. We present a fully automated algorithm that eliminates the need for subjective human judgment. In addition to improving their understandability and manageability, an automated algorithm facilitates the re-clustering of ER diagrams as they undergo many changes during their design, development, and maintenance phases.     

A CASE tool for conceptual database design

The paper describes a Computer Aided Software Engineering (CASE) tool to support conceptual database modelling. One popular approach for conceptual database modelling is use of the Entity-Relationship (ER) model. The paper proposes the use of an Enhanced Entity-Relationship (EER) model for conceptual database modelling. This Enhanced Entity-Relationship model extends the Entity-Relationship model by incorporating the generalization/specialization, aggregation and categorization abstractions. The CASE tool, which is based on the Enhanced Entity-Relationship model, is known as the Enhanced Entity-Relationship Diagrammer (EERD). In addition, the CASE tool supports direct visual query and update based on the EERM.     

Iteration-free clustering algorithm for nonstationary image database

Image database systems must effectively and efficiently handle and retrieve images from a large collection of images. A serious problem faced by these systems is the requirement to deal with the nonstationary database. In an image database system, image features are typically organized into an indexing structure, and updating the indexing structure involves many computations. In this paper, this difficult problem is converted into a constrained optimization problem, and the iteration-free clustering (IFC) algorithm based on the Lagrangian function, is presented for adapting the existing indexing structure for a nonstationary database. Experimental results concerning recall and precision indicate that the proposed method provides a binary tree that is almost optimal. Simulation results further demonstrate that the proposed algorithm can maintain 94% precision in seven-dimensional feature space, even when the number of new-coming images is one-half the number of images in the original database. Finally, our IFC algorithm outperforms other methods usually applied to image databases.     

Computer aided design of database internal schema

A large number of complexly interrelated parameters are involved at the internal schema level design of database systems. Consequently, a single design model is seen to be infeasible. A package of three aids is proposed to assist a designer in step by step design of internal schema. The three aids pertain to splitting of a relation, merging of relations, and access strategy selection for a relation.     

Novice errors in conceptual database design

Conceptual and logical database modelling are difficult tasks for designers, and the potential for committing and correcting errors is significant. This paper reports on two laboratory experiments that investigated the underlying causes of errors committed by novice designers engaged in conceptual database modelling tasks. These causes can be traced to combinatorial complexity of the task, biases resulting from misapplication of heuristics, and incomplete knowledge about database design. The most common error was that subjects translated their initial understanding of the application into final database structures and did not consider alternative hypotheses and solutions. The paper includes recommendations to reduce the occurrence of errors.     

A comprehensive framework for modeling set-based business rules during conceptual database design

Business rules are the basis of any organization. From an information systems perspective, these business rules function as constraints on a database helping ensure that the structure and content of the real world—sometimes referred to as miniworld—is accurately incorporated into the database. It is important to elicit these rules during the analysis and design stage, since the captured rules are the basis for subsequent development of a business constraints repository. We present a taxonomy for set-based business rules, and describe an overarching framework for modeling rules that constrain the cardinality of sets. The proposed framework results in various types constraints, i.e., attribute, class, participation, projection, co-occurrence, appearance and overlapping, on a semantic model that supports abstractions like classification, generalization/specialization, aggregation and association. We formally define the syntax of our proposed framework in Backus-Naur Form and explicate the semantics using first-order logic. We describe partial ordering in the constraints and define the concept of metaconstraints, which can be used for automatic constraint consistency checking during the design stage itself. We demonstrate the practicality of our approach with a case study and show how our approach to modeling business rules seamlessly integrates into existing database design methodology. Via our proposed framework, we show how explicitly capturing data semantics will help bridge the semantic gap between the real world and its representation in an information system.     

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.     

A conceptual database design approach based on rules and heuristics

Conceptual and logical database design are complex tasks for non-expert designers. Currently, the popular data models for conceptual and logical database design are the entity–relationship (ER) and the relational model, respectively. Logical design methodologies for relational databases have relied on mathematically rigorous approaches which are impractical, or textbook approaches which do not provide the rich constructs to capture real applications. Consequently, designers have to use their intuition to develop their own rules and heuristics. There is a need, therefore, to develop practical rules and heuristics that can be used to handle the complexity of design in real applications. This paper proposes a realistic and detailed approach for conceptual design using the ER model for relational databases. The approach is based on four rules that specify the order in which various types of relationships must be modelled, three rules that pertain to detection of derived relationships, and three heuristics based on observation of constructs in real applications. The approach is illustrated by many examples.     

Framework design of a domain-key schema of a relational database

A new approach to the synthesis of the domain-key normal form (DK/NF) for an arbitrary domain is proposed. The Cartesian dependency, which is a special case of multivalued dependencies, is investigated. A lemma on the non-abnormality of a special relational and a theorem on the non-abnormality of the actual part of a relational framework are proved. A new criterion for determining the belonging of a database schema to DK/NF is given. The proposed approach can be used in designing information warehouse schemas.     

Reducing the search space for conceptual schema transformation

In this paper we focus on the transformation of a conceptual schema into an internal schema. For a given conceptual schema, quite a number of internal schemata can be derived. This number can be reduced by imposing restrictions on internal schemata.

We present a transformation algorithm that can generate internal schemata of several types (including the relational model and the NF² model). Guidance parameters are used to impose further restrictions.

We harmonise the different types of schemata by extending the conceptual language, such that both the conceptual and the internal models can be represented within the same language.     

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.     

Information semantics and the conceptual schema

The semantics of various proposals for Conceptual Schema languages are compared and contrasted. Concepts are defined using logic and class theory notation, so that terminology is reduced to a common basis. A basis for handling temporal aspects of an Information System is provided.     

Alternate implementations of the conceptual schema

A proposal is made to allow a data base administrator to define arbitrary data models at the conceptual level. A set of abstract concepts for the purpose is developed and an implementation described. Alternate interfaces by which the dba can define arbitrary data models in terms of theses concepts are described.     

A sweep-line algorithm for spatial clustering

This paper presents an agglomerative hierarchical clustering algorithm for spatial data. It discovers clusters of arbitrary shapes which may be nested. The algorithm uses a sweeping approach consisting of three phases: sorting is done during the preprocessing phase, determination of clusters is performed during the sweeping phase, and clusters are adjusted during the post processing phase. The properties of the algorithm are demonstrated by examples. The algorithm is also adapted to the streaming algorithm for clustering large spatial datasets.     

An extended system for conceptual clustering

CLUSTER/2 (Michalski, 1980a, Stepp&Michalski, 1986) in a conceptual clustering system, having the great advantage that obtained clusters are represented in the formof symbolic expressions. However, it has some disadvantages. In this article, a modified version of CLUSTER/2 is proposed. Background knowledge can be conveyed to the system through semantic networks; differentiation among objects is calculating using semantic distance. A different quality evaluation is used to measure the quality of clustering in a more sensible way. The order dependence problem of overlap resolution is eliminated with a fuzzy k-nearest neighborhood technique. Finally, a hill-climbing algorithm is applied to determine the number of clusters automatically. These improvements provide a more stable and user-friendly clustering environment for the user, without changing the system architecture of CLUSTER/2.     

A grey-based clustering algorithm and its application on fuzzy system design

A grey-based clustering method was proposed and applied on fuzzy system design. A new grey-clustering algorithm using grey relational analysis as the similarity measure was developed for data clustering. It was more effective and accurate than C-Means like algorithms when dealing with data clustering issue, when the compact and complete separate data were considered. Some data clustering examples are presented to illustrate the effectiveness of the proposed clustering algorithm. Next, an application of the proposed method on fuzzy system design is presented. The procedure of fuzzy system design can be separated into two parts. In the first procedure, the grey-clustering algorithm was employed to form a rough fuzzy system only from gathered input-output data. Then, the gradient descent method was used to determine a suitable parameter set of the formed fuzzy system. A nonlinear system modelling and an inverted pendulum control problem were then used to illustrate the validity of the proposed fuzzy system design procedure.