Search

The data dictionary contains the description of all types of data produced, managed, exchanged, and maintained in an organization. Data descriptions (very often hundreds of schemas) should be organized in such a way to allow all the users of the information system to understand the meaning of data and their relationships. In this paper, a new set of structuring primitives is presented for a dictionary of entity relationship data schemas. The formal properties of such structuring primitives ire investigated and the feasibility of their usage is shown by providing a methodology for dictionary design. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze the relationships among different planar embeddings of the same graph and study how two planar embeddings can be morphed one into the other with the minimum number of elementary changes, while preserving the mental map of the user. We call this problem Topological Morphing, in analogy with the well-known Geometric Morphing problem, in which it is studied how two planar drawings can be morphed one into the other with the minimum number of elementary changes. First, we define two operations, called flip and skip, describing natural transformations of a graph embedding that preserve the mental map of the user. Then, we study the problem of performing a morph while minimizing the number of these operations. We show that the Topological Morphing problem is NP-hard for biconnected planar graphs, we give polynomial-time algorithms for some restricted versions of the problem, and, based on such polynomial-time algorithms, we give a fixed-parameter tractable algorithm for the general case. [Copyright &y& Elsevier]