\documentclass{article}
\usepackage{times}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{pstricks}
\usepackage{pst-node}
\usepackage{subfigure}
\usepackage{multirow}
\usepackage{eepic}
\usepackage{rotating}
\usepackage{a4wide}
\usepackage{multicol}
\title{\textbf{Translating Descriptions of a Viewpoint \\ among Different Representations}}
\author{Nigel Stanger \\ \emph{University of Otago, Dunedin, New Zealand} \\ \emph{nstanger@infoscience.otago.ac.nz}}
\date{}
\def\figures{:Figures:} % Mac path
%\def\figures{Figures\} % DOS path
%\def\figures{Figures/} % Unix path
\setlength{\textwidth}{6.8125in} % 6 7/8 in
\setlength{\columnsep}{0.3125in} % 5/16 in
\setlength{\oddsidemargin}{-0.2723in} % to compensate
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textheight}{8.875in} % 8 7/8 in
\renewcommand{\topfraction}{0.9}
\renewcommand{\bottomfraction}{0.7}
\begin{document}
\maketitle
\input{hyphenation}
\input{commands}
\begin{multicols}{2}
\section*{Abstract}
\emph{An important part of the systems development process is building models of real-world phenomena. These phenomena are described by many different kinds of information, and this diversity has resulted in a wide variety of modelling representations. Some types of information are better expressed by some representations than others, so it is sensible to use multiple representations to describe a real-world phenomenon. The author has developed an approach to facilitating the use of multiple representations within a single viewpoint by translating descriptions of the viewpoint among different representations. An important issue with such translations is their \emph{quality}, or how well they map constructs of one representation to constructs of another representation. Two possible methods for improving translation quality, \emph{heuristics} and \emph{enrichment}, are proposed in this paper, and a preliminary metric for measuring relative translation quality is described.}
%================================================================================
\section{Introduction}
\label{Sec:Translating:Introduction}
To more completely model a phenomenon, Finkelstein et al.~\cite{Fink:ACW:1989} suggested using multiple descriptions of the phenomenon expressed using different representations. For example, a data flow diagram (DFD) is a description of constituent business processes expressed using a representation suited to showing the flow of information among these processes; whereas an entity-relationship diagram (ERD) describes clearly the structure and associations among data elements. The benefits from using different descriptions of the same phenomenon are recognised in current modelling approaches such as the Unified Modeling Language (UML) \cite{Rumb:J:1999:UML}, in which real world phenomena are described using a combination of use cases, class hierarchy diagrams, sequence diagrams, state charts, and so on.
The author has developed an approach to facilitating the use of multiple representations within a single viewpoint by translating descriptions of the viewpoint among different representations \cite{Stan:N:1999:PhD}. These translations are defined by a collection of \emph{rules} that specify how to map constructs of a source representation to constructs of a target representation. A key issue with such translations is how well they map constructs of the source representation onto constructs of the target representation, referred to here as the \emph{quality} of a translation \cite{Pasc:RT:1990}.
In this paper are proposed two possible methods for improving the quality of translations between representations: use of \emph{heuristics} which allow additional information to be generated automatically by a translation; and \emph{enrichment}, in which the translation elicits missing information from the developer. Also described is a preliminary metric that has been used to show that heuristics can improve the quality of translations.
%================================================================================
\section{Terminology and notation used in this paper}
Finkelstein et al.~\cite{Fink:ACW:1989} suggested using multiple representations in the context of a viewpoint-oriented approach to systems analysis and design, which acknowledges that there may often be multiple, possibly conflicting interpretations or \emph{perspectives} of the phenomenon being modelled. For example, the Chief Executive, marketing manager, sales personnel and accountant are likely to have different perspectives, each having correspondingly different descriptions of the business. A \emph{viewpoint} is the formalisation of a particular perspective \cite{East:SM:1991:PhD}, as shown at the top of Figure~\ref{Fig.Terminology}.
Viewpoints provide a useful context within which to discuss translations among multiple representations, so the author \cite{Stan:N:1999:PhD,Stan:N:1997:ECIS97,Stan:N:2000:dp2000-09} has developed the viewpoint-based framework shown in Figure~\ref{Fig.Terminology}. This framework was synthesised from earlier work by Finkelstein et al.~\cite{Fink:ACW:1989}, Easterbrook~\cite{East:SM:1991:PhD} and Darke~\& Shanks~\cite{Dark:P:1996:RE}.
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[htb]
\centering
\psset{unit=0.75cm}
\begin{pspicture}(15,15.35)
\rput[bl](0,0){\includegraphics[width=11.25cm,keepaspectratio]%
{\figures Terminology2}}
\rput(2.55,6.47){\includegraphics[width=1.875cm,keepaspectratio]%
{\figures MarksDFD}}
\rput(6,6.47){\includegraphics[width=1.875cm,keepaspectratio]%
{\figures MarksERD}}
\rput(12.95,6.47){\includegraphics[width=1.875cm,keepaspectratio]%
{\figures MarksFDD}}
\end{pspicture}
\caption{The viewpoint/representation/description framework}
\label{Fig.Terminology}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
As shown in Figure~\ref{Fig.Terminology}, a \emph{viewpoint} comprises one or more \emph{descriptions}, each expressed using a suitable \emph{representation}. A representation comprises two parts: a technique and a scheme. A representation's \emph{technique} specifies the generic \emph{constructs} of the representation, such as classes, relations and attributes. A representation's \emph{scheme} comprises constructs specialised from the generic constructs of the technique, and includes the `symbols' required to express these constructs; for example, boxes for UML classes, SQL \texttt{create table} statements for relations and so on. While a given technique may have several possible schemes, the combination of a particular technique and scheme forms a single representation. For example, SQL/92 and QUEL are two possible schemes that may be used in association with the relational technique, but the combinations $(Relational,$ $SQL/92)$ and $(Relational,$ $QUEL)$ form two distinct representations, as illustrated in Figure~\ref{Fig.Terminology}.
Representations must be instantiated in some way in order to describe a viewpoint. The instantiation of a representation can be thought of as a collection of `statements' that describe the viewpoint, and is thus referred here as a \emph{description} (the terms `model' or `schema' could perhaps be used, but these terms are somewhat ambiguous). The `statements' of a description are expressed by \emph{elements}, which can be thought of as instantiations of a representation's constructs; for example, the \textsf{Customer} actor in a use case diagram for a sales system (an instantiation of the \domain{Actor} construct), or the \textsf{Product} table in an SQL/92 schema definition (an instantiation of the \domain{Table} construct).
In practical terms, a representation can be thought of as the combination of a generic modelling approach (the technique) with a specific version of that approach (the scheme, which includes the notation used). The representation is then used to build descriptions of a particular viewpoint.
%================================================================================
\subsection{Abstract notation}
The author has developed an abstract notation for writing representation, description, construct and element expressions \cite{Stan:N:2000:dp2000-09}. The notation is derived from the data transfer notation of Pascoe~and Penny~\cite{Pasc:RT:1995}, and is summarised in Table~\ref{Tab.Notation}. (There are additional notations for specifying translations which are not used in this paper and have thus been omitted.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table*}[htb]
\centering
\caption{Summary of representation, description, construct and element notation}
\label{Tab.Notation}
\settowidth{\mra}{\BIGL[7mm]{Construct of a representation}}
\medskip\hrule\medskip
\begin{tabular}{clp{7.5cm}}
\textbf{Notation} & \textbf{Associated term} & \textbf{Definition} \\
\\
$V$ & Viewpoint \dotfill & A formalisation of a particular perspective on a real-world phenomenon. \\
\\
$T$ & Technique \dotfill & A collection of generic constructs that form a modelling `method', for example, the relational model or entity-relationship approach. \\
\\
$S$ & Scheme \dotfill & A collection of specialised constructs that form a specific modelling `notation' within a technique, for example, SQL/92 or Martin ERD notation. \\
\\
\Representation{R}{T}{S} or \Rep{R} & Representation \dotfill & Representation \Rep{R} comprises constructs defined by the combination of technique $T$ and scheme $S$. \\
\\
\Description{D_{i}}{V}{T}{S} or $D$ & Description \dotfill & Description $D_{i}$ of viewpoint $V$ is expressed using constructs of technique $T$ and scheme $S$. \\
\\
\construct{\Representation{R}{T}{S}}{con}, & \multirow{2}{\mra}{\BIGL[7mm]{Construct of a representation} \dotfill} & \multicolumn{1}{l}{\multirow{2}{7.5cm}{\domain{con} specifies a construct of representation \Representation{R}{T}{S}.}} \\
\Construct{R}{con}, or \domain{con} \\
\\
\Elementt{\Description{D_{i}}{V}{T}{S}}{e}{con}, & \multirow{2}{\mra}{\BIGL[7mm]{Element of a description} \dotfill} & \multicolumn{1}{l}{\multirow{2}{7.5cm}{$e$ specifies an element (instantiated from construct \domain{con}) of description \Description{D_{i}}{V}{T}{S}.}} \\
\Elementt{D_{i}}{e}{con}, or \Element{D_{i}}{e} \\
\end{tabular}
\medskip\hrule
\end{table*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The notation \Description{D_{i}}{V}{T}{S} denotes that description $D_{i}$ of viewpoint $V$ is expressed using constructs of technique $T$ and scheme $S$ (this may be abbreviated to $D_{i}$ when $V$, $T$ and $S$ are clear). Thus, \Description{D_{1}}{V_{p}}{\ER}{\Martin} denotes a description $D_{1}$ of the viewpoint $V_{p}$ that is expressed using constructs of the entity-relationship technique ($\ER$) and the Martin ERD scheme ($\Martin$) \cite{Mart:J:1990:IE2}.
The notation \Representation{R}{T}{S} denotes a representation \Rep{R} that comprises a collection of constructs defined by the combination of technique $T$ and scheme $S$ (this may be abbreviated to \Rep{R} when $T$ and $S$ are clear). Thus, \RepresentationS{R}{e}{\ER}{\Martin} denotes the representation \RepS{R}{e} formed by combining the constructs of the entity-relationship technique ($\ER$) with the Martin ERD scheme ($\Martin$).
Constructs are the fundamental components of a representation, whereas elements are the fundamental components of a description. Given a representation \Representation{R}{T}{S}, a construct \domain{con} of \Rep{R} is denoted by \construct{\Representation{R}{T}{S}}{con}, or, if $T$ and $S$ are clear, simply \Construct{R}{con}. Often \Rep{R} may also be clear from the context, allowing the \Construct{R}{} notation to also be omitted, leaving just \domain{con}. The name of the construct is denoted by \textsc{small caps}. For example, the regular entity construct of the representation \RepresentationS{R}{e}{\ER}{\Martin} is denoted by \construct{\RepresentationS{R}{e}{\ER}{\Martin}}{RegularEntity} or \Construct{R_{e}}{RegularEntity}.
The construct \domain{con} can be thought of as analogous to the concept of a relational domain in that it specifies a pool of possible `values' from which an element $e$ may be drawn. The notation $e:\domain{con}$ is used to denote that $e$ is a member of the set of all possible elements corresponding to the construct \domain{con}.
Now consider a description \Description{D_{i}}{V}{T}{S}. An element $e$ of $D_{i}$ (instantiated from construct \construct{\Representation{R}{T}{S}}{con}) is denoted by \Elementt{\Description{D_{i}}{V}{T}{S}}{e}{con}, or, if $V$, $T$ and $S$ are clear, simply \Elementt{D_{i}}{e}{con}. The construct may also be omitted if it is clear from the context, that is, \Element{D_{i}}{e}. For example, the \textsf{Customer} regular entity of the description \Description{D_{1}}{V}{\ER}{\Martin} is denoted by \Elementt{\Description{D_{1}}{V}{\ER}{\Martin}}{\mathit{customer}}{RegularEntity} or \Element{D_{1}}{\mathit{customer}}.
%================================================================================
\section{Translating descriptions among representations}
\label{Sec:Translating}
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[b]
\centering
\psset{linecolor=lightgray,linewidth=2pt,arrows=->,unit=0.55}
\subfigure[Source FDD \Description{D_{1}}{V_{\mathit{staff}}}{\FD}{\SmithS}
\protect\label{Fig.Translating.Heuristic.FDD}]%
{ \begin{minipage}{11cm}
\centering
\begin{pspicture}(10.3,7.9)
\rput[bl](0.1,0){\includegraphics[scale=0.55]{\figures Heuristic-FDD}}
\psframe(0.2,4.1)(1.2,5.1) % box 1
\psframe(0,1.2)(1.4,5.3) % box 2
\pnode(0.2,4.6){FB1}
\pnode(1.4,3.8){FB2}
\end{pspicture}
\end{minipage}
} % subfigure
\\
\hfill
\subfigure[\protect\centering Target ERD \protect\linebreak
\Description{D_{2}}{V_{\mathit{staff}}}{\ER}{\Martin}
\protect\label{Fig.Translating.Heuristic.ERDR}]%
{ \begin{pspicture}(12.8,6)
\rput[bl](0,0){\includegraphics[scale=0.55]{\figures Heuristic-ERDR}}
\pnode(3,5.1){EB1}
\end{pspicture}
} % subfigure
\hfill
\subfigure[\protect\centering Target ERD \protect\linebreak
\Description{D_{3}}{V_{\mathit{staff}}}{\ER}{\Martin}
\protect\label{Fig.Translating.Heuristic.ERDH}]%
{ \begin{pspicture}(12.8,6)
\rput[bl](0,0){\includegraphics[scale=0.55]{\figures Heuristic-ERDH}}
\psframe(1.1,1.6)(11.7,4.4)
\pnode(10,4.4){EB2}
\end{pspicture}
} % subfigure
\hfill \mbox{}
\nccurve[angleA=180,angleB=90]{FB1}{EB1}
\nbput[nrot=:D,labelsep=2pt]{\scriptsize \emph{rule}}
\nccurve[angleB=90]{FB2}{EB2}
\naput[nrot=:U,labelsep=2pt,npos=0.66]{\scriptsize \emph{heuristic}}
\caption{Example of applying a heuristic}
\label{Fig.Translating.Heuristic}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
A representation comprises a collection of constructs that are instantiated to form the elements of descriptions. The translation of a description from a source representation \RepS{R}{s} to a target representation \RepS{R}{t} can therefore be decomposed into a collection of translations of the elements that make up the description. The translation of one or more elements of a source description to one or more elements of a target description is defined by a \emph{rule} that specifies a mapping from a collection of constructs of \RepS{R}{s} to some collection of constructs of \RepS{R}{t} \cite{Atze:P:1995:Lattice,Atze:P:1996:EDBT}. This mapping may have constraints that specify pre- and post-conditions for elements translated by the rule. Pre-conditions ensure that a rule is applied only to appropriate source elements. Post-conditions enforce the semantics of the target representation by ensuring that elements generated by a rule make sense in the context of the target representation. Both pre- and post-conditions are referred to here as \emph{invariants} \cite{Amor:R:1997:PhD}, as a pre-condition when a rule is applied in one direction (`left-to-right') can become a post-condition when the rule is applied in the opposite direction (`right-to-left').
The application of a rule should always result in a target structure that is semantically consistent with the source description, but in general it is unlikely that a set of rules can be defined to map completely from \RepS{R}{s} to \RepS{R}{t}. This is because some constructs of \RepS{R}{s} may not be directly mappable onto constructs of \RepS{R}{t}, or vice-versa. This mismatch can sometimes be ameliorated by use of \emph{heuristics}, which are similar to rules except that the application of a heuristic will \emph{generally} result in a target structure that is semantically consistent with the source, but not always. Heuristics can be thought of as `rules of thumb' that usually but not always produce the correct result.
Rules generally only translate the structure or syntax of a description. Heuristics also translate structure, but can also affect the semantics of the encompassing viewpoint by making explicit semantics that may be implicit in the original description. Consider the functional dependency description \Description{D_{1}}{V_{\mathit{staff}}}{\FD}{\SmithS} expressed using Smith's notation \cite{Smit:HC:1985,Stan:N:1999:Smith} and shown in Figure~\ref{Fig.Translating.Heuristic.FDD}. This description has a collection of domain flag elements that all reference the same attribute element (\textsf{IRD\_NUMBER}). Now suppose there is a rule specifying that a \domain{DomainFlag} construct maps to a \domain{Relationship} construct in an ERD. The description \Description{D_{2}}{V_{\mathit{staff}}}{\ER}{\Martin} that results from applying this rule is shown in Figure~\ref{Fig.Translating.Heuristic.ERDR}. Examining $D_{2}$, it is apparent that the \textsf{Salary\_staff}, \textsf{Wage\_staff} and \textsf{Salesrep} entities are actually subtypes of the \textsf{Staff} entity. A rule cannot be defined to this effect, however, because a domain flag does not always imply a type hierarchy.
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[b]
\centering
\setlength{\unitlength}{1mm}
\thinlines
\subfigure[Disjoint \protect\label{Fig.MultipleRepresentations.Overlaps.Disjoint}]%
{ \begin{picture}(70,20)
\multiput(15,10)(40,0){2}{\ellipse{30}{20}}
\put(15,10){\makebox(0,0){\RepS{R}{p}}}
\put(55,10){\makebox(0,0){\RepS{R}{q}}}
\end{picture}
} % subfigure
\qquad
\subfigure[Intersecting \protect\label{Fig.MultipleRepresentations.Overlaps.Intersecting}]%
{ \begin{picture}(50,20)
\multiput(15,10)(20,0){2}{\ellipse{30}{20}}
\put(10,10){\makebox(0,0){\RepS{R}{p}}}
\put(40,10){\makebox(0,0){\RepS{R}{q}}}
\end{picture}
} % subfigure
\\
\subfigure[Inclusive \protect\label{Fig.MultipleRepresentations.Overlaps.Inclusive}]%
{ \begin{picture}(30,20)
\put(15,10){\ellipse{30}{20}}
\put(19,10){\ellipse{18}{12}}
\put(5,10){\makebox(0,0){\RepS{R}{p}}}
\put(19,10){\makebox(0,0){\RepS{R}{q}}}
\end{picture}
} % subfigure
\qquad
\subfigure[Equivalent \protect\label{Fig.MultipleRepresentations.Overlaps.Equivalent}]%
{ \begin{picture}(30,20)
\put(15,10){\ellipse{30}{20}}
\put(10,10){\makebox(0,0){\RepS{R}{p}}}
\put(20,10){\makebox(0,0){\RepS{R}{q}}}
\end{picture}
} % subfigure
\caption{Four categories of expressive overlap}
\label{Fig.MultipleRepresentations.Overlaps}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
Instead, a heuristic could be defined that specifies a mapping from a collection of \domain{DomainFlag} constructs to a \domain{TypeHierarchy} construct. The likelihood of this being the correct interpretation increases as the number of domain flags referencing the attribute increases. A reasonable assumption is that if three or more domain flags reference the same attribute, they should be mapped to a type hierarchy (this would be defined as an invariant on the heuristic). The result of applying such a heuristic is shown in Figure~\ref{Fig.Translating.Heuristic.ERDH}. Compare $D_{2}$ and $D_{3}$ --- without the heuristic, the type hierarchy implicit in $D_{1}$ and $D_{2}$ would not be drawn out in $D_{3}$. This heuristic will of course not always apply, but will usually produce the correct result.
In effect, the application of heuristics can cause an increase in the explicit semantic content of a viewpoint, by drawing out semantics that are implicit in the source description. Thus, in the example shown in Figure~\ref{Fig.Translating.Heuristic}, the explicit semantic content of the viewpoint is increased by making explicit the type hierarchy implicit in the source FDD.
In summary, the translation of a description from one representation to another can be decomposed into a collection of translations of elements. These element translations are defined by a collection of rules and heuristics, which specify mappings between collections of constructs in the source and target representations. Rules always produce semantically consistent results, whereas heuristics can sometimes produce semantically inconsistent results. A simple prototype system called \emph{Swift} has been implemented that demonstrates use of rules and heuristics in description translations \cite{Stan:N:1997:APSEC97,Stan:N:1997:dp9708}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Translation quality}
\label{Sec:MultipleRepresentations:ExpressivePower}
Every representation has boundaries to what may be expressed using the constructs of that representation. This is referred to here as the \emph{expressive power} of a representation, and covers the constructs of a representation and any semantic constraints that may exist between constructs. Representations may overlap in terms of expressive power, such that some subset of the constructs of one representation can be mapped to constructs of another representation. This concept is referred to here as the \emph{expressive overlap} between two representations.
The nature of the expressive overlap between a particular pair of representations \RepresentationS{R}{p}{T_{i}}{S_{j}} and \RepresentationS{R}{q}{T_{k}}{S_{l}} can fall into one of four categories, as illustrated in Figure~\ref{Fig.MultipleRepresentations.Overlaps}.
The four categories of expressive overlap are:
\begin{description}
\item[Disjoint] There is no expressive overlap between \RepS{R}{p} and \RepS{R}{q}, as shown in Figure~\ref{Fig.MultipleRepresentations.Overlaps.Disjoint}, and translating descriptions between them is therefore typically impossible.
\item[Intersecting] There is a partial expressive overlap between \RepS{R}{p} and \RepS{R}{q}, as shown in Figure~\ref{Fig.MultipleRepresentations.Overlaps.Intersecting}, and it is therefore possible to partially translate descriptions from \RepS{R}{p} to \RepS{R}{q}, and vice versa.
\item[Inclusive] One representation is contained entirely within the other, for example, \RepS{R}{p} contains \RepS{R}{q} in Figure~\ref{Fig.MultipleRepresentations.Overlaps.Inclusive}. Anything that can be expressed using constructs of \RepS{R}{q} may also be expressed using constructs of \RepS{R}{p}, but not vice versa. It is therefore possible to translate descriptions completely from \RepS{R}{q} to \RepS{R}{p}, but only partially from \RepS{R}{p} to \RepS{R}{q}.
\item[Equivalent] Anything that can be expressed using constructs of \RepS{R}{p} can also be expressed using constructs of \RepS{R}{q}, and vice versa, as shown in Figure~\ref{Fig.MultipleRepresentations.Overlaps.Equivalent}. It is therefore possible to translate descriptions completely in either direction.
\end{description}
The \emph{quality} of a translation is defined as how completely it maps constructs from the source representation to the target representation \cite{Pasc:RT:1990}. The expressive overlap of a pair of representations determines the maximum amount of information that may be translated from one representation to the other, and hence the maximum quality of any translation between those representations. The intersecting and inclusive categories are of the most interest, because translating a description from a more expressive representation to a less expressive one can result in a `loss' of information, whereas the reverse translation can result in the need to `gain' information during the translation in order to build a sensible target description.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Improving translation quality}
\label{Sec:Translating:Improving}
In an environment that facilitates the use of multiple representations, information loss may not be as great a concern as it is in more typical data translation problems. This is because the information that is `lost' during a description translation is still held in the source description. All descriptions will presumably be held in the same repository, so it may be possible to `restore' information that is `lost' during a translation when the translation is applied in the reverse direction. For instance, if the data flow description \Description{D_{1}}{V}{\DF}{\Gane} is translated into the functional dependency description \Description{D_{2}}{V}{\FD}{\SmithS}, the names of data stores may not be translated because of differences in the expressive powers of the two representations. The data store names still exist in $D_{1}$, however, so if $D_{2}$ is at some later stage used to incrementally update $D_{1}$, or translated to a new DFD $D_{3}$, then it is in principle possible to extract the data store names from the original $D_{1}$. This would require some means of tracking the translation `history' of descriptions.
A less obvious concern that arises when performing description translations is that it may be necessary to `gain' information that does not already exist when performing a translation. For example, when translating from a functional dependency description to an entity-relationship description, the names of the entities that are created must be generated or acquired in some way. This sort of situation would most commonly occur with inclusive representations when translating a description from the `contained' representation to the `containing' representation, but could also occur with intersecting representations.
Information `gain' is a particular issue with translations among representations with different techniques, as the expressive powers of two representations with different techniques are more likely to be divergent than the expressive powers of two representations that share the same technique. The effect will be less severe in translations that change only the scheme.
The problem is determining what information can and cannot be generated automatically during a translation, and why. Information that cannot be automatically generated and that is essential to build a syntactically correct target description (such as the names of tables in SQL) must be acquired somehow, otherwise it will not be possible to complete the translation. One way to improve the quality of a translation would therefore be to acquire information from the developer in some way. This process of acquiring information is termed \emph{enrichment}, and may occur before, during and after a translation.
Enrichment performed before a translation (`pre-enrichment') involves pre-po\-pu\-la\-ting the viewpoint with information that will be useful to the target description, and is analogous to Su~\& Fang's~\cite{Su:SYW:1993} notion of modifying and extending the semantics of a schema before translating it. For example, before translating from an FDD to an ERD, template entities with appropriate names but no attributes could be created by the developer, to filled in later by the translation.
Enrichment performed during a translation requires the developer to at least supply any information that is essential to properly build the target description, and that has not already been supplied. Using the same example as above, if entity names were not defined prior to the translation, then the developer would be requested to enter suitable names for each entity as it was generated by the translation. Non-essential information could also be included at this stage.
Enrichment after a translation (`post-enrichment') involves adding any remaining missing information that was not automatically generated during the translation or entered prior to the translation. In effect, the developer is refining the resultant description.
Another way to improve the quality of a translation is the application of heuristics. Heuristics allow the \emph{automatic} translation of more information than would normally be possible using rules, by drawing out semantics that are implicit in the source description, as noted in the previous section. Adding heuristics can reduce the amount of enrichment that is required, and produces an improvement in translation quality, as less information is lost or needs to be gained during the translation.
An important issue with use of heuristics is that they may sometimes produce semantically inconsistent results, which could result in an invalid viewpoint. This issue will typically arise when heuristics are applied without regard to the context in which they are being applied. That is, semantically inconsistent results will be produced in cases where the heuristic was not appropriate and should not have been applied. The applicability of a particular heuristic, however, will typically be difficult (if not impossible) to determine in an automatic manner. Fortunately, the enrichment process provides a practical solution to this issue. Rather than applying heuristics regardless of context, the developer can be notified that a heuristic is about to be applied and what the result of applying the heuristic will be. The developer can then use their contextual and semantic knowledge of the viewpoint to determine whether this is a correct result, and thus choose whether or not the heuristic should be applied.
Heuristics can increase the explicit semantic content of a viewpoint, so ensuring that heuristics are manually activated provides the benefit of making the developer aware of the semantic changes that are occurring during the translation. This process may also help identify possibilities that the developer may not otherwise have considered, thus promoting a more complete understanding by the developer of the phenomenon being modelled.
Both heuristics and enrichment have been implemented in the Swift prototype mentioned earlier, and have been found informally to produce improvements in translation quality. It would be useful, however, to actually measure such quality gains. In the next section is described a preliminary metric for measuring relative translation quality, which has been used to show that heuristics can produce improvements in translation quality \cite{Stan:N:1999:PhD}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Measuring relative translation quality}
\label{Sec:Measuring}
In order to determine whether use of heuristics has an impact on translation quality, the author is developing metrics for measuring translation quality. An overview of a preliminary metric is presented here.
Hull's concept of \emph{relative information capacity} \cite{Hull:R:1986:SIAM} provides a basis for comparing the information content of schemas in the context of schema integration, and Miller's \emph{schema intension graphs} \cite{Mill:RJ:1994:CS-TR-94-1185} are a tool that may be used to determine the relationship between the relative information capacities of two schemas. Representation definitions can be interpreted as a form of schema, so relative information capacity may also be applied to representations. In particular, the author has found that the expressive power of a representation can be characterised by the information capacity of its definition. Consequently, schema intension graphs may be used to determine the category of expressive overlap between two representations, providing a relative measure of translation quality.
Schema intension graphs provide an alternate graphical representation for describing schemas, and comprise:
\begin{itemize}
\item a collection of nodes representing typed domains (that is, sets of data values);
\item a collection of labelled edges representing binary relations between domains; and
\item annotations on the edges that represent simple constraints on the binary relations.
\end{itemize}
In Figure~\ref{Fig.SIGExample} is shown an example of a schema intension graph (SIG) that corresponds to an entity-relationship diagram of a used cars business.
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[htb]
\centering
\hfill
\subfigure[\Description{D_{1}}{\UsedCars}{\ER}{\Martin}
\protect\label{Fig.Measuring.SIGExample.ERD}]%
{ \begin{minipage}[c]{0.45\textwidth}
\centering
\includegraphics[scale=0.5]{\figures UsedCarsERD}
\end{minipage}
}
\hfill
\subfigure[Corresponding SIG $G_{D_{1}}$ \protect\label{Fig.Measuring.SIGExample.SIG}]%
{ \begin{minipage}[c]{0.45\textwidth}
\centering
\includegraphics[scale=0.5]{\figures SIGExample}
\end{minipage}
}
\hfill
\caption{Example of a schema intension graph}
\label{Fig.SIGExample}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
It is possible to determine the relationship between the relative information capacities of two schemas by comparing SIGs for the two schemas. Intuitively, if two SIGs are isomorphic, then the corresponding schemas are equivalent \cite{Mill:RJ:1994:CS-TR-94-1185}. An isomorphism occurs between two SIGs when the graphs are structurally identical and corresponding nodes in the two SIGs have compatible semantics. Isomorphisms may also be achieved by performing various equivalence preserving and information capacity augmenting transformations on one of the SIGs \cite{Mill:RJ:1994:IS19-1}.
The information capacity of a schema determines the set of all valid instances of that schema within the context of the phenomenon that it models \cite{Mill:RJ:1994:PhD}. A schema defines a set of valid database structures for a given phenomenon. Combined with the set of of all data relating to the phenomenon, the schema may be used to generate all possible database states for the phenomenon. By extension, the information capacity of a representation definition determines the set of all valid descriptions that may expressed using the representation; that is, it determines the extent of what may be expressed using that representation. This is effectively identical to the notion of expressive power introduced in Section~\ref{Sec:MultipleRepresentations:ExpressivePower}. That is, the expressive power of a representation can be characterised by the information capacity of the representation's definition. This means that SIGs may be used to determine any relationship between the expressive powers of two representations, and thus the nature of the expressive overlap between those representations, which in turn gives an indication of the maximum quality of any translations between those representations.
Given two representations \RepresentationS{R}{p}{T_{1}}{S_{1}} and \RepresentationS{R}{q}{T_{2}}{S_{2}}, the expressive overlap of the pair can be categorised by building SIGs corresponding to the definitions of the two representations, and comparing them as follows:
\begin{itemize}
\item If the two SIGs are isomorphic, or one SIG can be transformed by a series of equivalence preserving transformations to be isomorphic to the other, then the expressive powers of \RepS{R}{p} and \RepS{R}{q} are equivalent.
\item If the two SIGs are not isomorphic, but the SIG for \RepS{R}{p} can be transformed by a series of information capacity augmenting transformations to be isomorphic to the SIG for \RepS{R}{q}, then the expressive power of \RepS{R}{q} is inclusive of that of \RepS{R}{p} (or vice versa).
\item If the two SIGs are not isomorphic, but one or more subgraph(s) of the SIGs are either isomorphic, or can be transformed to be isomorphic, then \RepS{R}{p} and \RepS{R}{q} have an intersecting expressive overlap.
\item If the two SIGs are not isomorphic, and no subgraphs of the SIGs are isomorphic and cannot be transformed to be isomorphic, then \RepS{R}{p} and \RepS{R}{q} have a disjoint expressive overlap.
\end{itemize}
The author has used these concepts to develop a preliminary metric that provides a relative measure of translation quality \cite{Stan:N:1999:PhD}. SIGs are built for both the source and target representations, and the extent of overlap is calculated by tagging nodes and edges in each SIG corresponding to constructs that are mapped by the translation. These then counted to provide an indication of the relative quality of the translation. An example of this approach is shown in Figure~\ref{Fig.Metric} for the translation from \RepresentationS{R}{f}{\FD}{\Smith} to \RepresentationS{R}{e}{\ER}{\Martin} (tagged nodes and edges are shown in \emph{\textbf{bold italic}}).
%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[htb]
\centering
\subfigure[Source: \RepresentationS{R}{f}{\FD}{\SmithS}]
{ \includegraphics[scale=0.5]{\figures Tagged-FDDERD-FDDsrc}
} % subfigure
\\
\subfigure[Target: \RepresentationS{R}{e}{\ER}{\Martin}]
{ \includegraphics[scale=0.5]{\figures Tagged-FDDERD-ERDtgt-H}
} % subfigure
\caption{Applying the relative translation quality metric}
\label{Fig.Metric}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%
This metric has been successfully used by the author to show that use of heuristics has a positive impact on the quality of translations, but unfortunately the metric is only useful for comparing the \emph{relative} quality of two or more translations. It does not provide a quantitative measure of translation quality, so further research is required.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Summary}
\label{Sec:Translating:Summary}
There are many diverse types of information to be modelled when building an information system, so it is sensible to use multiple representations to describe real-world phenomena. The author has developed an approach to facilitating the use of multiple representations within a single viewpoint by translating descriptions of the viewpoint among different representations. An important issue with such translations is their \emph{quality}, or how well they map constructs of one representation to constructs of another representation. In this paper were proposed two methods of improving translation quality, \emph{heuristics} and \emph{enrichment}.
Heuristics improve translation quality by automatically translating information that could not normally be translated. In particular, heuristics can draw out implied semantics from the source description, and make them explicit in the target description. Heuristics may, however, sometimes produce incorrect results.
Enrichment improves translation quality by eliciting additional information from the developer that cannot be generated automatically. Enrichment may occur before, during and after a translation.
Also described was a preliminary metric for comparing the relative quality of translations. Relative information capacity can be used to characterise the expressive power of a representation. Schema intension graphs can therefore be used to determine the expressive overlap between two representations and hence the maximum quality of translations among those representations. % This metric has been used to show that heuristics can improve translation quality, but further work is required to make the metric more effective.
\bibliographystyle{ieeetr}
\bibliography{:::Biblio}
\end{multicols}
\end{document}
