algebra.mx

一个内存数据库的源代码这是服务器端还有客户端

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f algebra
@a Peter Boncz, Martin Kersten, Niels Nes
@v 2.0
@+ BAT Algebra
This modules contains the most common algebraic BAT manipulation
commands. We call them @#algebra@, because all operations take
values as parameters, and produce new result values, but
@%do not modify their parameters@.
@
Unlike the previous Monet versions, we reduce the number
of functions returning a BAT reference. This was previously needed
to simplify recursive bat-expression and manage reference counts.
In the current version we return only a BAT identifier when a new
bat is being created.
@-
All parameters to the modules are passed by reference.
In particular, this means that
string values are passed to the module layer as (str *)
and we have to de-reference them before entering the gdk library.
This calls for knowlegde on the underlying BAT typs`s
@{
@= derefStr
{int _tpe= ATOMstorage(@1->@2type);
 if( _tpe == TYPE_str || _tpe > TYPE_str )
 { if(@3== 0 || *(str*)@3==0) @3 = (str)str_nil;
   else @3 = *(str *)@3;
}}

@
We split between selections that return one value, and selections
that return a BAT.
@+ Value Selections
@mal
module algebra;

command exist(b:bat[:any_1,:any_2], h:any_1):bit 
address ALGexist
comment "Returns whether 'h' occurs as a head value in b.";

command exist(b:bat[:any_1,:any_2], h:any_1, t:any_2):bit 
address ALGexistBUN
comment "Returns true when 'h,t' occurs as a bun in b.";

command find(b:bat[:any_1,:any_2], h:any_1):any_2 
address ALGfind
comment "Returns the tail value 't' for which some [h,t] BUN 
	exists in b.  If no such BUN exists, an error occurs." ;

command position(b:bat[:any_1,:any_2], v:any_1):int
address ALGposition
comment "Returns BAT position [0.. b.count] of 'v' in the head 
	column of b. It Return an error if 'v' does not exist.";

command position(b:bat[:any_1,:any_2], val:any_1, tval:any_2) :int 
address ALGpositionBUN
comment "Returns the position of the value pair It returns an 
	error if 'val' does not exist.";

command fetch(b:bat[:any_2,:any_1], x:oid) :any_1 
address ALGfetchoid;
command fetch(b:bat[:any_2,:any_1], x:lng) :any_1 
address ALGfetch;
command fetch(b:bat[:any_2,:any_1], x:int) :any_1 
address ALGfetchint
comment "Returns the tail value of the BUN at x-th position 
	with 0 <= x < b.count";

@+ BAT Selections
The operations are grouped by positional and range selections.
A simple sampling operation is also provided.
@- Positional selection
@mal
command fetch(b:bat[:any_1,:any_2], s:bat[:int,:any_3]) :bat[:any_1,:any_2] 
address ALGfetchbat;
command fetch(b:bat[:any_1,:any_2], s:bat[:lng,:any_3] ) :bat[:any_1,:any_2] 
address ALGfetchbat;
command fetch(b:bat[:any_1,:any_2], s:bat[:oid,:any_3]) :bat[:any_1,:any_2] 
address ALGfetchbat
comment "Returns a positional selection of b by the oid 
	head values of s";

@- Range selection
The range selections are targeted at the tail of the BAT.
@mal
command select(b:bat[:any_1,:any_2], low:any_2, high:any_2) 
		:bat[:any_1,:any_2] 
address ALGselect
comment "Select all BUNs that have tail values: {v| low <= v <= high}.
	NIL boundary values have a special meaning.
		+ low  == nil means: no lower bound
		+ high == nil means: no upper bound.
		NOTE 1: you should cast the nil to the appropriate type, 
				e.g. int(nil) in order to cirumvent type clashes.
		NOTE 2: as the 'nil' element has no clear place in the 
				ordered domain of values, tuples with 'nil' values 
				are NEVER returned by the range select.";

command select(b:bat[:any_1,:any_2], low:any_2, 
	high:any_2, li:bit, hi:bit) :bat[:any_1,:any_2] 
address ALGselectInclusive
comment "Select all BUNs that have tail values: {v| low <{=} v <{=} high}.
	Boundary inclusion is indicated separately.
	NIL boundary values have a special meaning.
	+ low  == nil means: no lower bound
	+ high == nil means: no upper bound.";

command select(b:bat[:any_1,:any_2],value:any_2) :bat[:any_1,:any_2] 
address ALGselect1
comment "Select all BUNs of a BAT with a certain 
	tail value. Selection on NIL is also 
	possible (it should be properly casted, 
	e.g.:int(nil)).";

command selectNotNil(b:bat[:any_1,:any_2]):bat[:any_1,:any_2]
address ALGselectNotNil
comment "Select all not-nil values";
@-
The second group uses the head to perform the range selection.
@mal
command selectH(b:bat[:any_1,:any_2], low:any_1, high:any_1) 
			:bat[:any_1,:any_2] 
address ALGselectHead;

command selectH(b:bat[:any_1,:any_2], low:any_1, 
	high:any_1, li:bit, hi:bit) :bat[:any_1,:any_2] 
address ALGselectInclusiveHead;

command selectH(b:bat[:any_1,:any_2],value:any_1) :bat[:any_1,:any_2] 
address ALGselect1Head;
@-
A special case for this set are the void tailed bats.
@mal
command select(b:bat[:any_2,:void], low:any_2) 
		:bat[:any_2,:void] 
address ALGselect1Head;
command select(b:bat[:any_2,:void], low:any_2, high:any_2) 
		:bat[:any_2,:void] 
address ALGselectHead;
command select(b:bat[:any_2,:void], low:any_2, high:any_2,li:bit, hi:bit) 
		:bat[:any_2,:void] 
address ALGselectInclusiveHead;

@-
The second group uses the head to perform the range selection
@mal

command fragment ( b:bat[:any_1,:any_2], hlow:any_1, hhigh:any_1,
		tlow:any_2, thigh:any_2 ) :bat[:any_1,:any_2] 
address ALGfragment
comment "Select both on head and tail range.";

command slice(b:bat[:any_1,:any_2], x:lng, y:lng) :bat[:any_1,:any_2] 
address ALGslice
comment "Return the slice with the BUNs at position x till y.";

command slice(b:bat[:any_1,:any_2], x:int, y:int) :bat[:any_1,:any_2] 
address ALGslice_int
comment "Return the slice with the BUNs at position x till y.";

command topN( b:bat[:any_1,:any_2], top:lng ) :bat[:any_1,:any_2]
address ALGtopN
comment "Trim all but the top N tuples.";

command groupby(b:bat[:any_1,:int]) :bat[:any_1,:oid] 
address ALGgroupby
comment "Produces a new BAT with groups identified by the head column. The result contains tail times the head value, ie the tail contains the result group sizes.";

command uselect(b:bat[:any_1,:any_2], low:any_2, high:any_2, 
		li:bit, hi:bit) :bat[:any_1,:oid] 
address ALGuselectInclusive
comment "See select() but limited to head values";

command uselect(b:bat[:any_1,:any_2], low:any_2, high:any_2):bat[:any_1,:oid] 
address ALGuselect;
command uselect(b:bat[:any_1,:any_2], value:any_2) :bat[:any_1,:oid] 
address ALGuselect1
comment "Value select, but returning only the 
	head values. SEE ALSO:select(bat,val)";
@- Pattern matching
@mal
command like(b:bat[:any_1,:str], substr:str) :bat[:any_1,:str]
address ALGlike
comment "Selects all elements that have 'substr' as in the tail.";

@- Sampling
@mal
command sample ( b:bat[:oid,:any_2], num:int ) :bat[:oid,:any_2] 
address ALGsample
comment "Produce a random selection of size 'num' from the input BAT.";
@+ BAT copying
@mal
command copy( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGcopy
comment "Returns physical copy of a BAT.";
@- Sorted copy
@mal
command sort( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGhsort
comment "Returns a BAT copy sorted on the head column.";
command sortReverse( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGhsort_rev
comment "Returns a BAT copy reversely sorted on the tail column.";

command sortTail( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGtsort
comment "Returns a BAT copy sorted on the tail column.";
command sortReverseTail( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGtsort_rev
comment "Returns a BAT copy reversely sorted on the tail column.";

command sortHT( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGhtsort
comment "Returns a lexicographically sorted copy on head,tail.";
command sortTH( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2] 
address ALGthsort
comment "Returns a lexicographically sorted copy on tail,head.";

command ssort( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2]
address ALGssort
comment "Returns copy of a BAT with the BUNs sorted on ascending head values.
         This is a stable sort.";
command ssort_rev( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2]
address ALGssort_rev
comment "Returns copy of a BAT with the BUNs sorted on descending head values.
         This is a stable sort.";

command revert( b:bat[:any_1,:any_2]) :bat[:any_1,:any_2]
address ALGrevert
comment "Returns a BAT copy with buns in reverse order";

@+ Set operations
Sets in Monet can be viewed in two ways:
(1) by looking at both columns of a BAT together (Set-, or s-operators).
(2) by looking at the head column only (Key- or k-operators).
(3) by looking at the tail column only (Tail key- or t-operators).
For this reason, all standard set operations come in three flavors:
k-@emph{operand} series, which look only at the head column, 
t-@emph{operand} series, which look only at the tail column, and
s-@emph{operand} series, that look at the whole BUN.

@noindent Operands provided are:
@itemize
@item [s,k,t]unique(bat[:any_1,:any_2]) :bat[:any_1,:any_2]
produces a copy of the bat, with double elimination
@item [s,k,t]union(bat[:any_1,:any_2],bat[:any_1,:any_2]) :bat[:any_1,:any_2]
bat union.
@item [s,k,t]difference(bat[:any_1,:any_2],bat[:any_1,:any_2]) :bat[:any_1,:any_2]
bat difference.
@item [s,k,t]intersection(bat[:any_1,:any_2],bat[:any_1,:any_2]) :bat[:any_1,:any_2]
bat intersection.
@end itemize
Implementations typically take two forms: if the input relation(s) is/are
ordered, a merge-algorithm is used. Otherwise, hash-indices are produced
on demand for the hash-based algorithms.@*
The [k,s]intersect(l,r) operations result in all BUNs of @emph{l} that
are also in @emph{r}. They do not do double-elimination over the @emph{l} BUNs.@*
The [k,s]difference(l,r) operations result in all BUNs of @emph{l} that are
not in @emph{r}. They do not do double-elimination over the @emph{l} BUNs.@*
The [k,s]union(l,r) operations result in all BUNs of l that are 
not in @emph{r}, plus all BUNs of @emph{r}. They do not do double-elimination
over the @emph{l} nor @emph{r} BUNs.@*
Operations with double-elimination can be formed by performing
[k,s]unique(l) on their operands.
The kintersect(l,r) is used also as implementation for the
@emph{semijoin()}.

The t-@emph{operand} series are cast into a k-@emph{operand}
expression enclosing it with a BATmirror.
@- Bun-unique elements
@mal
command unique (b:bat[:any_1,:any_2] ) :bat[:any_1,:any_2] 
address ALGsunique;
command sunique (b:bat[:any_1,:any_2] ) :bat[:any_1,:any_2] 
address ALGsunique
comment "Select unique tuples from the input BAT. Double elimination is 
		done over BUNs as a whole (head and tail).  Result is a BAT 
	with real set() semantics.";
@- Head-unique elements
@mal
command kunique ( b:bat[:any_1,:any_2] ) :bat[:any_1,:any_2] 
address ALGkunique
comment "Select unique tuples from the input BAT.  Double elimination is 
		done only looking at the head column. The result is a BAT with
		property hkeyed() == true.";

command tunique (b:bat[:any_1,:any_2] ) :bat[:any_1,:any_2] 
address ALGtunique
comment "Select unique tuples from the input BAT. Double elimination is 
		done over the BUNs tail. The result is a BAT with property
		tkeyd()== true";

@- Bun-intersecting elements
@mal
command intersect ( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2]) 
		:bat[:any_1,:any_2] 
address ALGsintersect;
command sintersect ( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2]) 
		:bat[:any_1,:any_2] 
address ALGsintersect
comment "Returns the intersection taken over *both* columns of two BATs. 
		Results in all BUNs of 'left' that are also in 'right'. Does *not* 
		do double-elimination over the 'left' BUNs, If you want this, use:
	 'sintersect(sunique(left),sunique(right))' 
	or: 'sunique(sintersect(left,right))'.";

@- Head-intersecting elements (a.k.a. semijoin)
@mal
command semijoin( left:bat[:any_1,:any_2], right:bat[:any_1,:any] ) 
		:bat[:any_1,:any_2] 
address ALGsemijoin
comment "Returns the intersection taken over only the *head* columns of 
		two BATs.  Results in all BUNs of 'left' that are also in 'right'. 
		Does *not* do double-elimination over the 'left' BUNs. 
		If you want this, use: 'kintersect(kunique(left),kunique(right))' 
	or: 'kunique(kintersect(left,right))'.";

command kintersect( left:bat[:any_1,:any_2], right:bat[:any_1,:any] ) 
		:bat[:any_1,:any_2] 
address ALGsemijoin
comment "Returns the intersection taken over only the *head* columns of two BATs. 
	Results in all BUNs of 'left' that are also in 'right'. 
		Does *not* do double- elimination over the 'left' BUNs.
		If you want this, use: 'kintersect(kunique(left),kunique(right))' 
	or: 'kunique(kintersect(left,right))'.";
@- Bun-differing elements
@mal
command difference( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2] ) 
		:bat[:any_1,:any_2] 
address ALGsdiff;
command sdifference( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2] ) 
		:bat[:any_1,:any_2] 
address ALGsdiff
comment "Returns the difference taken over *both* columns of two BATs. 
		Results in all BUNs of 'left' that are *not* in 'right'. 
		Does *not* do double-elimination over the 'left' BUNs. 
		If you want this, use:
		 'sdifference(left.sunique,right.sunique)' 
	or: 'sdifference(left,right).sunique'.";
@- Head-differing elements
@mal
command kdifference ( left:bat[:any_1,:any_2], right:bat[:any_1,:any] ) 
		:bat[:any_1,:any_2] 
address ALGkdiff
comment "Returns the difference taken over only the *head* columns of two BATs. 
		Results in all BUNs of 'left' that are *not* in 'right'. 
		It does *not* do double-elimination over the 'left' BUNs. 
		If you want this, use:
	 'kdifference(left.kunique,right.kunique)' 
	or: 'kdifference(left,right).kunique'.";
@- Unions on bun
@mal
command union ( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2]) 
		:bat[:any_1,:any_2] 
address ALGsunion;
command sunion ( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2]) 
		:bat[:any_1,:any_2] 
address ALGsunion
comment "Returns the union of two BATs; looking at both columns of both BATs.
		Results in all BUNs of 'left' that are  not in 'right', plus all 
		BUNs of 'right'.  *no* double-elimination is done. 
		If you want this, do:
	 'sunion(left.sunique,right.sunique)' 
	or: 'sunion(left,right).sunique'.";
@- Union on head
@mal
command kunion ( left:bat[:any_1,:any_2], right:bat[:any_1,:any_2])
		:bat[:any_1,:any_2] 
address ALGkunion
comment "Returns the union of two BATs; looking at head-columns only. 
		Results in all BUNs of 'left' that are  not in 'right', plus 
	all BUNs of 'right'.  *no* double-elimination is done. 
		If you want this, do:
	'kunion(left.kunique,right.kunique)' 
	or: 'sunion(left,right).kunique'.";
@+ Join operations
The core of every relational engine.
The join collection provided by the GDK kernel.
Note that joins over void columns are handled as if they are oids.
@mal
command crossproduct(left:bat[:any_1,:any_2], right:bat[:any_3,:any_4])
	:bat[:any_1,:any_4]
address ALGcross
comment "Returns the cross product";

command antijoin(left:bat[:any_1,:any_2], right:bat[:any_2,:any_4])
	:bat[:any_1,:any_4]
address ALGantijoin
comment "Returns the antijoin";

command join( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3])
		:bat[:any_1,:any_3] 
address ALGjoin
comment "Returns all BUNs, consisting of a head-value from 'left' and 
		a tail-value from 'right' for which there are BUNs in 'left' 
		and 'right' with equal tail- resp. head-value (i.e. the join
	columns are projected out).";

command join( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3])
		:bat[:any_1,:any_3] 
address ALGjoin;

command leftjoin( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3],
		estimate:lng) :bat[:any_1,:any_3] 
address ALGleftjoinestimate;
command join( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3],
		estimate:lng) :bat[:any_1,:any_3] 
address ALGjoinestimate;

command fetchjoin ( left:bat[:any_1,:oid], right:bat[:oid,:any_3] )
		:bat[:any_1,:any_3] 
address ALGfetchjoin
comment "Hook directly into the fetch implementation of the join.";

command leftfetchjoin ( left:bat[:any_1,:oid], right:bat[:oid,:any_3] )
		:bat[:any_1,:any_3] 
address ALGleftfetchjoin
comment "Hook directly into the left fetch join implementation.";

command mergejoin (left:bat[:any_1,:any_2], right:bat[:any_2,:any_3])
		:bat[:any_1,:any_3] 
address ALGmergejoin
comment "Hook directly into the merge implementation of the join.";

command hashjoin ( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3])
		:bat[:any_1,:any_3] 
address ALGhashjoin
comment "Hook directly into the hash implementation of the join.";

command indexjoin ( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3])
		:bat[:any_1,:any_3] 
address ALGindexjoin
comment "Hook directly into the index implementation of the join.";

@- Outer Join
@mal
command outerjoin( outer:bat[:any_1,:any_2], inner:bat[:any_2,:any_3]) 
		:bat[:any_1,:any_3] 
address ALGouterjoin
comment "Returns all the result of a join, plus the BUNS formed NIL in 
		the tail and the head-values of 'outer' whose tail-value does