数据仓库的概念、特点与组成
目录1概念2特点2.1面向主题2.2集成2.3相对稳定2.4反映历史变化3组成3.1数据仓库数据库3.2数据抽取工具3.3元数据3.4访问工具3.5数据集市（DataMart）3.6数据仓库管理3.7信息发布系统1概念数据仓库（DataWarehouse）通常指一个数据库环境，而不是一件产品，它提供用户用于决策支持的当前的和历史数据，这些数据在传统的数据库中通常不方便得到；数据仓库是一个面向主题的（SubjectOriented）、集成的（Integrated）、相对稳定的（Non-Volatile）、反映历史变化（TimeVariant）的数据集合；通常用于辅助决策支持；2特点2.1面向主题操作型数据库中的数据针对事务处理任务，各个业务系统之间彼此分离，而数据仓库中的数据按照一定的主题域进行组织；主题是个抽象概念，指用户使用数据仓库进行决策时所关心的重点领域，如顾客/供应商/产品等；一个主题通常与多个操作型数据库相关；2.2集成操作型数据库通常与某些特定的应用相关，数据库之间相互独立，且往往是异构的；而数据仓库中的数据是在原有分散的数据库数据作抽取、清理的基础上经过系统加工、汇总和整理得到的，因此必须消除源数据中的不一致性，以保证数据仓库内的信息是关于整个企事业单位一致的全局信息；即存放在数据仓库中的数据应使用一致的命名规则、格式、编码结构和相关特性来定义；2.3相对稳定操作型数据库中的数据通常实时更新，数据根据需要及时发生变化；数据仓库中的数据主要用作决策分析，涉及的数据操作主要是查询和定期更新，一旦某个数据加载到数据仓库以后，一般情况下将作为数据档案长期保存，几乎不再做修改和删除操作；即数据仓库中通常有大量的查询操作及少量定期的更新操作；2.4反映历史变化操作型数据库主要关心当前某一时间段内的数据，而数据仓库中的数据通常包含较久远的历史数据；因此数仓中通常包括一个时间维，以便研究趋势和变化；数仓系统通常记录了一个单位从过去某一时期到目前的所有时期的信息，通过这些信息，可以对单位的发展历程和未来趋势作出定量分析和预测；3组成3.1数据仓库数据库数仓数据库是整个数仓环境的核心，是数据信息存放的地方，对数据提供存取和检索支持；相对传统数据库，其突出特点是对海量数据的支持和快速的检索技术；3.2数据抽取工具数据抽取工具把数据从各种各样的存储环境中提取出来，进行必要的转化、整理，再存放到数仓内；对各种不同数据存储方式的访问能力是数据抽取工具的关键，可以运用高级语言编写的程序、操作系统脚本、批命令脚本或SQL脚本等方式访问不同的数据环境；数据转换通常包括如下内容：删除对决策分析没有意义的数据；转换到统一的数据名称和定义；计算统计和衍生数据；填补缺失数据；统一不同的数据定义方式；3.3元数据元数据是描述数据仓库内数据的结构和建立方法的数据；元数据为访问数据仓库提供了一个信息目录，这个目录全面描述了数据仓库中有什么数据、数据是怎么得到的、怎么访问这些数据；元数据是数仓运行和维护的中心内容，数仓系统对数据的存取和更新都需要元数据信息；根据元数据用途的不同可将元数据分为技术元数据和业务元数据两类；技术元数据是数仓的设计和管理人员在开发和管理数仓时使用的元数据，包括数据源信息、数据转换的描述、数仓内对象和数据结构的定义、数据清理和数据更新时用的规则、源数据到目的数据的映射表，以及用户访问权限、数据备份历史记录、数据导入历史记录和信息发布历史记录等；业务元数据是从单位业务的角度描述数仓中的元数据，例如业务主题的描述，即业务主题包含的数据、查询及报表等信息；3.4访问工具访问工具是为用户访问数仓提供的手段，如数据查询和报表工具、应用开发工具、数据挖掘工具和数据分析工具等。
3.5数据集市（DataMart）数据集市是为了特定的应用目的，从数仓中独立出来的一部分数据，也称为部门数据或主题数据；在数仓的实施过程中往往可以从一个部门的数据集市着手，再逐渐用几个数据集市组成一个完整的数仓；注意：在实施不同的数据集市时，相同含义字段的定义一定要相容，以免未来实施数仓时出现问题；3.6数据仓库管理数仓管理包括安全与权限的管理、数据更新的跟踪、数据质量的检查、元数据的管理与更新、数仓使用状态的检测与审计、数据复制与删除、数据分割与分发、数据备份与恢复、数据存储管理等。
3.7信息发布系统信息发布系统用于把数仓中的数据或其他相关的数据发送给不同的地点或用户；基于Web的信息发布系统是当前流行的多用户访问的最有效方法；人工智能搜索策略：A*算法
人工智能搜索策略：A*算法目录人工智能搜索策略：A*算法A算法1.全局择优搜索2.局部择优搜索A*算法1.A*算法的可纳性2.A*算法的最优性3.h(n)的单调限制A*算法应用举例对A*算法的一点思考熟练掌握A*算法的性质A*算法的性质A*算法的最优性h(n)的单调限制A算法在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法又称为启发式搜索算法。对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。
1.全局择优搜索在全局择优搜索中，每当需要扩展节点时，总是从Open表的所有节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可能描述如下：
（1）把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；（2）如果Open表为空，则问题无解，失败退出；（3）把Open表的第一个节点取出放入Closed表，并记该节点为n；（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；（5）若节点n不可扩展，则转到第(2)步；（6）扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni)(i=1,2,……)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；（8）转第(2)步。
由于上述算法的第(7)步要对Open表中的全部节点按其估价函数值从小到大重新进行排序，这样在算法第(3)步取出的节点就一定是Open表的所有节点中估价函数值最小的一个节点。因此，它是一种全局择优的搜索方式。对上述算法进一步分析还可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的广度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为广度优先搜索。可见，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。
例1：八数码难题。设问题的初始状态S0和目标状态Sg如图所示，估价函数与请用全局择优搜索解决该题。
解：这个问题的全局择优搜索树如图1所示。在图1中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数的计算为f(S2)=d(S2)+W(S2)=2+2=4从图1还可以看出，该问题的解为S0→S1→S2→S3→Sg
图1八数码难题的全局择优搜索树
2.局部择优搜索在局部择优搜索中，每当需要扩展节点时，总是从刚生成的子节点中选择一个估价函数值最小的节点进行扩展。其搜索过程可描述如下：
(1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；(2)如果Open表为空，则问题无解，失败退出；(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；(5)若节点n不可扩展，则转到第(2)步；(6)扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni)(i=1,2,……)，并按估价值从小到大的顺序依次放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。
由于这一算法的第六步仅仅是把刚生成的子节点按其估价函数值从小到大放入Open表中，这样在算法第(3)步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。对这一算法进一步分析也可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的深度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。
A*算法上一节讨论的启发式搜索算法，都没有对估价函数f(n)做任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。假设f*(n)为从初始节点S0出发，约束经过节点n到达目标节点的最小代价值。估价函数f(n)则是f*(n)的估计值。显然，f*(n)应由以下两部分所组成：
一部分是从初始节点S0到节点n的最小代价，记为g*(n)；另一部分是从节点n到目标节点的最小代价，记为h*(n)，当问题有多个目标节点时，应选取其中代价最小的一个。因此有f*(n)=g*(n)+h*(n)把估价函数f(n)与f*(n)相比
g(n)是对g*(n)的一个估计h(n)是对h*(n)的一个估计。在这两个估计中，尽管g(n)的值容易计算，但它不一定就是从初始节点S0到节点n的真正最小代价，很有可能从初始节点S0到节点n的真正最小代价还没有找到，故有有了g*(n)和h*(n)的定义，如果我们对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制：•g(n)是对g*(n)的估计，且g(n)>0；•h(n)是对h*(n)的下界，即对任意节点n均有则称得到的算法为A*算法。
1.A*算法的可纳性一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。A*算法是可采纳的。下面我们分三步来证明这一结论。
定理1对有限图，如果从初始节点S0到目标节点Sg有路径存在，则算法A*一定成功结束。定理1证明：首先证明算法必定会结束。由于搜索图为有限图，如果算法能找到解，则会成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束。然后证明算法一定会成功结束。由于至少存在一条由初始节点到目标节点的路径，设此路径S0=n0，n1，…，nk=Sg算法开始时，节点n0在Open表中，而且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中。因此，算法必定会成功结束。
引理0在最佳路径上的所有节点n的f值都应相等，即f(n)=f*(S0)
引理1对无限图，如果从初始节点S0到目标节点Sg有路径存在，且A*算法不终止的话，则从Open表中选出的节点必将具有任意大的f值。引理1证明：设d*(n)是A生成的从初始节点S0到节点n的最短路径长度，由于搜索图中每条边的代价都是一个正数，令这些正数中最小的一个数是e,则有因为是最佳路径的代价，故有又因为h(n)>=0,故有如果A算法不终止的话，从Open表中选出的节点必将具有任意大的d*(n)值，因此，也将具有任意大的f值。引理2在A*算法终止前的任何时刻，Open表中总存在节点n’，它是从初始节点S0到目标节点的最佳路径上的一个节点，且满足。引理2证明：设从初始节点S0到目标节点t的最佳路径序列为S0=n0，n1，…，nk=Sg算法开始时，节点S0在Open表中，当节点S0离开Open进入Closed表时，节点n1进入Open表。因此，A没有结束以前，在Open表中必存在最佳路径上的节点。设这些节点排在最前面的节点为n’,则有由于n’在最佳路径上，故有从而又由于A算法满足故有因为在最佳路径上的所有节点的f*值都应相等，因此有
定理2对无限图，若从初始节点S0到目标节点t有路径存在，则A*算法必然会结束。证明：（反证法）假设A算法不结束，又引理5.1知Open表中的节点有任意大的f值，这与引理2的结论相矛盾，因此，A算法只能成功结束。
推论1Open表中任一具有的节点n，最终都被A*算法选作为扩展节点。
定理3A算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A算法必能结束在最佳路径上。证明：证明过程分以下两步进行：先证明A*算法一定能够终止在某个目标节点上。由定理1和定理2可知，无论是对有限图还是无限图，A算法都能够找到某个目标节点而结束。**再证明A算法只能终止在最佳路径上（反证法）。**假设A算法未能终止在最佳路径上，而是终止在某个目标节点t处，则有但由引理2可知，在A算法结束前，必有最佳路径上的一个节点n’在Open表中，且有这时，A算法一定会选择n’来扩展，而不可能选择t，从而也不会去测试目标节点t，这就与假设A算法终止在目标节点t相矛盾。因此，A*算法只能终止在最佳路径上。
在A*算法中，对任何被扩展的任一节点n，都有证明：令n是由A*选作扩展的任一节点，因此n不会是目标节点，且搜索没有结束。由引理2可知，在Open表中有满足的节点n’。若n=n’，则有否则，算法既然选择n扩展，那就必有，所以有
2.A*算法的最优性A算法的搜索效率很大程度上取决于估价函数h(n)。一般说来，在满足**h(n)≤h(n)**的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A算法搜索时扩展的节点就越少，搜索的效率就越高?A算法的这一特性也称为信息性。下面通过一个定理来描述这一特性。
定理4设有两个A算法A1和A2*，它们有A1*：f1(n)=g1(n)+h1(n)A2*：f2(n)=g2(n)+h2(n)如果A2比A1有更多的启发性信息，即对所有非目标节点均有h2(n)>h1(n)则在搜索过程中，被A2扩展的节点也必然被A1扩展，即A1扩展的节点不会比A2扩展的节点少，亦即A2扩展的节点集是A1扩展的节点集的子集。证明：（用数学归纳法）(1)对深度d(n)=0的节点，即n为初始节点S0，如果n为目标节点，则A1和A2都不扩展n；如果n不是目标节点，则A1和A2都要扩展n。(2)假设对A2搜索树中d(n)=k的任意节点n，结论成立，即A1也扩展了这些节点。(3)证明A2搜索树中d(n)=k+1的任意节点n，也要由A1扩展（用反证法）。假设A2搜索树上有一个满足d(n)=k+1的节点n,A2扩展了该节点，但A1没有扩展它。根据第(2)条的假设，知道A1扩展了节点n的父节点。因此，n必定在A1的Open表中。既然节点n没有被A1扩展，则有f1(n)≥f*(S0)即g1(n)+h1(n)≥f*(S0)但由于d=k时，A2扩展的节点A1也一定扩展，故有g1(n)≤g2(n)因此有-g1(n)≥-g2(n)因此有h1(n)≥f*(S0)-g1(n)≥f*(S0)-g2(n)h1(n)≥f*(S0)-g2(n)另一方面，由于A2扩展了n，因此有f2(n)≤f(S0)即g2(n)+h2(n)≤f*(S0)亦即h2(n)≤f*(S0)-g2(n)f*(S0)-g2(n)≥h2(n)所以有h1(n)≥h2(n)这与我们最初假设的h1(n)h1(n)则在搜索过程中，被A2扩展的节点也必然被A1扩展，即A1扩展的节点不会比A2扩展的节点少，亦即A2扩展的节点集是A1扩展的节点集的子集。
h(n)的单调限制•如果启发函数满足以下两个条件：•（1）h(Sg)=0；•（2）对任意节点ni及其任意子节点nj,都有其中c(ni,nj)是节点ni到其子节点nj的边代价，则称h(n)满足单调限制•如果h满足单调条件，则当A*算法扩展节点n时，该节点就找到了通往它的最佳路径，即