查看“关系代数”的源代码

关系代数 （Relational Algebra）

=集合运算=

==集合（Set）==

For a set of integers: S = {1, 2, 3, 1000}. Set operations include:

membership test: x ∈ S?

Set intersection: S1 ∩ S2

Set union: S1 ∪ S2

Set differences: S1 ∖ S2

Jaccard Index (Tanimoto similarity) ∣S1 ∩ S2 ∣/∣S1 ∪ S2 ∣

==有序集合（Ordered Set） ==

* Iterate: 

in sorted order,

in reverse order,

skippable iterators (jump to first value ≥ x)

* Rank:  how many elements of the set are smaller than k? (counting the number of ones up to a given position)

* Select: find the kth smallest value (finding the position of the k-th bit set)

* Min/max: find the maximal and minimal value

[https://lucene.apache.org/core/4_5_0/core/org/apache/lucene/util/BroadWord.html Broadword Implementation of Rank/Select Queries]

研究论文：
# Vigna, Sebastiano. "Broadword implementation of rank/select queries." In International Workshop on Experimental and Efficient Algorithms, WEA 2008.