中文摘要：

表连接是关系数据库中最重要的操作之一,在数据流管理系统中同样重要.构建StreamCube的聚集查询时,数据流与超大维表（如IPaddress维表）作表连接将耗费大量有限的计算资源和内存.超大维表需划分为多个块,分块读入内存,造成磁盘I/O频繁.根据维表及其连接键层的特性,降低维表与数据流连接的连接键冗余,将维表无损压缩为可装入内存的连接键范围维表（RJ-DT）,引出数据流上非等值连接问题;并提出一种超大维表多表连接算法——多动态索引嵌套循环连接算法（multi dynamicindex nested-loopjoin）,该算法实现数据流与压缩维表高效的非等值连接,并拓展为多表连接.理论分析及实验结果表明,该算法可使超大维表连接性能明显改善,最高可达到一个数量级的加速并具有很强的实用性.

英文摘要：

Join is one of the most important operations in relational database,and is also important in data stream management system.In group-bys which construct StreamCube,join will be done before them,and join between data stream and huge dimension tables（such as IPaddress table） would consume limited power of CPU and capacity of memory.Generally,a huge dimension table must be partitioned into small tables and each partition table is loaded into memory in turn that causes frequent disk IO.To avoid this shortage,it compress huge dimension tables losslessly by taking characters of dimension tables and their join-key layer into account and finding join-key redundancies in those tables.So,one dimension table with n concept columns is compressed into n ranged join-key dimension tables（RJ-DT） by reducing join-key redundancies and using decomposed of storage model of column-store.Each RJ-DT is composed of start and end columns and several concept columns.However,a new issue that non-equijoin called range join between data stream and RJ-DT is brought out.Then,it proposes a multi-join algorithm of huge dimension table,called multi dynamic index nested-loop join（MDI-NL）,which implements non-equijoin efficiently,also supports multi-join.MDI-NL constructs RB＋Tree index of each RJ-DT before join.In join operation,it dispatches index dynamically referring to demand of group-by which get the exact smallest index and makes MDI-NL more powerful.Through theoretical analysis and extensive experiments,it is found that MDI-NL outperforms other join algorithms by an order of magnitude for huge dimension table join and has a strong practicability.