1027 lines
33 KiB
C++
1027 lines
33 KiB
C++
/*
|
|
----
|
|
This file is part of SECONDO.
|
|
|
|
Copyright (C) 2004, University in Hagen, Department of Computer Science,
|
|
Database Systems for New Applications.
|
|
|
|
SECONDO is free software; you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation; either version 2 of the License, or
|
|
(at your option) any later version.
|
|
|
|
SECONDO is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with SECONDO; if not, write to the Free Software
|
|
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
----
|
|
|
|
//paragraph [1] Title: [{\Large \bf \begin{center}] [\end{center}}]
|
|
//paragraph [10] Footnote: [{\footnote{] [}}]
|
|
//[TOC] [\tableofcontents]
|
|
|
|
[1] Implementation of the range operators for the BTree2-Algebra
|
|
|
|
[TOC]
|
|
|
|
1 Defines and Includes
|
|
|
|
*/
|
|
|
|
#include "op_rangebtree2.h"
|
|
|
|
#include "ListUtils.h"
|
|
#include "QueryProcessor.h"
|
|
#include "Algebras/Relation-C++/RelationAlgebra.h"
|
|
#include "Algebras/TupleIdentifier/TupleIdentifier.h"
|
|
#include "Symbols.h"
|
|
|
|
|
|
#include "BTree2.h"
|
|
#include "BTree2Iterator.h"
|
|
|
|
#include <limits>
|
|
|
|
extern NestedList* nl;
|
|
extern QueryProcessor *qp;
|
|
|
|
using namespace std;
|
|
|
|
namespace BTree2Algebra {
|
|
namespace Operators {
|
|
|
|
/*
|
|
The following constant values of the operators are defined to calculate
|
|
the number of arguments by (value div 9) and the type of range operator
|
|
by calculating (value mod 3). Type 0 means range2, type 1 means rangeS
|
|
and type 2 means range2.
|
|
The type mapping function and value mapping function use these constant
|
|
value as a template parameter.
|
|
|
|
*/
|
|
const int EXACTMATCH2 = 18; // (div 9 = 2) (mod 3 = 0)
|
|
const int EXACTMATCHS = 19; // (div 9 = 2) (mod 3 = 1)
|
|
const int LEFTRANGE2 = 21; // (div 9 = 2) (mod 3 = 0)
|
|
const int LEFTRANGES = 22; // (div 9 = 2) (mod 3 = 1)
|
|
const int RIGHTRANGE2 = 24; // (div 9 = 2) (mod 3 = 0)
|
|
const int RIGHTRANGES = 25; // (div 9 = 2) (mod 3 = 1)
|
|
const int EXACTMATCH = 29; // (div 9 = 3) (mod 3 = 2)
|
|
const int LEFTRANGE = 32; // (div 9 = 3) (mod 3 = 2)
|
|
const int RIGHTRANGE = 35; // (div 9 = 3) (mod 3 = 2)
|
|
const int RANGE2 = 27; // (div 9 = 3) (mod 3 = 0)
|
|
const int RANGES = 28; // (div 9 = 3) (mod 3 = 1)
|
|
const int RANGE = 38; // (div 9 = 4) (mod 3 = 2)
|
|
|
|
|
|
/*
|
|
2 Operators ~exactmatch2~, ~exactmatchS~, ~exactmatch~
|
|
|
|
The operator ~exactmatch2~ uses the given btree2 to find all keys or
|
|
(key-value)-pairs of the btree2 with key Tk.
|
|
The operator ~exactmatchS~ uses the given btree2 to find all tuples
|
|
identifiers where the key matches argument value Tk.
|
|
The operator ~exactmatch~ uses the given btree2 to find all tuples
|
|
in the given relation where the key matches argument value Tk.
|
|
|
|
The signatures are
|
|
|
|
----
|
|
exactmatch2: (btree2 Tk none u) x Tk --> stream(tuple((Key Tk)))
|
|
exactmatch2: (btree2 Tk Td u) x Tk --> stream(tuple((Key Tk) (Data Td)))
|
|
|
|
exactmatchS: (btree2 Tk tid multiple) x Tk --> stream(tuple((id tid)))
|
|
|
|
exactmatch: (btree2 Tk tid multiple) x rel(tuple(T)) x Tk --> stream(tuple(T))
|
|
|
|
----
|
|
|
|
|
|
2.1 Type mapping function of operators ~exactmatch2~, ~exactmatchS~, ~exactmatch~
|
|
|
|
The template parameter operatorId specifies the range operator. The operator ~exactmatch2~
|
|
with value 18 needs (18 div 9 =) 2 parameters and is a range2-type with code (18 mod 3 =) 0,
|
|
the operator ~exactmatchS~ with value 19 needs (19 div 9 =) 2 parameters, too, and is a
|
|
rangeS-type with code (19 mod 3 =) 1 and finally the operator ~exactmatch~ with value 29
|
|
needs (29 div 9 =) 3 parameters and is a range-type with code (29 mod 3 =) 2.
|
|
|
|
*/
|
|
|
|
template<int operatorId>
|
|
ListExpr RangeTypeMap(ListExpr args)
|
|
{
|
|
if(nl->ListLength(args)!=(int)(operatorId/9)){
|
|
return listutils::typeError("wrong number of arguments");
|
|
}
|
|
// Split arguments in the parts depending on the
|
|
// operator-type indicated by operatorId
|
|
ListExpr btree2Description = nl->First(args);
|
|
ListExpr relDescription = nl->TheEmptyList();
|
|
ListExpr keyDescription = nl->TheEmptyList();
|
|
ListExpr secondKeyDescription = nl->TheEmptyList();
|
|
|
|
switch ((int)(operatorId/9))
|
|
{
|
|
case 2:
|
|
keyDescription = nl->Second(args);
|
|
break;
|
|
case 3:
|
|
if ((operatorId%3)==2)
|
|
{
|
|
relDescription = nl->Second(args);
|
|
keyDescription = nl->Third(args);
|
|
}
|
|
else
|
|
{
|
|
keyDescription = nl->Second(args);
|
|
secondKeyDescription = nl->Third(args);
|
|
}
|
|
break;
|
|
case 4:
|
|
relDescription = nl->Second(args);
|
|
keyDescription = nl->Third(args);
|
|
secondKeyDescription = nl->Fourth(args);
|
|
break;
|
|
}
|
|
|
|
// find out type of key
|
|
if(!listutils::isSymbol(keyDescription)){
|
|
return listutils::typeError("invalid key");
|
|
}
|
|
|
|
// check range-operators for a second key
|
|
if ((nl->IsEmpty(secondKeyDescription)) &&
|
|
((operatorId==RANGE)||
|
|
(operatorId==RANGES)||
|
|
(operatorId==RANGE2)) )
|
|
{
|
|
return listutils::typeError("operator belongs second key type");
|
|
}
|
|
|
|
// find out type of second key (if any)
|
|
if ((!nl->IsEmpty(secondKeyDescription)) &&
|
|
(!nl->Equal(keyDescription, secondKeyDescription))) {
|
|
return listutils::typeError("different key types");
|
|
}
|
|
|
|
// check btree2 part of argument
|
|
if (!listutils::isBTree2Description(btree2Description)) {
|
|
return listutils::typeError("first argument is not a valid btree2");
|
|
}
|
|
|
|
ListExpr btree2KeyType = nl->Second(btree2Description);
|
|
|
|
// check that the type of given key is equal to the btree2 key type
|
|
if(!nl->Equal(keyDescription, btree2KeyType)){
|
|
return listutils::typeError("key and btree key are different");
|
|
}
|
|
|
|
ListExpr btree2ValType = nl->Third(btree2Description);
|
|
ListExpr btree2Unique = nl->Fourth(btree2Description);
|
|
|
|
ListExpr trel = nl->TheEmptyList();
|
|
if (!nl->IsEmpty(relDescription))
|
|
{
|
|
if (!listutils::isRelDescription(relDescription))
|
|
{
|
|
return listutils::typeError("not a relation");
|
|
}
|
|
trel = nl->Second(relDescription);
|
|
}
|
|
|
|
// check loadtype and unique-type of overloaded btree-operators
|
|
if ((operatorId%3)>0)
|
|
{
|
|
// check loadtype
|
|
if (!nl->IsEqual(btree2ValType,TupleIdentifier::BasicType())){
|
|
return listutils::typeError("datatype not a TID");
|
|
}
|
|
// check unique-type
|
|
if ((!nl->IsEqual(btree2Unique,"multiple")) &&
|
|
(!nl->IsEqual(btree2Unique,"stable_multiple"))) {
|
|
return listutils::typeError("uniquetype not multiple");
|
|
}
|
|
}
|
|
|
|
// generate different tuple-types as result of the operator
|
|
// that is indicated by the operatorId
|
|
ListExpr resultType;
|
|
switch (operatorId%3)
|
|
{
|
|
case 0:
|
|
if (nl->IsEqual(btree2ValType,"none"))
|
|
{
|
|
resultType = nl->TwoElemList(
|
|
nl->SymbolAtom(Symbol::STREAM()),
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom(Tuple::BasicType()),
|
|
nl->OneElemList(
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom("Key"),
|
|
keyDescription)
|
|
)));
|
|
}
|
|
else
|
|
{
|
|
resultType = nl->TwoElemList(
|
|
nl->SymbolAtom(Symbol::STREAM()),
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom(Tuple::BasicType()),
|
|
nl->TwoElemList(
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom("Key"),
|
|
keyDescription),
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom("Data"),
|
|
btree2ValType)
|
|
)));
|
|
}
|
|
break;
|
|
case 1:
|
|
resultType = nl->TwoElemList(
|
|
nl->SymbolAtom(Symbol::STREAM()),
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom(Tuple::BasicType()),
|
|
nl->OneElemList(
|
|
nl->TwoElemList(
|
|
nl->SymbolAtom("Id"),
|
|
btree2ValType)
|
|
)));
|
|
break;
|
|
case 2:
|
|
resultType = nl->TwoElemList(
|
|
nl->SymbolAtom(Symbol::STREAM()),
|
|
trel);
|
|
break;
|
|
}
|
|
|
|
return resultType;
|
|
}
|
|
|
|
/*
|
|
2.2 Value mapping function of operators ~exactmatch2~, ~exactmatchS~, ~exactmatch~
|
|
|
|
The template parameter operatorId specifies the range operator, a detailled
|
|
description is given with the type mapping function.
|
|
|
|
*/
|
|
|
|
struct RangeQueryLocalInfo
|
|
{
|
|
RangeQueryLocalInfo(): iter(), iterStopMarker(), relation(0),
|
|
ttype(0), nextOK(false){}
|
|
|
|
~RangeQueryLocalInfo(){
|
|
if(ttype){
|
|
ttype->DeleteIfAllowed();
|
|
}
|
|
ttype=0;
|
|
relation=0;
|
|
}
|
|
BTree2Iterator iter;
|
|
BTree2Iterator iterStopMarker;
|
|
Relation* relation;
|
|
TupleType* ttype;
|
|
bool nextOK;
|
|
};
|
|
/*
|
|
Structure to handle the information of the underlying btree2.
|
|
|
|
*/
|
|
|
|
template<int operatorId>
|
|
int
|
|
RangeQuery(Word* args, Word& result, int message, Word& local, Supplier s)
|
|
{
|
|
BTree2* btree2;
|
|
Attribute* key;
|
|
Attribute* secondKey;
|
|
Tuple* tuple;
|
|
TupleId id;
|
|
RangeQueryLocalInfo* localInfo;
|
|
bool nextOK;
|
|
|
|
switch (message)
|
|
{
|
|
case OPEN :
|
|
// local information structure for range operations
|
|
localInfo = (RangeQueryLocalInfo*)local.addr;
|
|
if(localInfo){
|
|
delete localInfo;
|
|
}
|
|
localInfo = new RangeQueryLocalInfo;
|
|
btree2 = (BTree2*)args[0].addr;
|
|
|
|
localInfo->ttype = new TupleType(nl->Second(GetTupleResultType(s)));
|
|
localInfo->nextOK = true;
|
|
|
|
// Split arguments in the parts depending on the
|
|
// operator-type indicated by operatorId
|
|
switch ((int)(operatorId/9))
|
|
{
|
|
case 2:
|
|
key = (Attribute*)args[1].addr;
|
|
secondKey = key;
|
|
break;
|
|
case 3:
|
|
if ((operatorId%3)==2)
|
|
{
|
|
localInfo->relation = (Relation*)args[1].addr;
|
|
key = (Attribute*)args[2].addr;
|
|
secondKey = key;
|
|
}
|
|
else
|
|
{
|
|
key = (Attribute*)args[1].addr;
|
|
secondKey = (Attribute*)args[2].addr;
|
|
}
|
|
break;
|
|
case 4:
|
|
localInfo->relation = (Relation*)args[1].addr;
|
|
key = (Attribute*)args[2].addr;
|
|
secondKey = (Attribute*)args[3].addr;
|
|
break;
|
|
}
|
|
|
|
assert(btree2 != 0);
|
|
assert(key != 0);
|
|
|
|
// get starting point and endmarker point of the range operation
|
|
// depending on the operator-type indicated by operatorId
|
|
switch(operatorId)
|
|
{
|
|
case EXACTMATCH:
|
|
case EXACTMATCH2:
|
|
case EXACTMATCHS:
|
|
// exactmatch of key
|
|
btree2->findExactmatchBoundary(key, localInfo->iter,
|
|
localInfo->iterStopMarker);
|
|
break;
|
|
case RANGE:
|
|
case RANGE2:
|
|
case RANGES:
|
|
// range between and including key and secondKey,
|
|
// where key <= secondKey
|
|
btree2->findRangeBoundary(key, secondKey, localInfo->iter,
|
|
localInfo->iterStopMarker);
|
|
break;
|
|
case LEFTRANGE:
|
|
case LEFTRANGE2:
|
|
case LEFTRANGES:
|
|
// leftrange is the range of the B-tree smaller and equal key
|
|
localInfo->iterStopMarker = btree2->findRightBoundary(key);
|
|
localInfo->iter = btree2->begin();
|
|
break;
|
|
case RIGHTRANGE:
|
|
case RIGHTRANGE2:
|
|
case RIGHTRANGES:
|
|
// rightrange is the range of the B-tree greater and equal key
|
|
localInfo->iterStopMarker = btree2->end();
|
|
localInfo->iter = btree2->findLeftBoundary(key);
|
|
break;
|
|
default:
|
|
assert(false);
|
|
}
|
|
|
|
// if iterator indicates the endmarker position, the range is empty
|
|
localInfo->nextOK = (localInfo->iter != localInfo->iterStopMarker);
|
|
|
|
if (localInfo->iter != btree2->end())
|
|
{
|
|
local = SetWord(localInfo);
|
|
return 0;
|
|
}
|
|
else
|
|
// if iterator indicates the endposition, there is nothing to do
|
|
{
|
|
delete localInfo;
|
|
return -1;
|
|
}
|
|
case REQUEST :
|
|
localInfo = (RangeQueryLocalInfo*)local.addr;
|
|
|
|
if (localInfo == 0)
|
|
return CANCEL;
|
|
|
|
// nextOK indicates, if there is another result of the iterator
|
|
nextOK = localInfo->nextOK;
|
|
|
|
if(nextOK)
|
|
{
|
|
// get the attributes of the result tuple of the range operation
|
|
// depending on the operator-type indicated by operatorId
|
|
switch (operatorId%3)
|
|
{
|
|
case 0:
|
|
tuple = new Tuple(localInfo->ttype);
|
|
tuple->PutAttribute(0, ((localInfo->iter).key())->Copy());
|
|
if (tuple->GetNoAttributes()>1)
|
|
tuple->PutAttribute(1, (*(localInfo->iter))->Copy());
|
|
break;
|
|
case 1:
|
|
tuple = new Tuple(localInfo->ttype);
|
|
tuple->PutAttribute(0, (*(localInfo->iter))->Copy());
|
|
break;
|
|
case 2:
|
|
id = static_cast<TupleIdentifier*>(*(localInfo->iter))->GetTid();
|
|
if (id == 0)
|
|
return CANCEL;
|
|
tuple = localInfo->relation->GetTuple( id, false );
|
|
if(tuple == 0)
|
|
{
|
|
cerr << "Could not find tuple for the given tuple id. "
|
|
<< "Maybe the given btree2 and the given relation "
|
|
<< "do not match." << endl;
|
|
return CANCEL;
|
|
assert(false);
|
|
}
|
|
break;
|
|
}
|
|
result = SetWord(tuple);
|
|
// nextOK is true, if there is another result of the iterator and
|
|
// the iterator has not reached the endmarking point
|
|
localInfo->nextOK = (localInfo->iter).next();
|
|
localInfo->nextOK &= (localInfo->iter != localInfo->iterStopMarker);
|
|
|
|
return YIELD;
|
|
}
|
|
else
|
|
// iterator has reached the endmarking point
|
|
{
|
|
return CANCEL;
|
|
}
|
|
case CLOSE :
|
|
if(local.addr)
|
|
{
|
|
localInfo = (RangeQueryLocalInfo*)local.addr;
|
|
delete localInfo;
|
|
local = SetWord(Address(0));
|
|
}
|
|
return 0;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
2.3 Specification of operators ~exactmatch2~, ~exactmatchS~, ~exactmatch~
|
|
|
|
2.3.1 Specification of operator ~exactmatch2~
|
|
|
|
*/
|
|
const string ExactMatch2Spec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk none u) x Tk -> stream(tuple((Key Tk)))\n"
|
|
"(btree2 Tk Td u) x Tk -> stream(tuple((Key Tk)"
|
|
"(Data Td)))";
|
|
string spec = "_ exactmatch2 [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all keys or (key-value)-"
|
|
"pairs of the btree2 with key ti = argument value Tk";
|
|
string example = "query Staedte_SName_btree2 exactmatch2"
|
|
"[\"Hagen\"] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
2.3.2 Specification of operator ~exactmatchS~
|
|
|
|
*/
|
|
const string ExactMatchSSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x Tk -> stream(tuple((id tid)))";
|
|
string spec = "_ exactmatchS [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all tuple identifiers"
|
|
" where the key matches argument value Tk";
|
|
string example = "query Staedte_SName_btree2 exactmatchS[\"Bochum\"]"
|
|
" Staedte gettuples consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
2.3.3 Specification of operator ~exactmatch~
|
|
|
|
*/
|
|
const string ExactMatchSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x rel(tuple(T)) x Tk -> "
|
|
"stream(tuple(T))";
|
|
string spec = "_ _ exactmatch [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all tuples in the "
|
|
"given relation with key = argument value Tk";
|
|
string example = "query Staedte_SName_btree2 Staedte exactmatch"
|
|
"[\"Dortmund\"] count";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
2.4 Definition of operators ~exactmatch2~, ~exactmatchS~, ~exactmatch~
|
|
|
|
2.4.1 Definition of operator ~exactmatch2~
|
|
|
|
*/
|
|
Operator rangebtree2::exactmatch2 (
|
|
"exactmatch2", // name
|
|
ExactMatch2Spec(), // specification
|
|
RangeQuery<EXACTMATCH2>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<EXACTMATCH2> // type mapping
|
|
);
|
|
|
|
/*
|
|
2.4.2 Definition of operator ~exactmatchS~
|
|
|
|
*/
|
|
Operator rangebtree2::exactmatchS (
|
|
"exactmatchS", // name
|
|
ExactMatchSSpec(), // specification
|
|
RangeQuery<EXACTMATCHS>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<EXACTMATCHS> // type mapping
|
|
);
|
|
|
|
|
|
/*
|
|
2.4.3 Definition of operator ~exactmatch~
|
|
|
|
*/
|
|
Operator rangebtree2::exactmatch (
|
|
"exactmatch", // name
|
|
ExactMatchSpec(), // specification
|
|
RangeQuery<EXACTMATCH>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<EXACTMATCH> // type mapping
|
|
);
|
|
|
|
|
|
/*
|
|
3 Operators ~range2~, ~rangeS~, ~range~
|
|
|
|
The operator ~range2~ uses the given btree2 to find all stored keys or
|
|
(key-value)-pairs of the btree2 with key $ >= $ Tk argument value 1 and
|
|
key $ <= $ Tk argument value 2.
|
|
The operator ~rangeS~ uses the given btree2 to find all stored tuple
|
|
identifiers referencing tuples with key $ >= $ Tk argument value 1 and
|
|
key $ <= $ Tk argument value 2.
|
|
The operator ~range~ uses the given btree2 to find all tuples in the
|
|
given relation with key $ >= $ Tk argument value 1 and key $ <= $ Tk argument
|
|
value 2.
|
|
The stream is empty, if (Tk argument value 2) $ < $ (Tk argument value 1)
|
|
or the given range includes no key.
|
|
|
|
The signatures are
|
|
|
|
----
|
|
range2: (btree2 Tk none u) x Tk x Tk --> stream(tuple((Key Tk)))
|
|
range2: (btree2 Tk Td u) x Tk x Tk --> stream(tuple((Key Tk) (Data Td)))
|
|
|
|
rangeS: (btree2 Tk tid multiple) x Tk x Tk --> stream(tuple((id tid)))
|
|
|
|
range: (btree2 Tk tid multiple) x rel(tuple(T)) x Tk x Tk --> stream(tuple(T))
|
|
|
|
----
|
|
|
|
|
|
3.1 Type mapping function of operators ~range2~, ~rangeS~, ~range~
|
|
|
|
The same as for ~exactmatch2~, ~exactmatchS~ and ~exactmatch~.
|
|
The template parameter operatorId specifies the range operator. The operator ~range2~
|
|
with value 27 needs (27 div 9 =) 3 parameters and is a range2-type with code (27 mod 3 =) 0,
|
|
the operator ~rangeS~ with value 28 needs (28 div 9 =) 3 parameters, too, and is a
|
|
rangeS-type with code (28 mod 3 =) 1 and finally the operator ~range~ with value 38
|
|
needs (38 div 9 =) 4 parameters and is a range-type with code (38 mod 3 =) 2.
|
|
|
|
|
|
3.2 Value mapping function of operators ~range2~, ~rangeS~, ~range~
|
|
|
|
The same as for ~exactmtach2~, ~exactmatchS~ and ~exactmatch~. The template parameter
|
|
operatorId specifies the range operator, a detailled description is given with the
|
|
type mapping function of the operators ~range2~, ~rangeS~ and ~range~.
|
|
|
|
|
|
3.3 Specification of operators ~range2~, ~rangeS~, ~range~
|
|
|
|
3.3.1 Specification of operator ~range2~
|
|
|
|
*/
|
|
const string Range2Spec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk none u) x Tk x Tk -> stream(tuple((Key Tk)))\n"
|
|
"(btree2 Tk Td u) x Tk x Tk -> stream(tuple((Key Tk) "
|
|
"(Data Td)))";
|
|
string spec = "_ range2 [ _ , _ ]";
|
|
string meaning = "Uses the given btree2 to find all stored keys or "
|
|
"(key-value)-pairs of the btree2 "
|
|
"with key >= Tk argument value 1"
|
|
" and key <= Tk argument value 2";
|
|
string example = "query Staedte_Bev_btree2 range2[105000, 200000] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
3.3.2 Specification of operator ~rangeS~
|
|
|
|
*/
|
|
const string RangeSSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x Tk x Tk -> "
|
|
"stream(tuple((id tid)))";
|
|
string spec = "_ rangeS [ _ , _ ]";
|
|
string meaning = "Uses the given btree2 to find all stored "
|
|
"tuple identifiers referencing tuples "
|
|
"with key >= Tk argument value 1"
|
|
" and key <= Tk argument value 2";
|
|
string example = "query Staedte_Bev_btree2 rangeS[100000, 500000] "
|
|
"Staedte gettuples consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
3.3.3 Specification of operator ~range~
|
|
|
|
*/
|
|
const string RangeSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x rel(tuple(T)) x Tk x Tk"
|
|
" -> stream(tuple(T))";
|
|
string spec = "_ _ range [ _ , _ ]";
|
|
string meaning = "Uses the given btree2 to find all tuples in the "
|
|
"given relation with key >= Tk argument value 1"
|
|
" and key <= Tk argument value 2";
|
|
string example = "query Staedte_Bev_btree2 Staedte range"
|
|
"[250000, 400000] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
3.4 Definition of operators ~range2~, ~rangeS~, ~range~
|
|
|
|
3.4.1 Definition of operator ~range2~
|
|
|
|
*/
|
|
Operator rangebtree2::range2 (
|
|
"range2", // name
|
|
Range2Spec(), // specification
|
|
RangeQuery<RANGE2>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<RANGE2> // type mapping
|
|
);
|
|
|
|
/*
|
|
3.4.2 Definition of operator ~rangeS~
|
|
|
|
*/
|
|
Operator rangebtree2::rangeS (
|
|
"rangeS", // name
|
|
RangeSSpec(), // specification
|
|
RangeQuery<RANGES>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<RANGES> // type mapping
|
|
);
|
|
|
|
/*
|
|
3.4.3 Definition of operator ~range~
|
|
|
|
*/
|
|
Operator rangebtree2::range (
|
|
"range", // name
|
|
RangeSpec(), // specification
|
|
RangeQuery<RANGE>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<RANGE> // type mapping
|
|
);
|
|
|
|
/*
|
|
4 Operators ~leftrange2~, ~leftrangeS~, ~leftrange~
|
|
|
|
The operator ~leftrange2~ uses the given btree2 to find all stored keys or
|
|
(key-value)-pairs of the btree2 with key $ <= $ argument value Tk.
|
|
The operator ~leftrangeS~ uses the given btree2 to find all stored tuple
|
|
identifiers referencing tuples with key $ <= $ argument value Tk.
|
|
The operator ~leftrange~ uses the given btree2 to find all tuples in the
|
|
given relation with key $ <= $ argument value Tk.
|
|
|
|
The signatures are
|
|
|
|
----
|
|
leftrange2: (btree2 Tk none u) x Tk --> stream(tuple((Key Tk)))
|
|
leftrange2: (btree2 Tk Td u) x Tk --> stream(tuple((Key Tk) (Data Td)))
|
|
|
|
leftrangeS: (btree2 Tk tid multiple) x Tk --> stream(tuple((id tid)))
|
|
|
|
leftrange: (btree2 Tk tid multiple) x rel(tuple(T)) x Tk --> stream(tuple(T))
|
|
|
|
----
|
|
|
|
|
|
4.1 Type mapping function of operators ~leftrange2~, ~leftrangeS~, ~leftrange~
|
|
|
|
The same as for ~exactmtach2~, ~exactmatchS~ and ~exactmatch~.
|
|
The template parameter operatorId specifies the range operator. The operator ~leftrange2~
|
|
with value 21 needs (21 div 9 =) 2 parameters and is a range2-type with code (21 mod 3 =) 0,
|
|
the operator ~leftrangeS~ with value 22 needs (22 div 9 =) 2 parameters, too, and is a
|
|
rangeS-type with code (22 mod 3 =) 1 and finally the operator ~leftrange~ with value 32
|
|
needs (32 div 9 =) 3 parameters and is a range-type with code (32 mod 3 =) 2.
|
|
|
|
|
|
4.2 Value mapping function of operators ~leftrange2~, ~leftrangeS~, ~leftrange~
|
|
|
|
The same as for ~exactmatch2~, ~exactmatchS~ and ~exactmatch~. The template parameter
|
|
operatorId specifies the range operator, a detailled description is given with the
|
|
type mapping function of the operators ~leftrange2~, ~leftrangeS~ and ~leftrange~.
|
|
|
|
|
|
4.3 Specification of operators ~leftrange2~, ~leftrangeS~, ~leftrange~
|
|
|
|
4.3.1 Specification of operator ~leftrange2~
|
|
|
|
*/
|
|
const string LeftRange2Spec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk none u) x Tk -> stream(tuple((Key Tk)))\n"
|
|
"(btree2 Tk Td u) x Tk -> stream(tuple((Key Tk) "
|
|
"(Data Td)))";
|
|
string spec = "_ leftrange2 [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all stored keys or "
|
|
"(key-value)-pairs of the btree "
|
|
"with key <= argument value Tk";
|
|
string example = "query Staedte_Bev_btree2 leftrange2[150000] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
4.3.2 Specification of operator ~leftrangeS~
|
|
|
|
*/
|
|
const string LeftRangeSSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x Tk -> stream(tuple((id tid)))";
|
|
string spec = "_ leftrangeS [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all stored "
|
|
"tuple identifiers referencing tuples "
|
|
"with key <= argument value Tk";
|
|
string example = "query Staedte_Bev_btree2 leftrangeS[250000] Staedte "
|
|
"gettuples consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
4.3.3 Specification of operator ~leftrange~
|
|
|
|
*/
|
|
const string LeftRangeSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x rel(tuple(T)) x Tk -> "
|
|
"stream(tuple(T))";
|
|
string spec = "_ _ leftrange [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all tuples in the "
|
|
"given relation with key <= argument value Tk";
|
|
string example = "query Staedte_Bev_btree2 Staedte leftrange"
|
|
"[500000] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
4.4 Definition of operators ~leftrange2~, ~leftrangeS~, ~leftrange~
|
|
|
|
4.4.1 Definition of operator ~leftrange2~
|
|
|
|
*/
|
|
Operator rangebtree2::leftrange2 (
|
|
"leftrange2", // name
|
|
LeftRange2Spec(), // specification
|
|
RangeQuery<LEFTRANGE2>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<LEFTRANGE2> // type mapping
|
|
);
|
|
|
|
/*
|
|
4.4.2 Definition of operator ~leftrangeS~
|
|
|
|
*/
|
|
Operator rangebtree2::leftrangeS (
|
|
"leftrangeS", // name
|
|
LeftRangeSSpec(), // specification
|
|
RangeQuery<LEFTRANGES>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<LEFTRANGES> // type mapping
|
|
);
|
|
|
|
/*
|
|
4.4.3 Definition of operator ~leftrange~
|
|
|
|
*/
|
|
Operator rangebtree2::leftrange (
|
|
"leftrange", // name
|
|
LeftRangeSpec(), // specification
|
|
RangeQuery<LEFTRANGE>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<LEFTRANGE> // type mapping
|
|
);
|
|
|
|
/*
|
|
5 Operators ~rightrange2~, ~rightrangeS~, ~rightrange~
|
|
|
|
The operator ~rightrange2~ uses the given btree2 to find all stored keys or
|
|
(key-value)-pairs of the btree2 with key $ >= $ argument value Tk.
|
|
The operator ~rightrangeS~ uses the given btree2 to find all stored tuple
|
|
identifiers referencing tuples with key $ >= $ argument value Tk.
|
|
The operator ~rightrange~ uses the given btree2 to find all tuples in the
|
|
given relation with key $ >= $ argument value Tk.
|
|
|
|
The signatures are
|
|
|
|
----
|
|
rightrange2: (btree2 Tk none u) x Tk --> stream(tuple((Key Tk)))
|
|
rightrange2: (btree2 Tk Td u) x Tk --> stream(tuple((Key Tk) (Data Td)))
|
|
|
|
rightrangeS: (btree2 Tk tid multiple) x Tk --> stream(tuple((id tid)))
|
|
|
|
rightrange: (btree2 Tk tid multiple) x rel(tuple(T)) x Tk --> stream(tuple(T))
|
|
|
|
----
|
|
|
|
|
|
5.1 Type mapping function of operators ~rightrange2~, ~rightrangeS~, ~rightrange~
|
|
|
|
The same as for ~exactmatch2~, ~exactmatchS~ and ~exactmatch~.
|
|
The template parameter operatorId specifies the range operator. The operator ~rightrange2~
|
|
with value 24 needs (24 div 9 =) 2 parameters and is a range2-type with code (24 mod 3 =) 0,
|
|
the operator ~rightrangeS~ with value 25 needs (25 div 9 =) 2 parameters, too, and is a
|
|
rangeS-type with code (25 mod 3 =) 1 and finally the operator ~rightrange~ with value 35
|
|
needs (35 div 9 =) 3 parameters and is a range-type with code (35 mod 3 =) 2.
|
|
|
|
|
|
5.2 Value mapping function of operators ~rightrange2~, ~rightrangeS~, ~rightrange~
|
|
|
|
The same as for ~exactmtach2~, ~exactmatchS~ and ~exactmatch~. The template parameter
|
|
operatorId specifies the range operator, a detailled description is given with the
|
|
type mapping function of ~rightrange2~, ~rightrangeS~ and ~rightrange~.
|
|
|
|
|
|
5.3 Specification of operators ~rightrange2~, ~rightrangeS~, ~rightrange~
|
|
|
|
5.3.1 Specification of operator ~rightrange2~
|
|
|
|
*/
|
|
const string RightRange2Spec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk none u) x Tk -> stream(tuple((Key Tk)))\n"
|
|
"(btree2 Tk Td u) x Tk -> stream(tuple((Key Tk) "
|
|
"(Data Td)))";
|
|
string spec = "_ rightrange2 [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all stored keys or "
|
|
"(key-value)-pairs of the btree "
|
|
"with key >= argument value Tk";
|
|
string example = "query Staedte_Bev_btree2 rightrange2[500000] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
5.3.2 Specification of operator ~rightrangeS~
|
|
|
|
*/
|
|
const string RightRangeSSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x Tk -> stream(tuple((id tid)))";
|
|
string spec = "_ rightrangeS [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all stored "
|
|
"tuple identifiers referencing tuples "
|
|
"with key >= argument value Tk";
|
|
string example = "query Staedte_Bev_btree2 rightrangeS[1500000] Staedte "
|
|
"gettuples consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
5.3.3 Specification of operator ~rightrange~
|
|
|
|
*/
|
|
const string RightRangeSpec() {
|
|
string header = "\"Signature\" \"Syntax\" \"Meaning\" \"Example\"";
|
|
string sig = "(btree2 Tk tid multiple) x rel(tuple(T)) x Tk -> "
|
|
"stream(tuple(T))";
|
|
string spec = "_ _ rightrange [ _ ]";
|
|
string meaning = "Uses the given btree2 to find all tuples in the "
|
|
"given relation with key >= argument value Tk";
|
|
string example = "query Staedte_Bev_btree2 Staedte rightrange"
|
|
"[1000000] consume";
|
|
|
|
return "( ( "+header + ") ( " +
|
|
"<text>"+sig+"</text--->" +
|
|
"<text>"+spec+"</text--->" +
|
|
"<text>"+meaning+"</text--->" +
|
|
"<text>"+example+"</text--->" +
|
|
" ) )";
|
|
}
|
|
|
|
/*
|
|
5.4 Definition of operators ~rightrange2~, ~rightrangeS~, ~rightrange~
|
|
|
|
5.4.1 Definition of operator ~rightrange2~
|
|
|
|
*/
|
|
Operator rangebtree2::rightrange2 (
|
|
"rightrange2", // name
|
|
RightRange2Spec(), // specification
|
|
RangeQuery<RIGHTRANGE2>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<RIGHTRANGE2> // type mapping
|
|
);
|
|
|
|
/*
|
|
5.4.2 Definition of operator ~rightrangeS~
|
|
|
|
*/
|
|
Operator rangebtree2::rightrangeS (
|
|
"rightrangeS", // name
|
|
RightRangeSSpec(), // specification
|
|
RangeQuery<RIGHTRANGES>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<RIGHTRANGES> // type mapping
|
|
);
|
|
|
|
/*
|
|
5.4.3 Definition of operator ~rightrange~
|
|
|
|
*/
|
|
Operator rangebtree2::rightrange (
|
|
"rightrange", // name
|
|
RightRangeSpec(), // specification
|
|
RangeQuery<RIGHTRANGE>, // value mapping
|
|
Operator::SimpleSelect, // selection function
|
|
RangeTypeMap<RIGHTRANGE> // type mapping
|
|
);
|
|
|
|
|
|
} // end namespace operators
|
|
} // end namespace btree2algebra
|
|
|