Beispiele, Grammatik
und Semantische Probleme
der Anfragesprache fuer
das CSLIB-System

Status: Arbeitsunterlage bei der Entwicklung.
        KEINE verbindliche Spezifikation!

Adressaten: Entwickler der Anfragesprache und Suchmaschine und
            zukuenftige Anwender der Anfragesprache, welche sich ueber den
            aktuellen Stand informieren wollen (um eventuell das
            schlimmste noch zu verhindern:-).

Anderuengen:
19.12.95	Grammatik neu angefangen
		Datentypen fuer attributierten Strukturbaum angefangen
15.12.95	Nullwerte erweitert
13.12.95	Erste Version

Anmerkungen, Fragen usw. an pumuckel@cs.tu-berlin.de (Holger Westphal).
==============================================================================

Beispiele
---------
use 'CSLIB.IFB'.	% Importiere Modul fuer IFB-Bestand
use 'CSLIB.UB'.		% Importiere Modul fuer UB-Bestand
use 'CSLIB.UB-IFB'.	% Modul, welches UB und IFB vereinheitlicht
use 'CSLIB.Berlin'.	% Modul, welches Bibliothen in Berlin vereinheitlicht

define antwort1 ni D <<-
  D in dokument(dokumentart('Kongressband')).
redefine antwort1 = set of D where D in dokument(dokumentart('Kongressband')).
redefine antwort1 = dokument(dokumentart('Kongressband')).
cache antwort1.
uncache antwort1.

set of (autoren: autor(D), titel: titel(D)) where D in dokument, 
                                                  erscheinungsjahr(D) > 1990.
set of
  (autoren:
    (set of (vorname: vorname(A), nachname: nachname(A)) where A in autor(D)),
   titel: titel(D)) where D in dokument, titel(D) in ?'*[Dd]atenbank*'.
set of
  (autoren:
    (list of (nachn: nachname(A), stellung: stellung(A,D)) where A in autor(D)
                                     ordered by [(>,stellung)]),
   titel: titel(D)) where D in dokument, titel(D) in ?'*[Dd]atenbank*'.

ranklist of antwort1 ranked by D @ erscheinungsjahr(D) > 1990,
                                   wort('Datenbank') in wort(abstract(D)).
ranklist of (titel: titel(D), dok: D)
  where D in antwort1
  ranked by
    X @ erscheinungsjahr(dok(X)) > 1990,
    wort('Datenbank') in wort(abstract(dok(X))).

list of antwort1 ordered by [(>,erscheinungsjahr),(<,erscheinungsmonat)].
list of (titel: titel(D), dok: D) where D in antwort1 
                                  ordered by [(>,X @ erscheinungsjahr(dok(X)))].
list of (ti: titel(D), py: erscheinungsjahr(D)) where D in antwort1 
                                  ordered by [(>,X @ py(X))].

DML (optional)
--------------
for a new person do (
  P @ (assert nachname(P) = 'Haller', vorname(P) = 'Klaus')).
for a new person do (
  P @ (assert nachname(P) = 'Popst', vorname(P) = 'Hans')).
for a new dokument do (
  D @ (assert titel(D) = 'Katalogisierung nach den RAK-WB',
              (for a new isbn do I @ (assert nummer(I) = '3-598-10926-2'))
                 in isbn(D),
%              (a new isbn('3-598-10926-2')) in isbn(D),
              the person('Klaus','Haller') in autor(D),
              the person('Hans','Popst') in autor(D))).

for the (D where D in dokument, the isbn('3-598-10926') in isbn(D)) do
  D @ (assert ifbKlassifikation('53q345') in klassifikation(D)).

for (set of D where D in dokument, dokumentart(D) = dokumentart('Fakyr')) do
  D @ (assert titel(D) = cslibEncoding(titel(D)))

to assert titel(D as dokument) = T do
  sqlSetChar(D,`titel,new(T)).

to new isbn(I as int) do
  X @ (X = sqlNewTupleBySerial(`isbn,`id),
       assert nummer(X) = I).

Zeichenfolge, welche ein Wort der Sprache repraesentiert (Reader)
-----------------------------------------------------------------
Der Anwender uebergibt die Anfrage als Folge von Zeichen in einem
bestimmten Zeichensatz. Jedem Zeichen kann durch eine Adresse eine
eindeutige Position in der Zeichenfolge zugeordnet werden. Das
Adressierungsschema kann von Anwendung zu Anwendung variieren
(z.B. (Zeile,Spalte), (Index)). Zeichen, welche nicht im Zeichensatz
des Anwenders darstellbar sind, werden durch eine (mnemotechnische)
Ersatzdarstellung referenziert (Adressierung solcher 'komplexen'
Zeichen in der Zeichenfolge?), welche aus mehreren Zeichen
aus dem Zeichensatz besteht, den der Anwender benutzt. Alle Zeichen und
Ersatzdarstellungen werden entsprechend einer Konvertierungsfunktion in die
interne Repraesentation des Zeichens, welches sie bedeuten, uebersetzt.

Beispiel (der Anwender kann z.B. nur ASCII-Texte eingeben):

set of D where
  D in sch&o:neLiteratur,
  "M&u:ller" in autorenNachnamen(D)

Korrespondierende Zeichenliste:

[character(0x73,'s',smallLetter,rowCol(1,1)), ...,
 character(0xf6,'&o:',smallLetter,rowCol(2,11)), ...]

?-defvariant(characterLocation,[
    rowCol(line,column),
    index(position),
    noLocation]).

?-defvariant(characterClass,[
    smallLetter, capitalLetter, graphic, digit, whiteSpace]).

?-defstruct(character(
    unicode,
    cslibEncoding,
    class -: characterClass,
    position -: characterLocation)).

Probleme: Die Bestimmung der Zeichenklasse (SmallLetter, CapitalLetter,
Graphic, ...) fuer den Scanner wird sehr aufwendig (Ist ein 'Lambda' nun
ein Graphics oder ein CapitalLetter? Was sind alles White-Spaces?)

Regulaerer Teil der Grammatik von QueRist (Scanner)
---------------------------------------------------
(Wird angewendet auf Zeichenfolge.)
Name --> SmallLetter, OptionalLetterOrDigitOrUnderlineSeq.
%Name --> Graphic, OptionalGraphicOrLetterOrDigitSeq.
Name --> "'", MetaSinglequotedSeq, "'".
VarName --> CapitalLetterOrUnderLine, OptionalLetterOrDigitOrUnderlineSeq.
Symbolic  --> Graphic, OptionalGraphicOrLetterSeq.
%Operator --> NameOrSymbolic(Name),{optable(Name,Type,Asso,Prio)}.
  % Diese allgemeine Repraesentation von Operatoren verhindert vermutlich
  % den Einsatz eines Parser-Generators. Deshalb 3 Tokenklassen:
PrefixOperator --> NameOrSymbolic(Name),{optable(Name,prefix,Asso,Prio)}.
InfixOperator --> NameOrSymbolic(Name),{optable(Name,infix,Asso,Prio)}.
PostfixOperator --> NameOrSymbolic(Name),{optable(Name,postfix,Asso,Prio)}.
  % Die Beachtung der Assoziativitaeten und Prioritaeten wuerde eine
  % nachtraegliche Analyse und ggf. Transformation des Ableitungsbaumes
  % notwendig machen. Problem: als Operatoren definierte Namen oder Symbole
  % werden nur noch als Operatoren erkannt. Um sie gleichzeitig als Namen oder
  % Symbole verwenden zu koennen, muss es zwei Arten von quotierten
  % Token geben: Namen UND Symbolics. Dann kann man aber nichts als
  % Namen verwenden, was auch Graphics enthaelt.
StringLiteral --> """", OptionalMetaDoublequotedSeq, """".
IntLiteral --> DigitSeq(Literal).
FloatLiteral --> DigitSeq,".",DigitSeq,OptionalExponent.

?-defvariant(qrToken,[
  name(value,begin,end),
  varname(value,begin,end),
  symbolic(value,begin,end),
%  operator(value,type,associativity,priority,begin,end), s.o.
  prefixOperator(value,associativity,priority,begin,end),
  infixOperator(value,associativity,priority,begin,end),
  postfixOperator(value,associativity,priority,begin,end),
  stringliteral(value,begin,end),
  intliteral(value,begin,end),
  floatliteral(value,begin,end)]).

Token --> Name.
Token --> VarName.
Token --> Symbolic.
Token --> Operator.
Token --> StringLiteral.
Token --> IntLiteral.

TokenSeq --> Token, OptionalWhiteSpace, TokenSeq.
TokenSeq --> [].

Kontextfreier Teil der Grammatik von QueRist (Struktur-Parser)
--------------------------------------------------------------
(Wird angewandt auf Ergebnis von TokenSeq = Liste von Token.)

TopLevel --> Expression.

Expression --> SetOf.
Expression --> ListOf.
Expression --> [symbolic('(')],Expression,[symbolic(')')].
Expression --> Name.
Expression --> Variable.
Expression --> Application.
%Expression --> PrefixApplication.
%Expression --> InfixApplication.
%Expression --> PostfixApplication.
%Expression --> Concatenation.		% fuer Zeichenmasken
Expression --> StringLiteral.
Expression --> IntLiteral.
Expression --> FloatLiteral.
Expression --> SetConstruction.
Expression --> ListConstruction.
Expression --> TupleConstruction.
Expression --> WithinEval.

SetOf --> [name(set),name(of)],Lambda.
ListOf --> [name(list),name(of)],Lambda,[name(ordered),name(by)],SortSpec.
Lambda --> VarTuple,[name(where)],Formula.
Formula --> [name(exists)],VarTuple1,[name(such),name(that)],Formula.
Formula --> [name(for),name(all)],VarTuple1,[name(holds)],Formula.
Formula --> Formula1,Disjunctor,Formula.
Formula --> Formula1.
Formula1 --> Formula2,Konjunctor,Formula1.
Formula1 --> Formula2.
Formula2 --> Negator,Atom.
Formula2 --> Atom.
Formula2 --> [symbolic('(')],Formula,[symbolic(')')].
Atom --> Term,[name(in)],ApplicationOrName. % Term
Atom --> Term,[name(is)],ApplicationOrName. % Term
Term --> Expression.
Name --> [name(Name)].
Name --> [name(Name),symbolic(':')],TypExpression.
Name --> [name(ModuleName),symbolic('::'),name(Name)].
Name --> [name(ModuleName),symbolic('::'),name(Name),symbolic(':')],
         TypeExpression.
Variable --> [varname(Name)].
Application --> Name,TupleConstruction.
StringLiteral --> [stringLiteral(String)]. % Zeichensatz cslibEncoding
IntLiteral --> [intLiteral(Int)].
FloatLiteral --> [floatLiteral(Float)].
SetConstruction --> [symbolic('{')],OptionalExpressionList,[symbolic('}')].
ListConstruction --> [symbolic('[')],OptionalExpressionList,[symbolic(']')].
TupleConstruction --> [symbolic('(')],LabeledExpressionList,[symbolic(')')].
OptionalExpressionList --> Expression,ExpressionList1.
OptionalExpressionList --> [].
ExpressionList1 --> [symbolic(',')],Expression,ExpressionList1.
ExpressionList1 --> [].
LabeledExpressionList --> LabeledExpression,LabeledExpressionList1.
LabeledExpressionList1 --> [symbolic(',')],LabeledExpressionList1.
LabeledExpressionList1 --> [].
LabeledExpression --> Label,[symbolic(':')],Expression.
TypeExpression --> Name. % TypeName ?
TypeExpression --> [symbolic('(')],LabeledTypeList,[symbolic(')')].
TypeExpression --> [symbolic('(')],TypeExpression,[symbolic(')')].

WithinEval --> [name(within)],EnvSpec,[name(eval)],Expression.

(Nachteil der Realisierung als Backtracking-Parser (PROLOG): keine
 spezifischen Fehlermeldungen moeglich, ineffizient, keine Kontrolle
 der Grammatik. Alternative: Yacc-Kompilat erzeugt Strukturbaum.)

Attributierte Grammatik von QueRist mit Kontextbedingungen
----------------------------------------------------------
(Ich schlage vor: Trennung von kontextfreier Parsierung und Attributauswertung.
 Vorteil: Die Erzeugung des Strukturbaumes kann von verschiedenen Quellen
 aus erfolgen (WWW-Interface, Prolog-Reader, effizienter Yacc-Parser)
 und die Ueberfuehrung in abstrakte Syntax braucht nur einmal implementiert
 werden -> Modularitaet. Nachteil: Konsistenzsicherung zwischen den
 Komponenten.).

qrExpression( ptExpression@:setof @ [begin = Begin, end = End,
                                     lambda = Lambda],
              atExpression@:setof @ [begin = Begin, end = End,
                                     type = set(T)] )
  -->@ !,
  qr(Lambda, qrExpression@:lambda @ [type = T2] ),
  check T2 = (T->bool).
%  check isFunctionType(T2,T,bool)
%  check isSetType(T1,T)

Datentypen fuer attributierten Strukturbaum
-------------------------------------------
(Zur Zeit gehoeren die Ableitungen der rechten Seite noch zu den Attributen.)

?-defvariant(queristExpression,[
    name(name,object,module,type),
    variable(name,object,type),
    integer(value,type),
    float(value,type),
    string(value,type),
    term(value,type),
    set(expressions,type),
    list(expressions,type),
    tuple(components,type),
    setOf(lambda,type),
    orderedListOf(lambda,orderspec,type),
    rankedListOf(lambda,lambda,type),
    exist(varlist,expression,type),
    forAll(varlist,expression,type),
    application(expression,expressionlist,type)
  ]).


Ablauf der Uebersetzung mit den skizzierten Zwischenstufen 
----------------------------------------------------------
?-doQueryFromString(ascii,'&',sset of ...",outStream).

doQueryFromString(CharSet,EscapeChar,QueryString,OutStream /*,ErrorStream*/) :-
  newQueryId(Id), /* setErrorStream(ErrorStream) */
  qrRead8bit(CharSet,EscapeChar,indexCharacters,sset of ...",Characters),
  qrScan(Characters,Tokens),
  qrParse(Tokens,Structure),
    % bis hierher durch eine effizientere Implementierung
    % oder durch beliebiges Frontend ersetzbar, welche(s) Structure liefert
  qrAttributes(Structure,AttributedStructure,Assertions),
    % Falls Structure bereits 'Leerstellen' fuer Attribute enthaelt, entfaellt
    % die Erzeugung von AttributedStructure
  qrSolveAttributes( /*AttributedStructure,*/ Assertions),
    % Berechnung der Attribute, Pruefung Kontexbed., Typisierung/Bindung
  qrIntermediate(AttributedStructure,Intermediate),
    % Vereinfachung der Struktur
%  qrGenerateRules(Intermediate,Rules,ResultType), % safe formulas?
%  qrRewriteRules(Rules,RewrittenRules), % Primitiven einsetzen
%  qrBuildBlocks(RewrittenRules,BlockRules), % Primitiven zusammenfassen (SQL)
%  qrSequenceBlocks(BlockRules,SequencedRules), % I/O-Parameter der Blocks
%  qrGenerateBlockCode(SequencedRules,ExecutableRules), 
%  qrExecuteRules(Id,ExecutableRules,Result),
%  qrWriteResult(OutStream,Result,ResultType),
   qrClean(Id).
  % ... 

Alte Grammatik
--------------
<Interaction>		<- <Directive>
			   <Directive> <Interaction>

<Directive>		<- <Query> '.'
			 | <Definition> '.'
                         | <Imperative> '.'
                         | <Import> '.'.

<Query>			<- <Set : -> set(S)>
                         | <RankList : -> list((T,rank))>
                         | <OrderedList : -> list(T)>
			 | <Singleton : -> T>.
 
<Set : -> set(S)> 		<- set of <Lambda : S -> bool>
			 	 | <Expression : -> set(S)>
				 | <SetConstruction : -> set(S)>.
<RankList : -> list((T,rank))> 	<- ranklist of <Set : -> set(T)> ranked by
                                   <Lambda : T -> relevanceDescription>.
<OrderedList : -> list(T)>	<- list of <Set : -> set(T)> ordered by
                       <OrderSpecification : -> list(((S1,S1)->bool,T->S1),...).
<Singleton : -> T>		<- the <Lambda : T -> bool>
				 | the <Set : -> set(T)>
				 | <Expression : -> T>.

<Lambda : S -> bool>	<- <Var : S> where <Expression : -> bool|Var : S>.
<Lambda : S -> T>	<- <Var : S> @ <Expression : -> T|Var : S>.

<Var : S>		<- <VarName : S>.
<Var : S>		<- <TupleConstruction : S>.

<TupleConstruction : -> T>	<- '(' <LabeledList : -> T> ')'.

<LabeledList : -> (l:T)>	<- <Label l> : <Expression : -> T>.
<LabeledList : -> (l:T,L)>	<- <Label l> : <Expression : -> T> ,
				   <LabeledList -> L>.

<SetConstruction : -> set(T)>	<- '{' <SetElements : -> T> '}'.
<SetElements : -> T>		<- <empty>
				 | <Expression : -> T>.
<SetElements : -> (T1;Tr)>	<- <Expression : -> T1> ',' <SetElements : -> Tr>

<ListConstruction : -> list(T)> <- '[' ...

<Expression : -> T|TypeAssert>	<- <Application : -> T|TypeAssert>
				 | <Name : -> T>
				 | <VarName : -> T>
				 | <Integer : -> T>
				 | <String : -> T>
				 | <Term : -> T>
                                 | <Set : -> T>
				 | <List : -> T>
                                 | <Singleton : -> T>
				 | <TupleConstruction : -> T>.

<Application : -> T|TypeAssert> <- <Name : AT -> T><ArgTuple : -> AT|TypeAssert>
                                 | apply(<Expression : -> function>,<ArgList>)
				 | <Expression : -> R|TypeAssert>
                                   <InfixNameXFX : (R,S) -> T>
                                   <Expression : -> S|TypeAssert>

Alte abstrakte Syntax
---------------------
type atom = prologAtom.
type int  = prologInt.
type float  = prologFloat.
type string = prologString.
type term = prologTerm.
type list(T) = prologList(T).
type tuple([T|R]) = prologTuple([T|R]).

type lambda = tuple(Expression,Expression).

type
expression = name(atom)
             varname(atom)
             integer(int)
             float(float)
             string(string)
             term(term)
             set(list(expression))
             list(list(expression))
             tuple(list(tuple([atom,expression])))
             setOf(lambda)
             orderedListOf(expression,list(tuple([expression,expression])))
             rankedListOf(expression,expression)
             exist(atom,expression)
             forAll(atom,expression)
             application(expression,list(expression))

(Nicht so besonders aussagekraeftig, da zu allgemein.)

Ueberfuehrung von konkreter Syntax in abstrakte Syntax
------------------------------------------------------
set of (autoren: autor(D), titel: titel(D)) where D in dokument, 
                                                  erscheinungsjahr(D) > 1990.

setof(
  lambda(
    tuple([(autoren,application(name(autor),
                                [varname('D')])),
           (titel,application(name(titel),
                              [varname('N')]))),
    exists('D',
      application(name(','),[
        application(name(in),[varname('D'),name(dokument)]),
        application(name('>'),[application(name(erscheinungsjahr),
                                           [varname('D')])],
                               integer(1990))]))))

Implizite Quantifizierung von Variablen
---------------------------------------
set of
  (autoren:
    (set of (vorname: vorname(A), 
             nachname: nachname(A))
       where A in autor(D)),
   titel: titel(D))
     where D in dokument,
           (titel(D) in ?'*[Dd]atenbank*' ;
            titel(D) in ?'*[Ii]nformationssys*'),
           (for all C holds
              C in klassifikationscodes(D) ==>
              not C in (setof C where C in klassifikationscode,
                                    (bezeichnung(C) = 'KI';
                                     bezeichnung(C) = 'Programmiersprachen'))).
fa not a or b
not ex not( not a or b )
not ex a and not b

%           not (exists C such that
%                  C in klassifikationscodes(D),
%                  C in (setof C where ...)
%           not (C in klassifikationscodes(D),
%                C in (setof C where ...)

Ist nach Rectifizierung, expliziter Quantifizierung und Eliminierung von
All-Quantoren aequivalent zu

set of R where
  exists (D,As,T) such that
     R = (autoren: As, titel: T),
     As = (set of VN such that exists (A,V,N) such that
                                     A in autor(D),
                                     VN = (vorname: V, nachname: N),
                                     V = vorname(A), N = nachname(A)),
     T = titel(D),
     D in dokument,
     (exists T1 such that T1=titel(D), T1 in ?'*[Dd]atenbank*';
      exists T2 such that T2=titel(D), T2 in ?'*[Ii]nformationssys*'),
     not (exists C such that
            C in klassifikationscodes(D),
            C in (setof C where C in klassifikationscode,
                                (bezeichnung(C) = 'KI';
                                 bezeichnung(C) = 'Programmiersprachen'))).

Erzwingung von sicheren Formeln
-------------------------------
Ein theoretischer Begriff, welcher die Syntax von Anfragen dahingehend
einschraenkt, dass garantiert werden kann, dass ihre Antwort in endlicher
Zeit berechnet werden kann, ist der Begriff der sicheren Formel
(safe formula).
In den meisten real existierenden Anfragesprache (z.B. SQL, DAPLEX, IQL)
die ja darauf angewiesen sind, dass sie in endlicher Zeit etwas berechnen,
findet man deshalb eine Art explizite Typisierung (Beschraenkung auf eine
endliche Domain) der Variablen.
Statt also (wie bei der logischen Sichtweise)

set of D where ..., D in dokument, ...

zuzulassen und dann zu pruefen, ob die Formel tatsaechlich sicher ist,
wird gleich (syntaktisch) verlangt:

set of D in dokument where ...

Beispiel fuer eine nicht sichere Formel, welche bei der ersten Loesung erst
nach dem Test auf Sicherheit als solche erkannt werden wuerde, waere:

set of D where not D in dokument

Im zweiten Ansatz koennte man allenfalls

set of D in dokument where not D in dokument

fordern, was aber sicher waere, da man spaetestens! nach dem Test
aller (endlich vielen) Dokumente feststellen wuerde, dass die Bedingung
fuer kein Dokument zutrifft.

Allerdings ist grundsaetzlich zu beachten, dass nicht jede Typisierung
zugleich auch eine sichere Formel bedeuten muss, wenn der Typ (potentiell)
nicht endlich ist:

set of I in int such that I > 0.

Ich weiss momentan nicht so genau, was schoener, besser, einfacher ist.
Allgemeiner und einheitlicher scheint mir die erste Loesung zu sein, auch wenn
sie natuerlich mehr Fehler zulaesst, die erst auf einer tieferen Ebene
der Analyse erkannt werden und damit vermutlich aufwendiger zu testen ist.
Die zweite Loesung haette u.a. auch den Vorteil, dass der Typ der Variablen
direkt ersichtlich ist und als Ergebnistyp zu verwenden waere.

Bei der Verwendung von Tupel-Variablen und der Moeglichkeit, die Ergebniswerte
direkt als Ausdruck definieren zu koennen, wird die Sache nicht wesentlich
anders:

set of (titel: titel(D), irdendwas: in sonstwas)

Hier muessen alle Komponenten der Tupel-Variablen beschraenkt sein.
Dies duerfte insofern kein zusaetzliches Problem darstellen, da
die Komponenten 
  1. durch Gleichungen an Ausdruecke gebunden sind, deren
     Werte jeweils in endlicher Zeit berechnet werden koennen (rekursive
     Definition der Sicherheit). [Sollte ich fuer non-1NF Kalkuel noch besser
     verstehen!]
  2. 'frei' sind, sodass man wieder die syntaktische Einschraenkung fordern
     kann, welche die Sicherheit erzwingt.

Das Problem der unkontrollierten Konstruktion von Powersets sollte
hier diskutiert werden, wenn ich es ausreichend verstanden habe.

Nullwerte
----------
Das Problem der 'vernueftigen' Behandlung von Nullwerten ergibt sich,
da unser Relationales Datenmodell nicht ohne Nullwerte auskommt.
Nullwerte sind allerdings etwas, was bei der rein praedikatenlogischen
Sichweise (sagen wir mal: ohne Funktionen und Mengen) nicht auftritt,
da es nur Relationen gibt und entweder steht ein Tupel darin oder er
steht nicht darin.

Geht man zu non-1NF-Theorien ueber, wie das (wegen der Verwendung
von Funktionen, Element-Relation und Mengen) in der geplanten
Anfragesprache unverkennbar ist, sind Nullwerte durch die
leere Menge abbildbar. Dies hat zur Folge, dass fuer alle
Attribut-Werte im Datenmodell, die nicht mit 'NOT NULL' definiert
sind, eigentlich Mengentypen angesetzen werden sollten (strenggenommen
ist ein Relationales Datenmodell mit Nullwerten also nicht in 1NF!).

Ein semantisches Problem in diesem Zusammenhang ist, dass man dann
nicht mehr zwischen maximal einelementigen Mengen und Mengen mit
beliebig (endlich) vielen Elementen unterscheiden kann.  Definiert man
fuer alle Attribute Mengentypen (auch fuer solche ohne Nullwerte),
kann man auch keine genau einwertigen 'Mengen' mehr erkennen.  Vorteil
dieser Vorgehensweise: Wenn sich Attributkardinalitaeten aendern,
koennen die Anfragen gleich bleiben, ohne einen Typfehler zu
verursachen.  Nachteil: Wenn sich Attributkardinalitaeten aendern,
sollten alle (bereits irgendwo gespeicherten) Anfragen, welche
Annahmen bzgl.  der Kardinalitaeten machen, ueberdacht werden (woran
man durch die Typfehler erinnert werden wuerde).

Zeit fuer ein Beispiel:
Problem: Nicht alle Dokumente besitzen ein Erscheinungsjahr.

Die Semantik der Anfrage (praedikatenlogisch)

set of D where exists E such that dokument(D),				(1)
                                  erscheinungsjahr(D,E), E > 1990.

ist: Menge der Dokumente, mit einem Erscheinungsjahr groesser 1990, falls
sie ein Erscheinungsjahr haben.

Haette nun ein Dokument (aus nicht naeher geklaerten Umstaenden:-) mehrere
Erscheinungsjahre, wuerde es ausreichen, wenn eines dieser Jahre groesser
als 1990 waere (es fragt sich, ob das beabsichtigt war).

Will man nun aber die Menge der Dokumente, mit einem Erscheinungsjahr
groesser 1990, falls sie ein Erscheinungsjahr haben, und zusaetzlich
(sozusagen sicherheitshalber) alle, die kein Erscheinungsjahr haben,
muss"te man fordern:

set of D where dokument(D),						(2)
               ((not (exists E such that erscheinungsjahr(D,E)));
                (exists E such that erscheinungsjahr(D,E), E > 1990)).

Nullwerte, die leere Menge und die Negation sind eng miteinander verbunden.
Genauer gesagt: Leere Menge und Element-Operator koennen unter bestimmten
Bedingungen die Negation vollstaendig ersetzen.

Voraussetzung sei nun, dass eine mengenwertige Funktion existiere,
welche das Erscheinungsjahr eines Dokuments liefere. Wie oben beschrieben,
laesst sich damit nicht modellieren, dass ein Dokument hoechstens ein
Erscheinungsjahr haben kann (jedoch, dass es kein Erscheinungjahr haben
kann, was ja gerade gewuenscht ist).

Eine Anfrage mit derselben Semantik, wie Anfrage (1) lautete dann:

set of D where exists E such that D in dokument,
                                  E in erscheinungsjahr(D), E > 1990.

Eine Anfrage mit derselben Semantik, wie Anfrage (2) lautete dann:

set of D where D in dokument,
               (erscheinungsjahr(D) = {};
                (exists E such that E in erscheinungsjahr(D), E > 1990)).

Die (vielleicht) verlockende Schreibweise

  ... erscheinungsjahr(D) > 1990 ...

wuerde unter den gegebenen Umstaenden einen Typ-Fehler verursachen, da
die Funktion mengen-wertig ist und > nur zwischen Integers definiert
ist. SQL definiert 'False' als Ergebnis eines Vergleichs zwischen
zwei Ausdruecken, von denen einer 'NULL' ist und implementiert damit
per Default die Semantik von Anfrage (1).

Sicher kann man auch '>'-Praedikate definieren, die zwischen
einer Menge von Integern und einem Integer definiert sind, und die
eine Sonderbehandlung fuer leere Mengen erfordern. Dies fuehrt uns direkt
zum naechsten Problem: Sortierung mit Nullwerten (alias leere Mengen).

SQL behandelt bei der Sortierung den 'NULL'-Wert als kleiner als
jeden anderen Wert. D.h., das Sortierpraedikat liefert 'True' fuer
X > NULL und fuer NULL < X. Wuerde man bei der Sortierung
dasselbe Praedikat wie oben benutzen, waere keine Sortierung
nach Erscheinungsjahr moeglich, da die Attributfunktion eine Menge
liefert. Um zur Sortierung kein spezielles Vergleichspraedikat zu
verwenden, koennte die Verwendung des (noch nicht definierten)
'the'-Operators hilfreich sein. 'The' angewandt auf eine Menge liefert
das einzige Element der Menge, wenn die Menge zum Zeitpunkt der Anwendung
genau ein Element enthaelt, und ansonsten einen Laufzeitfehler (=Abbruch).

Dieses Vorgehen hat zur Folge, dass man eine Menge entsprechend der
Semantik von Anfrage (2) nicht nach dem Erscheinungsjahr sortieren
kann, wenn ein Erscheinungsjahr-Attribut kein Jahr oder (aus nicht naeher
geklaerten Umstaenden) mehr als ein Jahr enthaelt. Der 'the'-Operator
stellt damit eine 'Assertion' dar, welche die Uebereinstimmung zwischen
Annahmen des Anwenders und dem durch die jeweilige Anfrage beruehrten
Datenbankszustand sicherstellt.
Nuetzlich ist der 'the'-Operator vor allem dort, wo der Benutzer glaubt
(oder hofft), durch eine Anfrage genau ein einziges Objekt zu selektieren:

 ... P = the (set of X where X in person, nachname(X) = 'Walkes').
(moegliche Abkuerzung: the X where ...)

Bei der Modellierung mit mengenwertigen Attributen und einem Verzicht
auf Nullwerte treten auch bei mengenwertigen Attributen keine neuen Probleme
auf(?): Man kann mit der leeren Menge modellieren, dass ein Attribut keinen
Wert eines speziellen atomaren Typs besitzt. Bei einem Mengen-Typ geht man
entsprechend vor und setzt in diesem Fall eine Menge von Mengen als
Attributtyp an.

Ich frage mich jetzt folgendes: Soll es spezielle Mengentypen geben, welche
Min-Max-Angaben bzgl. ihrer Elementanzahl haben? Dies wuerde exakt zu den
Kardinalitaeten in der semantischen Datenmodellierung korrespondieren.
Dieser Mengentyp waere, bis auf die Beschraenkungen, ein vollwertiger
Mengentyp (Untertyp von 'set') und wuerde bei der Modellierung von
Attributfunktionen alle elementaren Typen ersetzen:

erscheinungsjahr : dokument -> limitedSet(int,0,1)

Weitere Frage: Sind die Typen 'limitedSet(int,1,1)' und 'int' identisch?.
Streng genommen ist naemlich auf ein Objekt vom ersten Typ der allgemeine
Element-Operator anwendbar und auf ein Objekt vom zweiten Typ nicht.
Existiert eine automatische Typkonvertierung zwischen den beiden Typen?
Vorteile: ? Nachteile: Unbekanntes Terrain. Vermutlich sind Laufzeittests
notwendig, um die Konsistenz sicherzustellen (wann, wo?).

Im Zusammenhang mit dem 'the'-Operator ist zu bemerken, dass dieser
auf Objekten vom Typ 'limitedSet(X,1,1)' einfach wegoptimiert werden
koennte und bei spaeteren Aenderungen der Kardinalitaet, jene
Stellen in Anfragen markiert, die besondere Anforderungen an die
Kardinalitaet stellen. Allerdings fuehrt dies hier nicht zu einem
Fehler zur Uebersetzungszeit, sondern erst zur Laufzeit, wenn die Annahme
bei der Ausfuehrung einer Anfrage nicht mehr erfuellt sein sollte.

Sortierung
----------
Bei dem bisher verfolgen Ansatz muessen entweder die Werte, nach denen
sortiert werden soll oder eine Referenz auf ein Objekt, nach dessen
Attributen sortiert werden soll, im Ergebnis-Tupel enthalten sein!
In SQL ist dies nicht erforderlich.

Objekt-Identifikatoren
----------------------

... to be continued
... to be revised