BEGIN
OPEN DBCommon, DBDefs;
DeclareIndex:
PUBLIC
PROC [r: Relation, fields: FieldSequence, isKey:
BOOL ←
FALSE, doCheck:
BOOL ←
TRUE]
RETURNS[index: Index] = {
sh: SegmentHandle = DBModelPrivate.SegmentToHandle[r.segment];
indicesToCheck: LIST OF IndexHandle;
DBModelPrivate.CheckRelationKey[r];
IF NOT r.indicesKnown THEN CacheIndices[r];
IF doCheck
THEN {
Check to see if index already exists
IF isKey THEN indicesToCheck ← r.keys ELSE indicesToCheck ← r.indices;
FOR i:
LIST
OF IndexHandle ← indicesToCheck, i.rest
UNTIL i =
NIL
DO
same: BOOL ← TRUE;
IF i.first.index.count # fields.count THEN LOOP;
FOR j:
CARDINAL
IN [0..fields.count)
WHILE same
DO
same ← same AND i.first.index[j] = fields[j]
ENDLOOP;
IF same
THEN
RETURN [NEW[ IndexObject ← [fields: i.first.index, isKey: i.first.isKey, key: r.key, index: i.first.indexHandle ] ] ]
ENDLOOP };
IF NOT r.attributesKnown THEN DBModelPrivate.CacheAttributes[r];
Ensure that each attribute appears at most once in the index
FOR i:
CARDINAL
IN [0..r.attributes.count)
DO
appears: BOOL ← FALSE;
FOR j:
CARDINAL
IN [0..fields.count)
DO
IF i = fields[j]
THEN {
IF appears THEN ERROR DB.Error[IllegalIndex] ELSE appears ← TRUE }
ENDLOOP
ENDLOOP;
BEGIN
indexTuple: DBStorage.TupleHandle = DBModelPrivate.CopyTupleHandle[DBStorage.CreateSystemPageTuple[x: DBModelPrivate.IndexTupleSet, y: r.tupleSet, s: r.segment]];
cachedIndexHandle: IndexHandle ← NEW[IndexHandleObject ← [indexHandle: indexTuple, isKey: isKey, index: NEW[FieldSequenceObject[fields.count]]]];
index ← NEW[IndexObject ← [isKey: isKey, index: indexTuple, fields: cachedIndexHandle.index, key: r.key]];
DBModelPrivate.SetBoolField[indexTuple, DBModelPrivate.IndexKeyField, isKey];
DBModelPrivate.SetCardField[indexTuple, DBModelPrivate.IndexCountField, fields.count];
DBModelPrivate.SetTupleField[indexTuple, DBModelPrivate.IndexRelationField, r.tupleSet];
Add the index factors to the database
BEGIN
indexFactorGroup: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[indexTuple, indexHandle, Last];
FOR i:
CARDINAL
IN [0..fields.count)
DO
indexFactorTuple: DBStorage.TupleHandle = DBStorage.CreateSystemPageTuple[x: DBModelPrivate.IndexTupleSet, y: indexTuple, s: r.segment];
DBModelPrivate.SetCardField[indexFactorTuple, attributeHandle, fields[i]];
DBStorage.WriteTID[indexFactorTuple, indexFactorGroup];
cachedIndexHandle.index[i] ← fields[i]
ENDLOOP;
DBStorage.CloseScanGroup[indexFactorGroup]
END;
sh.schemaUpdated ← TRUE;
index.key ← r.key;
index.isKey ← isKey;
IF isKey THEN r.keys ← CONS[cachedIndexHandle, r.keys]
ELSE r.indices ← CONS[cachedIndexHandle, r.indices];
Finally, include the new index in the list for all of the attributes
FOR i:
CARDINAL
IN [0..index.fields.count)
DO
r.attributes[index.fields[i]].indices ← CONS[cachedIndexHandle, r.attributes[index.fields[i]].indices]
ENDLOOP
END
};
DestroyIndex:
PUBLIC
PROC [r: Relation, index: Index] = {
sh: SegmentHandle = DBModelPrivate.SegmentToHandle[r.segment];
DBModelPrivate.CheckRelationKey[r];
IF NOT r.indicesKnown THEN CacheIndices[r];
IF NOT r.attributesKnown THEN DBModelPrivate.CacheAttributes[r];
IF NOT DBModelPrivate.IsLegalIndex[r, index] THEN ERROR DB.Error[IllegalIndex];
IF index.isKey THEN ERROR DB.Error[IllegalIndex]; -- Can't destroy a key index!
Remove it from the database
DestroyIndexTuple[index.index];
Remove it from the cache (this is a little aggressive, but simple!)
BEGIN
r.indicesKnown ← FALSE;
r.keys ← r.indices ← NIL;
FOR i:
CARDINAL
IN [0..index.fields.count)
DO
r.attributes[index.fields[i]].indices ← NIL
ENDLOOP
END;
sh.schemaUpdated ← TRUE
};
DestroyIndexTuple:
PUBLIC PROC[handle: DBStorage.TupleHandle] = {
indexFactors: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[handle, indexHandle, First];
FOR indexFactor: TupleHandle ← DBStorage.NextInGroup[indexFactors], DBStorage.NextInGroup[indexFactors]
UNTIL indexFactor =
NIL
DO
DBStorage.WriteTIDNil[indexFactor, indexHandle];
DBStorage.DestroyTuple[indexFactor]
ENDLOOP;
DBStorage.CloseScanGroup[indexFactors];
DBStorage.WriteTIDNil[handle, IndexRelationField]; -- remove it from the group for the relation
DBStorage.DestroyIndex[handle];
DBStorage.DestroyTuple[handle] };
DeleteTupleFromIndex:
PUBLIC
PROC[t: TupleHandle, r: Relation, iHandle: IndexHandle] = {
entry: Rope.ROPE = IndexEntryForTuple[t, r, iHandle.index];
DBStorage.DeleteFromIndex[x: iHandle.indexHandle, k: entry, v: t]
};
AddTupleToIndex:
PUBLIC PROC[t: TupleHandle, r: Relation, iHandle: IndexHandle] = {
entry: Rope.ROPE = IndexEntryForTuple[t, r, iHandle.index];
DBStorage.InsertIntoIndex[x: iHandle.indexHandle, k: entry, v: t]
};
IndexEntryForTuple:
PROC[t: TupleHandle, r: Relation, index: FieldSequence]
RETURNS[entry: Rope.
ROPE] =
TRUSTED {
entry ← "";
FOR i:
CARDINAL
IN [0..index.count)
DO
attr: REF AttributeObject = r.attributes[index[i]];
SELECT attr.type
FROM
ropeType => entry ← Rope.Concat[entry, NCodeRope[DBModelPrivate.GetRopeField[t, attr.fh]]];
boolType => entry ← Rope.Concat[entry, NCodeBool[DBModelPrivate.GetBoolField[t, attr.fh]]];
intType => entry ← Rope.Concat[entry, NCodeInt[DBModelPrivate.GetIntField[t, attr.fh]]];
timeType => entry ← Rope.Concat[entry, NCodeTime[DBModelPrivate.GetTimeField[t, attr.fh]]];
ENDCASE => entry ← Rope.Concat[entry, NCodeTuple[DBModelPrivate.GetTupleField[t, attr.fh]]];
ENDLOOP };
CacheIndices:
PUBLIC PROC[r: Relation] = {
indexHandles: LIST OF IndexHandle ← NIL;
keyHandles: LIST OF IndexHandle ← NIL;
indexGroup: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[r.tupleSet, DBModelPrivate.IndexRelationField, First];
IF NOT r.attributesKnown THEN DBModelPrivate.CacheAttributes[r];
Enumerate all of the attributes of the relation tuple
FOR t: TupleHandle ← DBStorage.NextInGroup[indexGroup], DBStorage.NextInGroup[indexGroup]
UNTIL t =
NIL
DO
factorCount: CARDINAL = DBModelPrivate.GetCardField[t, DBModelPrivate.IndexCountField];
isKey: BOOL = DBModelPrivate.GetBoolField[t, DBModelPrivate.IndexKeyField];
thisHandle: IndexHandle ← NEW[IndexHandleObject ← [indexHandle: DBModelPrivate.CopyTupleHandle[t], isKey: isKey, index: NEW[FieldSequenceObject[factorCount]]]];
Now enumerate each of the factors of the index
indexFactorGroup: DBStorage.GroupScanHandle = DBStorage.OpenScanGroup[t, indexHandle, First];
thisFactor: CARDINAL ← 0;
FOR if: TupleHandle ← DBStorage.NextInGroup[indexFactorGroup], DBStorage.NextInGroup[indexFactorGroup]
UNTIL if =
NIL
DO
thisHandle.index[thisFactor] ← DBModelPrivate.GetCardField[if, attributeHandle];
thisFactor ← thisFactor + 1
ENDLOOP;
DBStorage.CloseScanGroup[indexFactorGroup];
IF isKey THEN keyHandles ← CONS[thisHandle, keyHandles]
ELSE indexHandles ← CONS[thisHandle, indexHandles];
Finally, hook up with the attributes
FOR i:
CARDINAL
IN [0..factorCount)
DO
r.attributes[thisHandle.index[i]].indices ← CONS[thisHandle, r.attributes[thisHandle.index[i]].indices]
ENDLOOP
ENDLOOP;
DBStorage.CloseScanGroup[indexGroup];
r.indicesKnown ← TRUE;
r.indices ← indexHandles;
r.keys ← keyHandles };
Keys:
PUBLIC
PROC[r: Relation]
RETURNS[keys:
LIST
OF Index] = {
DBModelPrivate.CheckRelationKey[r];
CacheIndices[r];
IF r.isSurrogate
THEN {
Add the implied key of the surrogate
fields: FieldSequence ← NEW[FieldSequenceObject[1]];
fields[0] ← 0;
keys ← LIST[NEW[IndexObject ← [key: r.key, isKey: TRUE, fields: fields]]] };
FOR kL:
LIST
OF IndexHandle ← r.keys, kL.rest
UNTIL kL =
NIL
DO
keys ← CONS[NEW[IndexObject ← [key: r.key, index: kL.first.indexHandle, isKey: TRUE, fields: kL.first.index]], keys]
ENDLOOP };
Indices:
PUBLIC
PROC[r: Relation]
RETURNS[indices:
LIST
OF Index] = {
DBModelPrivate.CheckRelationKey[r];
CacheIndices[r];
FOR kL:
LIST
OF IndexHandle ← r.indices, kL.rest
UNTIL kL =
NIL
DO
indices ← CONS[NEW[IndexObject ← [key: r.key, index: kL.first.indexHandle, isKey: FALSE, fields: kL.first.index]], indices]
ENDLOOP};
NCode:
PUBLIC PROC [v: Value]
RETURNS [code: Rope.
ROPE] ~
TRUSTED {
WITH v: v
SELECT
FROM
rope => code ← NCodeRope[v.value];
boolean => code ← NCodeBool[v.value];
integer => code ← NCodeInt[v.value];
time => code ← NCodeTime[v.value];
entity => code ← NCodeTuple[v.value.tuple];
null => code ← "\000\000";
ENDCASE };
NCodeRope:
PUBLIC
PROC[rope: Rope.
ROPE]
RETURNS [code: Rope.
ROPE] = {
code ← Rope.Concat[rope, "\000\000"] };
NCodeBool:
PUBLIC
PROC[bool:
BOOL]
RETURNS [code: Rope.
ROPE] = {
code ← Rope.Concat[IF bool THEN "T" ELSE "F", "\000\000"] };
NCodeTuple:
PUBLIC PROC [t: TupleHandle]
RETURNS [code: Rope.
ROPE] ~ {
code ← NCodeCard[t.tid] };
NCodeInt:
PUBLIC
PROC[int:
INT]
RETURNS [code: Rope.
ROPE] =
TRUSTED {
i: LONG CARDINAL = LOOPHOLE[int, LONG CARDINAL]+20000000000B;
code ← NCodeCard[i] };
NCodeTime:
PUBLIC
PROC[time: BasicTime.
GMT]
RETURNS [code: Rope.
ROPE] =
TRUSTED {
i: LONG CARDINAL = LOOPHOLE[time];
code ← NCodeCard[i] };
LowByte:
PROC [n:
CARDINAL]
RETURNS [
CHAR] =
TRUSTED
INLINE
{RETURN[LOOPHOLE[LOOPHOLE[n, Basics.BytePair].low]]};
HighByte:
PROC [n:
CARDINAL]
RETURNS [
CHAR] =
TRUSTED
INLINE
{RETURN[LOOPHOLE[LOOPHOLE[n, Basics.BytePair].high]]};
NCodeCard:
PUBLIC
PROC[i:
LONG
CARDINAL]
RETURNS [code: Rope.
ROPE] =
TRUSTED {
s: STRING ← [4];
s.length ← 4;
s[0] ← HighByte[Basics.HighHalf[i]];
s[1] ← LowByte[Basics.HighHalf[i]];
s[2] ← HighByte[Basics.LowHalf[i]];
s[3] ← LowByte[Basics.LowHalf[i]];
code ← Rope.Concat[ConvertUnsafe.ToRope[s], "\000\000"] };
DCode:
PUBLIC
PROC[key: DBCommon.IndexKey, ropes: RopeSequence] =
TRUSTED {
This procedure takes apart a key that has been composed as a concatenation of calls to NCode and places each component in the given element of the rope sequence that was passed in
start: INT ← 0;
end: INT ← 0;
ropeText: Rope.Text;
IF key = NIL THEN RETURN;
FOR i:
CARDINAL
IN [0..ropes.length)
DO
Find the end of the next piece
UNTIL key.text[end] = '\000 AND key.text[end+1] = '\000 DO end ← end+1 ENDLOOP;
Create a new rope and copy the text
ropeText ← Rope.NewText[end - start];
ropeText.length ← end - start;
FOR j: INT IN [0 .. end-start) DO ropeText[j] ← key.text[start+j] ENDLOOP;
ropes[i] ← ropeText;
start ← end ← end+2
ENDLOOP };
CheckKeyInIndex:
PUBLIC PROC[i: IndexHandle, key: Rope.
ROPE]
RETURNS [yes:
BOOL] = {
yes ← DBModelPrivate.GetNamedTuple[i.indexHandle, key] # NIL };
4. Definition of the structure of Indices in the Database
The structure of the storage of the relations, attributes and index factors component of a Cypress database is reasonably complicated and takes advantage of the ability to define many groups at the storage level.
An index tuple is the head of an index-factor group; it also contains a count of the number of factors in the index. Elements of the index factor domain contain links to the attribute that defines the factor and are linked in the order in which the index factors are to be used in accessing the index.
IndexCountField: PUBLIC DBStorage.FieldHandle;
IndexRelationField: PUBLIC DBStorage.FieldHandle;
IndexKeyField: PUBLIC DBStorage.FieldHandle;
IndexFactorTupleSet: DBStorage.SystemTuplesetHandle;
IndexFactorDomain: DBCommon.TupleHandle;
Handles for the index factor domain
attributeHandle, indexHandle: DBStorage.FieldHandle;
InitializeIndexSchema:
PUBLIC
PROC[] =
TRUSTED {
The IndexDomain tuples are all used as indices; the first field is used to store the index information, the second may store the number of index factors that make up the index entries (if the index is client-created), the third gives the relation for which the index is being maintained, and the final field specifies whether the index is an index of keys of the relation
An index tuple is the head of an index-factor group; it also contains a count of the number of factors in the index. Elements of the index factor domain contain links to the attribute that defines the factor and are linked in the order in which the index factors are to be used in accessing the index.
[IndexFactorTupleSet, IndexFactorDomain] ← DBModelPrivate.SetSystemTable[DBModelPrivate.IndexFactorTSID];
[] ← DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBModelPrivate.IndexDescriptor];
IndexCountField ← DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBModelPrivate.OneWordDescriptor];
IndexRelationField ← DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBStorage.FieldDescriptor[Group[groupID: DBModelPrivate.RelationDomain]]];
IndexKeyField ← DBStorage.AddSystemField[DBModelPrivate.IndexTupleSet, DBModelPrivate.OneWordDescriptor];
The IndexFactor tuples have the following fields:
1. the index for the factor,
2. the position (a CARDINAL) of the corresponding attribute in the relation
indexHandle ← DBStorage.AddSystemField[IndexFactorTupleSet, DBStorage.FieldDescriptor[Group[groupID: DBModelPrivate.IndexDomain]]];
attributeHandle ← DBStorage.AddSystemField[IndexFactorTupleSet, DBModelPrivate.OneWordDescriptor] };