\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: