\def\filedate{1998/07/06}
\def\docdate{1997/07/06}
\def\fileversion{1.0}
\def\basename{spectrum}

\documentclass{article}
\makeatletter
\input{dvips.def}
\input{dvipsone.def}
\makeatother
\usepackage{spectrum}
\usepackage{pstricks,pst-node}
\begin{document}

\title{\fadeletters[70][0]{Spectre}\black}
 \author{Wolfgang May\\
 Institut f\"ur Informatik, \\
 Universit\"at Freiburg \\
 Am Flughafen 17 \\
 D-79110 Freiburg\\
 Federal Republic of Germany \\
 \small\texttt{may@informatik.uni-freiburg.de}}
 \date{\filedate}

\maketitle

\begin{abstract}
  The \specletters[50][70]{Spectre}\black\ style allows 
  \specletters[0][100]{running colors}\black\ or 
  \fadeletters[10][80]{fading out}\black\ and
  \fadeletters[80][10]{fading in}\black\ in a text.
  In addition to change the color with every letter, it is possible
  to change it with every word, every \emph{group}, every line,
  or with every line in a tabular. The style requires the dvips
  package.
\end{abstract}

\section{The User-Interface}
\black
The following table is typeset by ...
\footnote{\specwords[50][80]{In Germany, the last three teams are
    relegated. Kaiserslautern managed to be re-promoted the subsequent
    year and become champion two years later.}}
\specwords[50][80]{In Germany, the last three teams are
    relegated. Kaiserslautern managed to be re-promoted the subsequent
    year and become champion two years later.}

\begin{spectabular}[38][-2][t]{l|l|rrrrrr}
 1. BV 09 Borussia Dortmund   & 34 & 19 & 11 &  4 &  76-38 &  +38 & 68 \\
 2. FC Bayern M\"unchen       & 34 & 19 &  5 & 10 &  66-46 &  +20 & 62 \\
 3. FC Schalke 04             & 34 & 14 & 14 &  6 &  45-36 &  + 9 & 56 \\
 4. Borussia M\"onchengladbach &34 & 15 &  8 & 11 &  52-51 &  + 1 & 53 \\
 5. Hamburger SV              & 34 & 12 & 14 &  8 &  52-47 &  + 5 & 50 \\
 6. FC Hansa Rostock          & 34 & 13 & 10 & 11 &  47-43 &  + 4 & 49 \\
 7. Karlsruher SC             & 34 & 12 & 12 & 10 &  53-47 &  + 6 & 48 \\
 8. TSV M\"unchen 1860        & 34 & 11 & 12 & 11 &  52-46 &  + 6 & 45 \\
 9. SV Werder Bremen          & 34 & 10 & 14 & 10 &  39-42 &  - 3 & 44 \\
10. VfB Stuttgart             & 34 & 10 & 13 & 11 &  59-62 &  - 3 & 43 \\
11. SC Freiburg               & 34 & 11 &  9 & 14 &  30-41 &  -11 & 42 \\
12. 1. FC K\"oln              & 34 &  9 & 13 & 12 &  33-35 &  - 2 & 40 \\
13. TSV Fortuna D\"usseldorf  & 34 &  8 & 16 & 10 &  40-47 &  - 7 & 40 \\
14. TSV Bayer 04 Leverkusen   & 34 &  8 & 14 & 12 &  37-38 &  - 1 & 38 \\
15. FC St. Pauli Hamburg      & 34 &  9 & 11 & 14 &  43-51 &  - 8 & 38 \\
16. 1. FC Kaiserslautern      & 34 &  6 & 18 & 10 &  31-37 &  - 6 & 36 \\
17. Eintracht Frankfurt       & 34 &  7 & 11 & 16 &  43-68 &  -25 & 32 \\
18. Krefelder FC Uerdingen    & 34 &  5 & 11 & 18 &  33-56 &  -23 & 26 \\
\end{spectabular}


WORDS:

\specwords[60][100]{eins zwei drei vier fuenf}

\fadewords[0][60][+5]{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}

\specwords[0][90]{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}

EXPRESSIONS:

\specexpr[60][+5]{{alpha beta} {gamma delta} e {f g} h}

\specexpr[0][90]{{alpha beta} {gamma delta} e {f g} h}

\specexpr{{alpha beta} {gamma delta} e {f g} h}

\black
LETTERS:

\specletters{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}



\fadeletters{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}

\specletters[0][90]{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}

\specletters[70][+1]{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}

\specletters[\spectrumcolorval][-1]{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}

\specletters[90][+10]{T r a c i n g this concept one step further, also the initial states of procedures are not total interpretations, but their extension is inherited from the state-as-is interpretation of the calling state.}
\thispagestyle{empty}


\speclines[0][80][+5] Referential actions are specialized triggers used
to automatically maintain referential integrity.  While their local
behavior can be grasped easily, it is far from clear what the combined
effect of a set of referential actions, i.e., their global semantics
should be.  For example, different execution orders may lead to
ambiguities in determining the final set of updates to be applied.  To
resolve these problems, we propose an abstract logical framework for
rule-based maintenance of referential integrity: First, we identify
desirable abstract properties like \emph{admissibility} of updates
which lead to a 
non-constructive global semantics of referential
actions. We obtain a constructive definition by formalizing a set of
referential actions $RA$ as logical rules, and show that the
declarative semantics of the resulting logic program $P_{RA}$ captures
the intended abstract semantics: The well-founded model of $P_{RA}$
yields a unique set of updates, which is a safe, sceptical
approximation of the set of all maximal admissible updates; the third
truth-value \emph{undefined} is assigned to all controversial updates.
Finally, we show how to obtain a characterization of all maximal
admissible subsets of a given set of updates using certain maximal
stable models.
Finally, we show how to obtain a characterization of all maximal
admissible subsets of a given set of.

We study the following problem: Given a relational database $D$, a set
of user-defined update requests , and a set of referential
actions $RA$, find those sets of updates $\Delta$ which {(i)}
preserve referential integrity in the new database $D'$, {(ii)}
are maximal wrt.\, and {(iii)} reflect the intended
meaning of $RA$.


The problem is important both from a practical and theoretical point
of view: Referential integrity constraints are a
central concept of the relational database model and frequently used
in real world applications. \emph{Referential actions} (rac's) are
specialized triggers used to automatically maintain referential
integrity \cite{date-VLDB-81}.  While the \emph{local} behavior of
rac's is quite intuitive and easy to understand, it is far from clear
what their \emph{global semantics} should be. In particular, different
execution orders of rac's may lead to different outcomes, i.e.\ to
\emph{ambiguities} in determining the above $\Delta$ and $D'$.

Due to their practical importance, rac's have been included in the
SQL2 standard and SQL3 proposal \cite{SQL2,SQL3}.  However, the standards
describe the meaning of rac's in a lengthy and procedural way, making
it difficult to understand or predict their global behavior. The
problem of ambiguous global semantics is ``solved'' by fixing a rather
ad-hoc run-time execution model
\cite{horowitz-ICDE-92,cochrane-pirahesh-mattos-VLDB-96}. In a
different approach, \cite{markowitz-IS-94} presents safeness
conditions which aim at avoiding ambiguities at the schema level.
However, as shown in \cite{reinert-MISC-96}, it is in general
undecidable whether a database schema with rac's is ambiguous.
Summarizing, the problem is complex and, from a theoretical point of
view, has not been solved in a satisfactory way.
We study the following problem: Given a relational database $D$, a set
of user-defined update requests , and a set of referential
actions $RA$, find those sets of updates $\Delta$ which {(i)}
preserve referential integrity in the new database $D'$, {(ii)}
are maximal wrt.\, and {(iii)} reflect the intended
meaning of $RA$.


The problem is important both from a practical and theoretical point
of view: Referential integrity constraints are a
central concept of the relational database model and frequently used
in real world applications. \emph{Referential actions} (rac's) are
specialized triggers used to automatically maintain referential
integrity \cite{date-VLDB-81}.  While the \emph{local} behavior of
rac's is quite intuitive and easy to understand, it is far from clear
what their \emph{global semantics} should be. In particular, different
execution orders of rac's may lead to different outcomes, i.e.\ to
\emph{ambiguities} in determining the above $\Delta$ and $D'$.

Due to their practical importance, rac's have been included in the
SQL2 standard and SQL3 proposal \cite{SQL2,SQL3}.  However, the standards
describe the meaning of rac's in a lengthy and procedural way, making
it difficult to understand or predict their global behavior. The
problem of ambiguous global semantics is ``solved'' by fixing a rather
ad-hoc run-time execution model
\cite{horowitz-ICDE-92,cochrane-pirahesh-mattos-VLDB-96}. In a
different approach, \cite{markowitz-IS-94} presents safeness
conditions which aim at avoiding ambiguities at the schema level.
However, as shown in \cite{reinert-MISC-96}, it is in general
undecidable whether a database schema with rac's is ambiguous.
Summarizing, the problem is complex and, from a theoretical point of
view, has not been solved in a satisfactory way.

In contrast to previous work, we present an abstract logical framework
for rule-based maintenance of referential integrity: After introducing
a generic language for rac's, we identify general abstract properties
which a set of updates $\Delta$ wrt.\ a given set of rac's $RA$ may \\
possess (Section \ref{sec:referential-integrity}).  These abstract \\
properties give rise to a natural but non-constructive global \\
semantics.  To obtain a constructive definition, we associate with \\
every set of rac's $RA$ a \emph{logic program} $P_{RA}$ (Section
\ref{sec:rules}), and show that the declarative semantics of $P_{RA}$
captures the abstract semantics (Section \ref{sec:semantics}).  This
solves the above-mentioned problem in a rigorous and comprehensive
way.

\endspeclines \black
 
In contrast to previous work, we present an abstract logical framework
for rule-based maintenance of referential integrity: After introducing
a generic language for rac's, we identify general abstract properties
which a set of updates $\Delta$ wrt.\ a given set of rac's $RA$ may \\
possess (Section \ref{sec:referential-integrity}).  These abstract \\
properties give rise to a natural but non-constructive global \\
semantics.  To obtain a constructive definition, we associate with \\
every set of rac's $RA$ a \emph{logic program} $P_{RA}$ (Section
\ref{sec:rules}), and show that the declarative semantics of $P_{RA}$
captures the abstract semantics (Section \ref{sec:semantics}).  This
solves the above-mentioned problem in a rigorous and comprehensive
way.

In contrast to previous work, we present an abstract logical framework
for rule-based maintenance of referential integrity: After introducing
a generic language for rac's, we identify general abstract properties
which a set of updates $\Delta$ wrt.\ a given set of rac's $RA$ may \\
possess (Section \ref{sec:referential-integrity}).  These abstract \\
properties give rise to a natural but non-constructive global \\
semantics.  To obtain a constructive definition, we associate with \\
every set of rac's $RA$ a \emph{logic program} $P_{RA}$ (Section
\ref{sec:rules}), and show that the declarative semantics of $P_{RA}$
captures the abstract semantics (Section \ref{sec:semantics}).  This
solves the above-mentioned problem in a rigorous and comprehensive
way.


%\psset{linearc=0.15}
\psset{arrowsize=2pt 3}
\psset{nodesep=3pt}
\psset{linewidth=2pt}

\newcommand{\block}{\rule[0.12em]{0.45em}{0.4em}}
\newcommand{\lefta}{\Rnode{l}{}~~~\Rnode{r}{}\ncline{<-}{l}{r}}
\newcommand{\righta}{\Rnode{xl}{}~~~\Rnode{xr}{}\ncline{->}{xl}{xr}}



\paragraph{Spektrum von Datenbank-Regelsprachen}\ \bigskip

\noindent
\specexpr[25][95]
{{\emph{Deduktive Regeln}}\hfill 
 {\emph{Produktionsregeln}}\hfill
 {\emph{Aktive Regeln}}}\\\bigskip 
                                %
\specexpr[25][95]{{\textbf{deklarativ}}\hfill{\textbf{prozedural}}} \\\bigskip
                                %
{\psset{arrowsize=4pt 6}\psset{fillstyle=hlines}
\specexpr[25][95]{{\lefta}\block\block\block\block\block\block\block
\block\block\block\block\block\block\block\block\block\block\block
\block\block\block\block\block\block\block\block\block\block\block 
\block\block\block\block\block\block\block\block\block\block\block
\block\block\block\block\block\block\block\block\block\block\block
\block\block\block\block\block\block\block\block\block\block\block
\block\block\block\block\block\block\block\block\block\block\block
\block{\righta}}}\black\\\bigskip
                                %
\specexpr[25][95]
{{\begin{tabular}{@{}c@{}}
    S-Datalog\\
    WF-Datalog
  \end{tabular}}
  \dotfill
  {\begin{tabular}{@{}c@{}}
    RDL\\
    I-/P-Datalog
  \end{tabular}}
  \dotfill {A-RDL}\dotfill {Ariel} \dotfill {Starburst} \dotfill {Postgres}
  }


\end{document}
% Local Variables:
% TeX-command-default: "LaTeX"
% TeX-master: t
% End:
