注：考生属哪种类别请划“√”
（博士、在校硕士、工程硕士、师资硕士、同等学力、研究生班）
√
研 究 生 考 试 试 卷
考试时间：
考试科目： 分布式数据库
考生姓名：
评 卷 人：
考试分数： 注 意 事 项
1、考前研究生将上述项目填写清楚
2、字迹要清楚，保持卷面清洁
3、试题、试卷一齐交监考老师
4、教师将试题、试卷、成绩单，一起送研究生学院；
专业课报所在院、系
分布式数据库课程考试题签
一、说明分布式数据库系统的结构的特点（不低于 6 个）。
(1) 物理分布性
(2) 场地自治性
(3) 场地之间协作性
(4) 数据性
(5) 集中与自治相结合的控制机制
(6) 适当增加数据冗余度
(7) 事务管理的分布性
二、分布式查询处理的查询时间如何计算，根据数据在不同的场地分
布分别说明。
查询涉及多个库或者多张分表：
1.排序，即多个来源的数据查询出来以后，在应用层进行排序的工作。查出来如果是已经排序号的，则对多路进行归并排序否则就要进行一个全排序。
2.函数处理，即使用Max,Min,Sum,Count 等函数对多个数据来源的值进行相应的函数处理
3.求平均值，从多个数据来源进行查询时，需要把SQL改为查询SUM和Count，然后对多个数据来源的Sum求和，count求和后，计算平均值，这是需要注意的地方。
4非排序分页，这需要看具体实现所采取的策略，是同等步长地在多个数据源上分页处理，还是同等比例地分页处理。
5排序后分页。
二、分布式数据库系统的数据分片技术有哪些？分别说明。
三种分片方式：hash方式、一致性hash、按照数据范围（range based）。
hash方式：
哈希表（散列表）是最为常见的数据结构，根据记录（或者对象）的关键值将记录映射到表中的一个槽（slot），便于快速访问。绝大多数编程语言都有对hash表的支持，如python中的dict， C++中的map，Java中的Hashtable， Lua中的table等等。在哈希表中，最为简单的散列函数是 mod N（N为表的大小）。即首先将关键值计算出hash
值（这里是一个整型），通过对N取余，余数即在表中的位置。
一致性hash：
是将数据按照特征值映射到一个首尾相接的hash环上，同时也将节点（按照IP地址或者机器名hash）映射到这个环上。对于数据，从数据在环上的位置开始，顺时针找到的第一个节点即为数据的存储节点。
range based
简单来说，就是按照关键值划分成不同的区间，每个物理节点负责一个或者多个区间。其实这种方式跟一致性hash有点像，可以理解为物理节点在hash环上的位置是动态变化的。
四、数据库表的连接技术有哪些？基于 SQL 语言各举一例说明（DBMS
自选）。
1. 内连接（inner join）：内连接返回表A和表B在指定字段向匹配的行。
下面这句在MySql中返回的是A和B表的交叉连接（笛卡尔积），行数为A表行数乘以B表行数，但是不会生成数据表。
select * from A inner join B
2.左外链接：左外链接以左边的表为基准，左边表中的所有行都会返回，当右边表中
在指定字段有匹配时，返回匹配行。如果右表没有匹配时，返回右表所有字段为null的行
select * from A left join B on A.a = B.b
3.右外连接:右外连接除以右表为基准外与左外连接完全相同。
select * from A right join B on A.a = B.b
4.全外连接:以两边的表为基准，当某行在另一张表中没有匹配时，另一张表的列为空值。
select * from A full join B
5.交叉连接（笛卡尔积）:返回A中的每一行与B中的所有行进行连接的数据表 。返回的行数为：A的行数乘以B的行数。
select * from A cross join B
6.自然连接：自然连作用于其他连接之上，禁止指定连接列，且只能查询 * 信息。返回结果为去除重复列的连接表。等值连接要求连接的两张表中必须含有完全相同的字列（名字相同，类型可比）。
select * from A natural left join B
7.等值连接：在多表连接查询时只要是连接条件使用的是‘=’号都可以称之为等值连接，等值连接不会自动去除相同的属性列，且不要求连接的属性子列完全相同（不要求名
字相同，但类型必须可比）自然连接可以算是一种特殊的等值连接。
select * from A,B,C where A.a = B.b and B.b = C.c
五、何谓科学研究的四个范式？各自所处时代及研究方法。
第一范式 : 实验科学
人类最早的科学研究，主要以记录和描述自然现象为特征，又称为“实验科学”（第一范式），从原始的钻木取火，发展到后来以伽利略为代表的文艺复兴时期的科学发展初级阶段，开启了现代科学之门。指偏重于经验事实的描述和明确具体的实用性的科学，以归纳为主，带有较多盲目性的观测和实验。
其方法是先观察，进而假设，再根据假设进行实验。如果实验的结果与假设不符合，则修正假设再实验。
第二范式 : 理论科学
这种研究范式一直持续到19世纪末，都堪称完美，牛顿三大定律成功解释了经典力学，麦克斯韦理论成功解释了电磁学，经典物理学大厦美轮美奂。理论科学偏重理论总结和理性概括，强调较高普遍的理论认识而非直接实用意义的科学。
在研究方法上，以演绎法为主，不局限于描述经验事实。
第三范式 : 计算科学
20世纪中叶，John von Neumann提出了现代电子计算机架构，利用电子计算机对科学实验进行模拟仿真的模式得到迅速普及，人们可以对复杂现象通过模拟仿真，推演出越来越多复杂的现象，典型案例如模拟核试验、天气预报等。随着计算机仿真越来越多地取代实验，逐渐成为科研的常规方法，即第三范式：计算科学。
在实际应用中，计算科学主要用于对各个科学学科中的问题进行计算机模拟和其他形式的计算。典型的问题域包括：数值模拟，重建和理解已知事件（如地震、海啸和其他自然灾害），或预测未来或未被观测到的情况（如天气、亚原子粒子的行为）；模型拟合与数据分析，调整模型或利用观察来解方程（如石油勘探地球物理学、计算语言学，基于图的网络模型，复杂网络等）；计算和数学优化，最优化已知方案（如工艺和制造过程、运筹学等）。
第四范式 : 数据密集型科学
随着数据的爆炸性增长，计算机将不仅仅能做模拟仿真，还能进行分析总结，得到理论。数据密集范式理应从第三范式中分离出来，成为一个独特的科学研究范式。也就是说，过去由牛顿、爱因斯坦等科学家从事的工作，未来完全可以由计算机来做。这种科学研究的方式，被称为第四范式：数据密集型科学。数据密集型科学由传统的假设驱动向基于科学数据进行探索的科学方法的转变。
基于大数据的第四范式，则是先有了大量的已知数据，然后通过计算得出之前未知的理论。我们已经知道，大数据时代最大的转变，就是放弃对因果关系的渴求，取而代之关注相关关系。也就是说，只要知道“是什么”，而不需要知道“为什么”。
六、图示大数据分析的基本流程，各步骤的主要工作。
1．数据抽取与集成
由于大数据处理的数据来源类型丰富,大数据处理的第一步是对数据进行抽取和集成,从中提取出关系和实体,经过关联和聚合等操作,按照统一定义的格式对数据进行存储。现有的数据抽取和集成方法有三种:基于物化或数据仓库技术方法的引擎( Materialization or ETI Engine)、基于联邦数据库或中间件方法的引擎( Federation Engine or Mediator)、基于数据流方法的引擎( Stream Engine)
2．数据分析
数据分析是大数据处理流程的核心步骤,通过数据抽取和集成环节,我们已经从异构的数据源中获得了用于大数据处理的原始数据。用户可以根据自己的需求对这些数据进行分析处理,比如数据挖掘、机器学习、数据统计等。数据分析可以用于决策支持、商业智能、推荐系统、预测系统等。
3．数据解释
大数据处理流程中用户最关心的是数据处理的结果,正确的数据处理结果只有通过合适的展示方式才能被终端用户正确理解,因此数据处理结果的展示非常重要,可视化和人机
交互是数据解释的主要技术。
开发调试程序的时候经常通过打印语句的方式来呈现结果,这种方式非常灵活、方便,但只有熟悉程序的人才能很好地理解打印结果。
使用可视化技术,可以将处理的结果通过图形的方式直观地呈现给用户,标签云(Tag Cloud)、历史流( History Flow)空间信息流( Spatial Information Flow)等是常用的可视化技术,用户可以根据自己的需求灵活地使用这些可视化技术。人机交互技术可以引导用户对数据进行逐步的分析,使用户参与到数据分析的过程中,深刻地理解数据分析结果。
七、MapReduce 模型的执行步骤，其核心思想及主要技术有哪些？
MapReduce的执行步骤：
1、Map任务处理
1.1 读取HDFS中的文件。每一行解析成一个。每一个键值对调用一次map函数。1.2 覆盖map()，接收1.1产生的，进行处理，转换为新的输出。 1.3 对1.2输出的进行分区。默认分为一个区。详见《Partitioner》1.4 对不同分区中的数据进行排序（按照k）、分组。分组指的是相同key的value放到一个集合中。排序后： 分组后：1.5 （可选）对分组后的数据进行归约。详见《Combiner》
2、Reduce任务处理
2.1 多个map任务的输出，按照不同的分区，通过网络copy到不同的reduce节点上。（shuffle）详见《shuffle过程分析》
2.2 对多个map的输出进行合并、排序。覆盖reduce函数，接收的是分组后的数据，实现自己的业务逻辑， 处理后，产生新的输出。2.3 对reduce输出的写到HDFS中。MapReduce的核心思想
当启动一个MapReduce任务时，作业会将输入的数据集切分成若干的数据块，由Map端将数据映射成需要的键值对类型，然后对Map的输出进行排序，再把结果输入Reduce端；Reduce端接收Map端传过来的键值对类型的数据，根据不同键分组，对每一组键相同的数据进行处理，得到新的键值对并输出，这就是MapReduce的核心思想。
八、试给出词频计算或密码统计的 MapReduce 计算过程及其实现函
数。
词频计算：
map函数接受的键是文件名，值是文件的内容，map逐个遍历单词，每遇到一个单词w，就产生一个中间键值对，表示单词w又找到了一个；MapReduce将键相同（都是单词w）的键值对传给reduce函数，这样reduce函数接受的键就是单词w，值是一串\"1\"（最基本的实现是这样，但可以优化），个数等于键为w的键值对的个数，然后将这些“1”累加就得到单词w的出现次数。
最后这些单词的出现次数会被写到用户定义的位置，存储在底层的分布式存储系统（GFS或HDFS）
map(key, value):
// key: document name; value: text of document
for each word w in value:
emit(w, 1)
reduce(key, values):
// key: a word; value: an iterator over counts
result = 0
for each count v in values:
result += v
emit(result)
八、指出并行数据库与 MapReduce 各自的优缺点及生态。
MapReduce优点：
1，开发简单：用户不用考虑进程间的通信和套接字编程
2，可扩展性强：当集群资源不能满足计算需求时，可以增加节点的方式达到线性扩展集群的目的。
3，容错性强：对于节点故障导致失败的作业，MapReduce计算框架会自动将作业安排到健康的节点进行，直到任务完成。
MapReduce缺点：
1，执行速度慢：普通的MapReduce作业几分钟完成，数据量大的可能几个小时甚至一天的时间。
2，MapReduce过于低层化：一个简单的查询，需要写Map和reduce函数，复杂且耗费时间，建议使用hive数据库进行处理。
3，不是所有的算法都用MapReduce实现：例如机器学习的模型训练，有赖于状态共享和参数间的依赖，需要维护和更新。
并行数据库优点：
并行数据库系统的目标是高性能和高可用性，通过多个节点并行执行数据库任务，提高整个数据库系统的性能和可用性。最近一些年不断涌现一些提高系统性能的新技术，如索引、压缩、实体化视图、结果缓存、I/O共享等，这些技术都比较成熟且经得起时间的考验。与一些早期的系统如Teradata必须部署在专有硬件上不同，最近开发的系统如Aster、Vertica等可以部署在普通的商业机器上，这些数据库系统可以称得上准云系统。
并行数据库系统缺点：
的主要缺点就是没有较好的弹性，而这种特性对中小型企业和初创企业是有利的。人们在对并行数据库进行设计和优化的时候认为集群中节点的数量是固定的，若需要对集群进行扩展和收缩，则必须为数据转移过程制订周全的计划。这种数据转移的代价是昂贵的，并且会导致系统在某段时间内不可访问，而这种较差的灵活性直接影响到并行数据库的弹性以及现用现付商业模式的实用性。
并行数据库的另一个问题就是系统的容错性较差，过去人们认为节点故障是个特例，并不经常出现，因此系统只提供事务级别的容错功能，如果在查询过程中节点发生故障，那么整个查询都要从头开始重新执行。这种重启任务的策略使得并行数据库难以在拥有数以千个节点的集群上处理较长的查询，因为在这类集群中节点的故障经常发生。
十、阅读三篇分布式数据库或大数据分析的研究热点的相关论文，介
绍各论文的主要内容（能结合自己的研究方向最好，不少于 1000 字）
我看的三篇论文分别是《大数据下基于Spark 的电商实时推荐系统的设计与实现》、《大数据环境下智慧图书馆智能推荐系统设计及其在高职教育中的应用研究》、《基于多源大数据的个性化推荐系统效果研究》。
《大数据下基于Spark 的电商实时推荐系统的设计与实现》该论文主要讲的是基于 Spark 平台的电商实时推荐系统相对于 Hadoop 平台的电商推荐系统具有更高的可靠性和稳定性。因为大数据下基于 Hadoop 平台构建的电商推荐系统存在着计算缓慢、无法根据用户实时行为作出推荐的问题。针对以上问题,设计和实现基于 Spark 平台的电商实时推荐系统。系统首先基于 Spark 平台构建了分布式日志采集模块和分布式日志数据传输模块，用于采集和传输用户隐式行为日志，解决电子商务跨系统数据源收集问题；其次在统一数据源的基础上，采用基于 Spark 的矩阵分解推荐模型进行离线训练，提升离线推荐训练的效率；进而在离线推荐的基础上，提出一种使用 Spark Streaming 实时流技术对电商日志数据做实时过滤，获取用户当前所需商品，并将离线推荐结果与实时推荐结果通过统一介质融合的方案，实现对用户隐式行为进行实时推荐反馈的功能。
《大数据环境下智慧图书馆智能推荐系统设计及其在高职教育中的应用研究》该论文是
在探讨如何创建大数据环境下的智慧图书馆，感知学生阅读与学习需求，使之成为高职教育重要的组成部分的基础上，论文设计了一种能够用以收集、分析、处理和可视化呈现多种来源数据的大数据系统，以及专门适用于高职院校的智慧图书馆智能推荐系统。该系统能够较好地满足高职学生需求，为其搜寻和推荐个性化的内容资源，促进数据驱动决策理念在图书馆服务与高职教育中的应用。
《基于多源大数据的个性化推荐系统效果研究》该论文探究了基于多源大数据的个性
化推荐系统对消费者购物行为的影响。为了建立推荐系统与消费者购物行为之间的因果关系，采用实地实验有效地避免传统研究方法存在的内生性问题，并具有较好的外部有效性。一方面，基于内部数据和外部数据构造解释性变量，探究内部数据特征和外部数据特征与推荐效果之间的关系;另一方面，通过检验消费者特征与内外部数据的推荐效果间的交互效应，进一步分析外部数据和内部数据的推荐效果如何随消费者的特征变化，帮助企业更好地利用多源大数据提升推荐效果。研究结果表明，基于内部数据的推荐系统能够显著提升消费者点击个性化推荐商品的概率，可以降低消费者决策时间，激励消费者浏览更多的商品。外部数据的推荐效果不仅与外部公司网站的用户数量相关，也会受到外部网站与当前网站的关联程度的影响。消费者特征对基于内部数据和外部数据的推荐效果起调节作用，如果消费者是当前网站的老用户，利用该消费者在当前网站的内部数据提供个性化推荐的效果更佳。通过分析基于多源大数据的推荐效果对消费者购物行为的影响，进一步完善个性化推荐领域的理论框架。研究结果对如何利用多源数据构建更加有效的推荐系统具有重要指导价值，并为不同网站之间的数据共享机制提供重要的管理建议。