关系Top-N查询处理和优化

   Top-N查询(也称Top-K查询，排序查询或kNN查询等)检索出N个元组使其优选地匹配，但不一定接近匹配查询条件，并按指定的排序函数对输出的结果集合排序。本书主要内容包括三类Top-N查询的处理和优化。1．基于数值属性的Top-N查询，即"数值Top-N查询"包括:（1）基于学习的Top-N查询处理方法；（2）基于区域聚类的多Top-N查询优化；（3）Top-N查询流处理和优化。2．对于文本属性，在数据库中对关键词搜索得到Top-N结果，即"关键词Top-N查询"。3.对于具有自然语言语义的文本属性，基于语义相似度/语义距离的Top-N查询，即"语义Top-N查询"。

   序

前言

第1章绪论1

1.1数学概念和术语1

1.1.1集合及其运算2

1.1.2度量空间4

1.2关系数据库8

1.2.1关系模式8

1.2.2关系代数10

1.2.3规范化理论13

1.2.4关系模式的分解17

1.3Top-N查询模式19

1.3.1距离空间KNN查询19

1.3.2单调排序函数的Top-K查询20

1.3.3数值属性的关系Top-N查询22

参考文献26

第2章基于学习的Top-N查询处理28

2.1关系Top-N查询处理28

2.1.1基于直方图的方法30

2.1.2基于抽样的方法31

2.1.3数据维数对查询处理的影响32

2.2基于学习的Top-N查询处理方法33

2.2.1查询信息的存储33

2.2.2新提交查询的处理34

2.2.3知识库P的维护38

2.2.4知识库P的稳定性40

2.3实验与数据分析43

2.3.1数据集和准备43

2.3.2性能比较46

2.3.3LB方法的其他实验48

2.3.4重复查询的效果52

2.3.5知识库的稳定性53

2.4本章小结58

参考文献59

第3章基于区域聚类的多Top-N查询优化61

3.1问题分析61

3.2区域聚类64

3.2.1算法和术语65

3.2.2区域聚类模型71

3.3多个Top-N查询搜索区域的聚类73

3.4Top-N元组检索76

3.4.1搜索Top-N元组76

3.4.2确保获得Top-N元组77

3.5实验与数据分析78

3.5.1数据集和准备78

3.5.2通过训练确定聚类模型和阈值80

3.5.3性能比较82

3.6本章小结和相关研究87

参考文献88

第4章基于知识库的Top-N查询流处理89

4.1问题分析89

4.2Top-N查询流的处理92

4.2.1术语和结构93

4.2.2LRC方法与LB和RCM的对比94

4.2.3知识库的创建95

4.2.4处理新提交的Top-N查询98

4.2.5确保得到所有Top-N元组100

4.3知识库的维护101

4.3.1简档集合的维护101

4.3.2*和t-List的维护101

4.4性能分析101

4.4.1空间开销101

4.4.2时间开销102

4.5实验与数据分析103

4.5.1数据集和准备104

4.5.2耗用时间105

4.5.3I/O请求次数109

4.5.4检索元组的数目110

4.5.5知识库的空间开销113

4.5.6查询结果不同N值的影响114

4.5.7实验小结116

4.6本章小结116

参考文献117

第5章基于语义距离的Top-N查询处理118

5.1亲缘词和语义距离120

5.1.1亲缘词120

5.1.2语义距离和Top-N查询121

5.1.3排序方式比较124

5.2查询的语义搜索125

5.2.1索引创建过程126

5.2.2w-索引的结构和创建129

5.2.3w-索引的维护131

5.2.4查询处理131

5.3实验与数据分析135

5.3.1数据集和准备135

5.3.2实验结果138

5.4本章小结144

参考文献144

第6章基于索引技术的中文关键词Top-N查询处理146

6.1引言146

6.2相关工作149

6.3索引和索引表150

6.3.1索引表的创建152

6.3.2索引表的维护155

6.4中文关键词Top-N查询处理156

6.4.1候选元组查找和排序结构157

6.4.2候选元组生成157

6.4.3相似度159

6.4.4获得查询结果160

6.4.5相似度的短语修正160

6.4.6时间和空间开销162

6.5实验与数据分析163

6.5.1单表数据库163

6.5.2多表数据库165

6.6本章小结169

参考文献170

第7章N维赋范空间中的Top-N查询处理172

7.1查询模式和理论分析172

7.2Top-N查询处理算法175

7.2.1关于一般范数的算法176

7.2.2关于x-单调范数的算法183

7.3缓冲区大小和很优性187

7.3.1G-算法和m-算法缓冲区的大小187

7.3.2m-算法的伪实例很优性187

7.3.3NNS优化算法和TA-类算法的比较191

7.4实验与数据分析192

7.4.1数据集和准备193

7.4.2处理查询耗用的时间193

7.4.3顺序访问次数195

7.4.4不同结果大小N的影响196

7.4.5算法性能比较197

7.5本章小结199

参考文献200