Browsing by Author "McAllister, Andrew, J."

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A new heuristic algorithm for the linear arrangement problem
    McAllister, Andrew, J.
    A new algorithm for the linear arrangement problem is described. The goal is to produce linear arrangements of software model diagrams such that the total length of all connections is reduced as much as possible. The algorithm uses the same general numbering strategy as existing algorithms for the highly related problems of bandwidth and profile reduction but is based on a new heuristic that addresses the unique requirements of the linear arrangement problem. Extensive testing is performed with graphs derived from software model diagrams and from structural engineering. The testing indicates that three refinements to the new algorithm improve the arrangements produced. The new algorithm produces linear arrangements with lower total weighted edge length for both classes of test graphs in comparison with several bandwidth and profile reduction algorithms, and for the software model diagrams in comparison with an eigenvalue-based linear arrangement algorithm. The new heuristic is also shown to require slightly less execution time than the frontal increase minimization heuristic used by several bandwidth and profile reduction algorithms, and far less execution time than the eigenvalue-based algorithm. Key words. graph, linear arrangement, bandwidth, profile, diagram layout, algorithm
  • Thumbnail Image
    Item
    Enhancing data models with tuning transformations
    Mattinson, Jason, E.; McAllister, Andrew, J.
    Maintaining consistency between an entity-relationship model and the relational database it represents can be problematic. As a database evolves, reverse engineering can be used periodically to capture an up-to-date model. There are difficulties, however, in obtaining accurate conceptual data requirements using automated reverse engineering tools. A new approach is proposed that ensures data models are up to date and removes the need for reverse engineering. Tuning transformations are introduced as a concise method for specifying database design modifications related to performance tuning. This method reduces the effort required to keep models up to date. Maintaining an entity-relationship model together with concise specifications of tuning transformations enables a tuned relational database definition to be generated automatically. Keywords: conceptual data model, relational database, reverse engineering, physical database design tuning transformations
  • Thumbnail Image
    Item
    On the realizability of cardinality constraints in conceptual data models
    (1999) McAllister, Andrew, J.; Horton, Joseph, D.
    A new property of conceptual data models is introduced. Realizability extends strong satisfiability as defined by Lenzerini and Nobili, which is held by a data model when it must be possible to create at least one non-empty database in which no cardinality constraints are violated. A constraint is realizable when at least one database can be created in which the number of associations involving a specific entity instance is equal to the limit imposed by the constraint. When all constraints in a data model are realizable, then the entire model is said to be realizable. It is possible for a data model to be strongly satisfiable but not realizable, which means the latter is a more stringent test for model correctness. We define bounds imposed by cardinality constraints on the relative sizes of entity sets. A data model is shown to be realizable if and only if the bounds for any cycle of relationships are either both equal to one, or the lower bound is strictly less than one while the upper bound is strictly greater than one.