数据仓库查询技术在股票数据分析中的应用研究.doc

TP311分类号：密级：公开2007020689论文编号：贵州大学2010届硕士研究生学位论文数据仓库查询技术在股票数据分析中的应用研究学科专业：计算机应用技术研究方向：数据库技术与软件工程导师：王翰虎研究生：罗曼中国贵州贵阳2010年5月目录目录.I摘要Abstract.II.1第一章概述1.1.1研究背景和意义1.2.2国内外研究现状1.3.2本文主要创新点1.4.3本文的组织结构.4第二章股票数据分析系统2.1.4股票数据分析系统结构和功能2.2.7股票数据分析系统中的查询处理2.3.7小结.8第三章数据仓库查询技术3.1.8数据仓库数据仓库的体系结构数据仓库设计3.2.9数据仓库查询技术3.2.1OLAP.10查询操作3.2.2OLAP.11基于物化视图的查询3.2.3Ad-hocOLAP.13查询3.3.16数据仓库查询技术的分析与总结3.4.17小结.18第四章数据仓库查询技术在股票数据分析中的应用4.1.18股票交易数据仓库8股票交易数据仓库的特性9股票交易数据仓库的结构4.2.20股票交易数据查询处理0股票交易数据查询的特性1股票交易数据查询的结构4.3.23股票交易数据属性排序算法4股票交易数据属性排序算法的基本思路7股票交易数据属性排序算法的描述和实现4.4.29实验分析9实验数据说明9排序算法实验分析4.4.3OLAP.32查询算法实验分析4.5.33小结.34第五章结束语.35致谢.36参考文献.39附录摘要摘要随着数据库学科的迅猛发展，数据仓库技术已日趋成熟，它也被广泛地应用到各行各业中，特别对于证券行业的股票市场，它包含了海量的股票交易历史数据，更需要运用数据仓库技术对数据进行有效的管理。毋庸置疑，数据仓库除了有效地管理和维护数据以外，还需要支持即席的、复杂的查询，而这些查询需要访问大量的记录，进行复杂的多表连接与聚集操作，在最坏情况下，用户在忍受查询响应时间过长的同时，还要容忍查询有效性的低下，这在决策支持应用中是不能接受的，因此，如何提高海量数据上的查询效率已成为一个热点问题，对数据仓库查询技术方面的研究也就具有重大的意义。本文深入研究了数据仓库查询技术，并提出了一种适用于股票数据分析的查询方法，即通过增加一个查询预处理层来提高查询效率。该查询预处理层主要用M-Join来对股票交易数据属性进行排序，使其与基于星型模型的多表连接算法MuSA和聚集算法相结合，以此提高查询的有效性。在股票交易数据属性排序CA算法中，我们使用模糊聚类算法算法对数值型数据进行离散化，得到若干个优化的类，然后用关联规则挖掘出有意义的规则，最后根据其置信度对属性进行排序。实验结果表明，该方法在股票数据分析中有较好的效果，它不仅能够提高查询的有效性，而且提高了预测的准确度，为后续人员的分析带来了方便，具有较好的应用前景。关键词：数据仓库，数据仓库查询技术，股票数据分析，多表连接，模糊聚类，关联规则；I摘要AbstractTakentheadvantageoftherapidgrowingindatabasescience,thedatawarehousetechnologyislargelydevelopedandiswidelyusedinallthefields.Oneofthemosttypicalareasisthestokemarketinthesecuritiesindustry,whichincludesginormousamountofstockexchangehistoriesand,asaresult,needsveryadvancedtechniquesinefficientlymanipulatingthehugedatabase.Undoubtedly,adatawarehouseshouldbeabletomaintainandefficientlymanageinformation.Thedatabaseshouldalsobeabletorespondtocomplicatedadhocqueriesthatrequireaccesstoalargenumberofrecordsneverthelesstoexecutecomplicatedmulti-tablejoiningandaggregatequery.Intheworstcase,theusershavetostandtheextendedrespondingtimeandthelowaccuracyoftheoutcome,whichareunacceptableinthebusinessfield.Asaresult,increasingthequeryingefficiencyonmassivedataisahotandveryimportanttopicofdatabaseresearch.ThisthesiswillbetalkingabouttheDataWarehouseQueryTechnologyindepth.Theauthorwillpresentanewlydevelopedtechniqueespeciallydesignedforanalyzingdatafromstockmarket.Comparingtothetraditionalmethods,thenewtechniqueincludesaquerypre-processinglayertoincreasethequeryingefficiency.Thequerypre-processinglayerwillrearrangethestockexchangeattributetomakethepre-processinglayercompatiblewiththeM-JoinandMuSAalgorism.Tosortthestockexchangeattribute,theauthorintroducedtheCAalgorithmthatbelongedtothefuzzyclustermethodtodiscretizethenumericaldata.Italsocouldgetoneorseveraloptimalclusters.Thenweusethemethodofassociationrulesdataminingfindtheinterestingrules.Finally,wesorttheattributeaccordingtotheconfidenceoftherules.Theexperimentdatainthisresearchindicatesthatthisquerypre-processinglayerwillgreatlyincreasetheefficiencyandtheaccuracyofthequeries.Thistechniquewillbeapowerfultoolfortheusersandwouldpossiblybeusedinvariousareas.Keywords:Datawarehouse,Datawarehousequerytechnology,Stockdataanalysis,Multi-tablejoin,Fuzzycluster,AssociationrulesII贵州大学硕士学位论文第一章概述1.1研究背景和意义随着计算机的广泛应用，数据仓库技术在近几年得到了迅速发展，它已成功地应用到金融服务、零售、电信、保险等众多行业。从数据仓库本身的定义来看，它是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合，用于支1持管理决策，可见，其中包含了大量的历史数据，并且这些数据会随着时间的推移而增多，如何从这些庞大的数据中提取对决策分析有用的信息，是决策人员所面临的一个难题。换句话说，用户媸泵娑允菘猓袢氖荩饩托枰莶挚饽芄恢旨聪摹丛拥牟檠莶挚獾募聪檠枰梦蚀罅康募锹迹缓蠼懈丛拥亩啾砹佑刖奂僮鳎谧罨登榭鱿拢没谌淌艹奔涞牟檠煊院螅挂萑痰拖碌牟檠行裕庠诰霾咧钟弥惺遣荒芙邮艿摹裕绾胃行刈橹娲渴荩岣吆渴萆系牟檠食晌醚芯苛煊虻囊桓鋈鹊阄侍猓允莶挚獠檠际醴矫娴难芯恳簿途哂兄卮蟮囊庖濉LAP(On-LineAnalyticalProcessing)在数据仓库查询技术中，查询有着不可OLAP或缺的地位，它是面向海量数据的复杂多维查询。从数据仓库的综合数据出发，使用多维分析方法，从多个角度对数据进行分析与比较，使得用户以自然OLAP的方式获得丰富的信息。此外，具有强大的查询能力、数据对比和报表功能，用它可以进行探测式数据分析，从而使得它在数据仓库系统中发挥了关键性1OLAPad-hocOLAP的作用。查询根据其查询处理模式的不同分为两大类：查OLAPOLAP询和基于物化视图的查询。基于物化视图的查询主要从优化数据仓库查询性能的角度出发，在用户真正执行查询前，对存储的数据进行预处理并保存结果，待用户执行查询时，直接从物化视图中读取数据，而不需进行复杂的Ad-hocOLAP查询操作，大大提高了查询响应时间。查询主要从用户的角度出发，使用户能够随时面对数据仓库获取想要的数据，比如对数据的钻取、切片和切块OLAP操作可以满足用户多角度查看数据的需求。但是，无论是基于物化视图的Ad-hocOLAP查询，还是查询，它们有个共性，都把注意力集中在对本身算法的提高与改进上，然而对于一些特殊的应用，它们不能满足决策人员的需要，因此，可以考虑在对数据执行即席查询或者物化视图前，加入一个查询预处理层，OLAP用以在查询中对属性做出分析，以此来优化聚集操作，使物化视图的选择更为有效。比如在股票数据分析这一特殊应用中，股市每天都会产生大量的交易数据，若采用传统的数据库技术来对它们进行管理和维护，效率是很低下的，且不能满足用户的决策需求，因此我们可以用数据仓库技术来存储和管理庞大的股票历史OLAP数据，进而通过查询对各种股票数据属性进行灵活方便的分析，使上层用户从不同侧面、不同角度获取有用的信息。但是，对于股票数据分析系统来说，由于股票交易数据集市中事实表的属性繁多，仅从各个角度去观测这些数据远远不够，杂乱无章的属性，不仅为挖掘人员的分析带来不便，而且也不能更好地服务于决策用户，因此，我们提出了适用于本应用的查询方法，即增加一个查询预处理层，用于分析事实表数据中的属性。它可针对股票分析挖掘者以及决策用户1贵州大学硕士学位论文最关心的问题，即股票的涨跌，让属性根据其对涨跌的影响程度进行排序，有利于挖掘人员后续的分析预测，提高了查询效率及预测的准确度。排序的结果将呈现于事实表中，此后挖掘人员或决策人员可从各个角度去观测这些数据，使用户得到真正关心的查询结果。1.2国内外研究现状数据仓库查询技术的研究主要集中在提高查询性能上，比如对物化视图、索引、数据立方体、并行处理、数据压缩等技术的研究。其中，物化视图是利用冗余的数据来提高查询性能，即将经常使用的查询先进行计算后就保存结果，当真正处理查询时，直接查询该实视图，而不需要对多个基表进行连接或聚集操作；使用索引技术查找时，无需对整个表进行扫描就可以在其中找到符合查询条件的记录，由于数据仓库中的数据很少更新，使用合适的索引已成为一个提高查询性2能的重要方法；数据立方体是实现多维数据查询与分析的一种重要手段，对于它的研究主要集中在数据立方体的计算上；使用并行化策略来处理数据仓库的大量数据，是减少查询响应时间较为常用的手段；数据压缩技术是为了减少查询扫3描的数据，以此提高查询速度。目前，在国外，各个研究机构已经开展了大量的研究工作，并取得了一定的成果，例如斯坦福大学的WHIPS项目、IBMAlmaden研究中心和微软的Quest项目、Bell实验室的AQUA项目以及威斯康辛大学和AT&T的研究等。其中，WHIPS的研究目标是要生成一个高效的、自动集成异构数据源的算法和工具；Quest的研究重点是多维数据库的建模与组织；AQUA对于抽样在连接操作和聚集操作中存在的问题进行了深入了研究；威斯康辛大学和AT&T则侧重于实视图、OLAP数据组织、数据立方体计算等的研究。在系统开发方面，各大数据库厂商也对数据仓库的研制给予了相当的关注，如IBM、Oracle和Sybase都分别推出了各自的数据仓库整体解决方案。在国内，这方面的研究正在起步，一些学校和研究所也对数据仓库技术进行了研究，比如中国人民大学、南京大学、哈尔滨工业大学等，他们的研究则主要集中在数据仓库的体系结构、数据仓库的建模、数据仓库中数据的组织与存储、数据立方体的计算等方面。在数据仓库产品方面，这些应用产品一般都整合了即席查询与分析功能，比OracleDiscovererOracleBIAnswers如、等，它们能够很好地满足用户查询和分OracleDiscovererWeb析数据的需求。提供了即席查询、报表、复杂分析和发Discoverer布等功能，使得用户可以快速创建、修改和执行即席查询与报表。通过，用户可以从多个图表和布局选项中选择，以快速创建他们的查询结果的直观表示形式。用户还可以在数据或图形上执行查询，以查看和分析基础数据，从而识别4BIAnswers业务发展趋势和异常。以图表、透视表以及报告的方式，同样使查询结果可视化，它可通过字段的计算和下钻来加强查询结果。1.3本文主要创新点本文的创新点如下：1建立了以股票行情数据为主题的数据集市。该数据集市主要包括时间、2贵州大学硕士学位论文板块和股票类型等三个维，以及以股票行情数据为内容的事实表。2提出了一种适用于股票数据分析的查询方法，即增加一个查询预处理层，以此来提高预测的准确度及查询的有效性。该查询预处理层与基于星型模型的多M-JoinMuSAOLAP表连接算法和聚集算法相结合，形成一个完整的查询操作。3提出了股票交易数据属性排序算法，用它实现查询预处理。该算法中，主要使用模糊聚类算法对数值型数据进行离散化，然后用关联规则挖掘出有意义的规则，再根据其置信度对属性进行排序。实验结果表明，该方法在股票数据分析中具有较好的效果。1.4本文的组织结构本文共分为五个部分，组织结构如下：第一章为“概述”。本章首先介绍了数据仓库查询技术的研究背景和意义，然后介绍国内外相关的研究状况，最后说明了本文研究的主要内容及其创新点。第二章为“股票数据分析系统”。本章主要介绍了股票数据分析系统的结构和功能，以及查询处理在系统中的重要作用，为第四章的叙述做好了准备工作。第三章为“数据仓库查询技术”。本章首先介绍了数据仓库的相关概念，然OLAP后从基于物化视图和即席查询两方面，深入研究了查询方法，最后通过分析这些查询方法，提出增加一个查询预处理层来提高查询效率，引出了创新点，为下一章做出了铺垫。第四章为“数据仓库查询技术在股票数据分析中的应用”。本章详细介绍了股票交易数据仓库的特性及结构、股票交易数据查询处理的特性结构及其在股票数据分析中的重要作用、以及股票数据属性排序算法的提出与实现，并用实验表明了算法的有效性。这是本文研究的主要内容及其创新点，是核心部分。第五章为“结束语”，本章对所作的工作及研究成果进行了总结，并提出了下一步的研究方向。3贵州大学硕士学位论文第二章股票数据分析系统股票数据分析系统是一款适用分析国内证券市场的系统，它提出股票分析依据的是数据面，而非常规的基本面或技术面或基本面加技术面。这主要是考虑到国内股票数据挖掘的研究正处于起步阶段，缺乏实质性的研究成果，加上大多数的分析软件都是依据前人的技术分析和专家的经验，其中又包含了大量且复杂的技术参数和曲线。这些复杂的技术参数所蕴含的预测结果不直观，有时甚至是相互矛盾的，对于非专业投资者使用起来过于复杂，准确度不高。该系统在数据仓库的基础上，从数据的角度出发，脱离传统的分析手段，采用数据挖掘技术对股票历史数据进行智能分析处理，能有效地预测个股变化趋势，并且能为投资机构以及个人用户提供操作简单、功能强大的决策支持。本章将通过系统的总体架构及各层功能来了解股票数据分析系统，并且指出查询层的位置和作用。2.1股票数据分析系统结构和功能股票数据分析系统采用数据仓库技术来管理股市中的大量数据，使之形成一个综合的、面向分析的环境，最终建立面向高层的决策平台，系统还采用数据挖掘技术对股市的未来走势进行预测，从而对现有股票分析方法的进行有力补充，为投资机构以及个人用户提供操作简单、功能强大的决策支持。2-1系统总体结构如图所示，总体分为：数据获取层，数据存储与管理层（包括数据仓库，数据集市，元数据管理等），数据查询层，数据挖掘层，数据展现层等共五个层次。4贵州大学硕士学位论文选择开源数的图形展据示控件展交互客户端现查询报表指标曲线图服务数服据股票价格趋势分析（神经网络）务挖掘输出OLAP查询操作数物化视图据查OLAP服务器即席查询询数集市建模工具据股价趋势分析数据集市.存集市管理工具股票数据仓库储技术指标数据集市元数据管理与管理数据抽取，转换，装载，刷新数据数据获取方法网络公布的股票数据关系型股票数据库获数据获取取数据源1.清华大学金融数据库2.财富网2-1图股票数据分析系统原型结构图在系统中，位于下方的层次是上方应用层的基础，每个层次实现的功能如下：1数据获取层数据获取层包括对数据源的选取以及获取方法。系统的数据源来自清华大学金融数据库、财富网以及其他网站公布的数据，以此获得各个年份内深市与沪市的股票行情数据。获取层包括页面数据抽取和数据导入功能。页面数据抽取是对财富网的数据页面进行解析，从而获取公布的股票行情数据；数据导入功能是将清华大学金融EXCEL数据库下载得来的股票行情数据（格式），分解后导入相应的本地股票行2情数据库的各个表中。目前，获取程序针对选定的个数据源有效，系统可根据需要进一步扩展，使之能从若干股票数据源读取每日公布的股票数据，解析获取的数据包，最终转换成挖掘系统能够理解的数据格式。2数据存储与管理层该层包括对基本数据的存储以及数据抽取、转换、装载等过程。股票的行情数据存放再本地的关系型数据库中，数据库的数据存储表包括：个股资金流向数5贵州大学硕士学位论文RISC据、日交易行情、行业分类、板块分类、大盘日行情、股票基本数据、交2-2易日列表等七个表，表之间的关系如下图所示。2-2图股票数据库表间关系ETL过程负责按照数据集市的要求，从股票行情数据库中抽取对应的数据，按照指定方式进行转化，最后装入数据集市中。该过程对挖掘模块起到了数据预SQL处理的作用。整个过程通过自定义函数或存储过程实现。对数据仓库的管理包括建立统一规范的数据存储结构、划分股票数据存储粒度级别（细节级和按照时间的轻度综合级）、设计股票数据高效的物理分区、管理元数据。数据集市的迭代建设是为了满足特定的部门、用户群或业务线的分析需求而构建的。首先确定最紧迫或者优先级最高的主题域，根据主题域建立股票数据的多维存储模型，确定集市的数据粒度，最后从数据仓库中抽取、汇总数据，并将结果集装载到相应的数据集市中。数据集市实际上是股票数据的冗余存储，但它却能极大地降低用户进行多维分析和即席查询的响应时间。3数据查询层该层采用联机分析查询机制。接口层上方的数据挖掘、分析层可通过联机分析来查询、获取所需的数据。它是介于数据仓库与数据挖掘中的一层，不仅提供了直接的、基本的信息访问功能，而且实现了各部门信息的快速共享，为下一层的挖掘起到很好的过渡作用。4数据挖掘层该层根据个股近期的股票价格变化趋势进行预测。它从查询层中获得对应的数据，采用相应的数据挖掘算法对股票数据进行训练、建模，然后形成数据分类器。分类器在获取用户分析请求后，对指定的个股价格变换趋势进行预测，最终将分析结果反馈给表现层。5数据展现层将数据查询与数据挖掘层所产生的结果集转换成用户易于理解的形式，包括B/SEXCEL站点页面、表格、电子报表等。6贵州大学硕士学位论文2.2股票数据分析系统中的查询处理在股票数据分析系统中，采用了数据仓库技术来管理数据，利用了数据挖掘技术对大量股票的历史数据进行分析，以此实现股票发展趋势的预测，查询处理层则起到了承上启下的作用，是数据传输的枢纽，也是数据挖掘层的预处理过程。由于系统采用了数据仓库技术来管理数据，它必然包含了大量的股票历史行情数据，并且这些数据还会随时间的推移而增多，而在此之上建立的支持即席的、复杂的查询需要访问大量记录，进行复杂的多表连接与聚集操作，在最坏情况下，使得用户在忍受查询响应时间过长、系统的性能变坏的同时，还要容忍查询有效性的低下，这在决策支持应用中是不能接受的。除此之外，股票数据中繁多的属性为挖掘人员的分析带来了不便，可以考虑增加一个查询预处理层，让属性根据其对股票的涨跌影响程度进行排序，以此提高挖掘人员的查询效率，有利于挖掘人员后续的分析预测。排序的结果将呈现给本系统中以“股票行情数据”为主题的数据集市的挖掘人员，或者直接呈现给用户。所以，如何更有效地组织、存储海量股票数据，提高海量数据上的查询效率在系统中显得尤为重要，换句话说，如何建立以“股票行情数据”为主题的数据仓库的数据结构，有效地为挖掘人员提高查询效率，是该系统中的重点问题，它在系统中的重要性也是不言而喻的。2.3小结本章从股票数据分析系统的总体架构和各层功能入手，对股票数据分析系统进行了较为全面的介绍。股票数据分析系统总体架构重点介绍了系统的体系结构；股票数据分析系统功能详细介绍了各层的特点及功能；股票数据分析系统中的查询处理强调了该层在整个系统中的重要作用，具体内容将在本文的第四章有相当篇幅涉及。以上的内容为该课题的研究建立了一个背景，为数据仓库查询技术在股票数据分析中的应用做好了铺垫。7贵州大学硕士学位论文第三章数据仓库查询技术3.1数据仓库1991年，被称为数据仓库之父的美国人WilliamHInmon，在BuildingtheDataWarehouse一书中，正式提出了数据仓库的定义，此概念继而被人们广泛接受。他提出“数据仓库(DataWarehouse)是一个面向主题的、集成的、相对稳1定的、随时间变化的，用来支持管理者决策的数据集合”。与传统数据库的区别就在于它所定义的特性：面向主题性、集成性、稳定性和时变性。传统的数据库是为捕获数据而设计，而数据仓库的设计是为了分析数据。3.1.1数据仓库的体系结构数据仓库的结构如图3-1所示：查询数据报表OLAP分析数据挖掘数据访问层服务数据集市数据存储层数据仓库数据集市抽取、清理、转换、装载数据获取层数据源图3-1数据仓库的结构1数据获取层：包括了数据源和对数据源的抽取、清理、转换和装载，是数据仓库系统的基础，是整个系统的数据源泉。数据源包含了企业内部信息和外部信息。2数据存储层：包括了数据存储组织、数据维护、数据分发等，是整个数据仓库系统的核心。数据仓库的组织管理方式决定了它有别于传统数据库，同时也决定了其对外部数据的表现形式。8贵州大学硕士学位论文3OLAP数据访问层：包括各种查询工具、报表工具、服务器、数据分析工具、数据挖掘工具以及各种基于数据仓库或数据集市的应用开发工具。其中OLAP对分析需要的数据进行有效集成，按多维模型进行组织，以便多角度、多层次的分析，继而发现趋势。在数据仓库的体系结构中，先从外部数据源获取数据，经过数据抽取、清理、转换后装载到数据仓库中，然后由数据仓库管理数据，包括数据存储组织、数据维护、数据分发等，最后通过查询检索、多维分析和数据挖掘等工具实现提取信息、分析数据和挖掘数据，以统一的、集成的和丰富的信息来支持企业决策。数据获取部分确定了数据抽取的规则和方法，中间的数据存储和管理部分负责数据仓库的管理，查询分析工具部分用来支持企业决策。3.1.2数据仓库设计数据仓库的设计，是一个不断增长与完善的过程，它采取螺旋式的开发方法，一般来说数据仓库的构建有以下步骤：1数据仓库规划分析阶段，在该阶段，首先分析数据仓库的应用环境，调查数据仓库的开发需求，完成数据仓库的开发规划，确定了主题以及主题关系后，建立实体关系图，然后进行数据模型分析，建立包括星型模型、雪花模型、元数据模型以及数据源分析的主题域数据模型，并根据主题域数据模型开发数据仓库的逻辑模型。2数据仓库设计实施阶段，该阶段按照数据仓库的逻辑模型设计数据仓库的体系结构，设计数据仓库的物理数据库，用物理数据库元数据填充面向最终用户的元数据库，对数据仓库中每个目标字段确认其在业务系统或外部数据源中的数据来源，对数据进行抽取、清理、转换后，将数据装载到数据仓库中。3数据仓库的使用维护阶段，该阶段将数据仓库投入实际应用，在应用中改进和维护数据仓库，并对数据仓库进行效益评价，为下一个循环提供依据。可以看到，数据仓库的开发方法与传统的数据库开发方法有着不同的过程。传统的数据库开发以需求为驱动，要建立一个数据库，必须先理解用户需求，而DSS从数据仓库的应用角度来看，分析员一般是企业的中上层管理人员，他们对决策分析的需求不能预先做出规范的说明，只能给设计人员一个抽象的描述，所以数据仓库的开发以数据为驱动，先集成数据，对数据进行清理、转换，然后针对数据进行分析处理。因此，传统的数据库开发方法是以需求为驱动的，而数据仓库的开发是以数据为驱动的。3.2数据仓库查询技术由3.1章节的介绍可知，数据仓库是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合，用于支持管理决策。可见，数据仓库中包含了大量的历史数据，并且这些数据会随着时间的推移而增多，同时，数据仓库还要支持即席的、复杂的查询，而这些查询需要访问大量记录，进行复杂的多表连接与聚集操作，在最坏情况下，使得用户在忍受查询响应时间过长、系统的性能变坏的同时，还要容忍查询有效性的低下，这在决策支持应用中是不能接受的。所以，如何更有效地组织、存储海量数据，提高海量数据上的查询效率成为该研究领域的9贵州大学硕士学位论文一个热点问题，对数据仓库查询技术方面的研究也就有着重大意义。OLAP(On-LineAnalyticalProcessing)在数据仓库查询技术中，查询有着不可5OLAP或缺的地位，它是面向海量数据的复杂多维查询。从数据仓库的综合数据出发，使用多维分析方法，从多个角度对数据进行分析与比较，使得用户以自OLAP然的方式获得丰富的信息。此外，具有强大的查询能力、数据对比和报表功能，所以它可以进行探测式数据分析，也使得它在数据仓库系统中发挥了关键1OLAPad-hocOLAP性的作用。查询根据其查询处理模式的不同分为两大类：OLAPOLAPOLAP查询和基于物化视图的查询。本节将围绕查询，分别对查ad-hocOLAPOLAP询操作、查询和基于物化视图的查询进行详细阐述。3.2.1OLAP查询操作OLAP在星型结构或雪花型结构的数据仓库中，查询包括了大量的多表连接OLAP和聚集操作，而查询的主要特点是数据量大、计算量大，想要较快地响OLAP应查询，提高查询处理的速度，对这些操作的研究是数据仓库查询领域OLAP的关键。下面就这两种查询操作分别进行说明。1多表连接操作。ABC在传统的关系数据库中，对多表连接的处理，如，都是先选择其中的两个表进行连接运算，比如先计算AB或者BC，然后再将连接的结果和C或A进行连接。与之对应的查询优化则是选择表两两做连接的次序和基于查询代价选择连接的方法(如嵌套循环、基于Hash的连接等)。在存有大量数据的数据仓库中，数据模型为星型结构或雪花型结构，这就会经常涉及多个表的连接操作，若采用传统数据库中多表连接的方法，效率就会变得低下。比如一个星型结构由1个事实表和3个维表组成，并且事实表中的记录数远大于维表中的记录数，对于这样的结构，有极大可能在应用中出现需要将事实表3和个维表做连接的情况。若采用传统数据库中多表连接的方法，可以选择表两两做连接的次序，或是先将事实表和维表连接，或是先将两个维表连接。如果先将事实表和维表做连接，连接的结果记录数和事实表的记录数相等，由于事实表I/O的记录数很大，造成需要暂存的中间结果集很大，从而带来巨大的磁盘开销；如果先将两个维表做连接，因为维表之间没有连接字段，连接等于笛卡尔积运算，I/O中间结果集也将越来越大，这同样会带来巨大的磁盘开销。此时，查询性能I/O的瓶颈主要是查询处理时巨大的代价。7M-Join针对这个问题，有人提出了基于星型模式的多表连接算法，它可以一次同时进行多个表的连接操作，算法首先将维表中的记录读出，存入内存中的Hash序表，或者存入其他可按连接属性值进行检索的数据结构，然后依次读取事实表中的记录，对应于读出的每条记录，根据连接属性，查找内存中的各个维表形成的有序表，得到相应的元组，再利用这些元组完成连接操作。因为一般维表中的记录数是有限的，而事实表中的记录数却很多，与维表相比相差好几个数量级，并且表的连接可以通过一个中心表，即事实表来进行。该算法适用的条件为参加连接的表通过一个中心表来进行，除了中心表以外，参与连接运算的其他表的记录数较少，并且可以全部读入内存进行操作。当数据仓库的数据按照星型模式进行组织时，一般的多表连接查询都能够满足M-Hash-Join所要求的条件。8对于雪花结构的数据模型，有人提出了LINK-Join算法，它是基于雪花模10贵州大学硕士学位论文Hash型的多表连接算法，首先将维表中的记录读入内存中的表、排序表，或者其他可按连接属性值进行检索的数据结构，然后对其中一个维表进行循环，在每次循环中根据这个维表的当前记录值读取事实表中的记录，对应于读出的每条记录，根据连接属性，查找内存中的其他维表形成的有序表，得到相应的元组，再利用这些元组完成连接操作。对于两个表的连接运算，这种算法跟索引嵌套循环9连接类似，不过此算法节省的依然就是扫描索引的代价。在索引嵌套循环连接算法中，对于外层关系的每个元组需要对内层关系进行一次在索引上单个选择运算，扫描索引的代价在外层关系的每一次循环中都重复，因此线性搜索算法比索I/O引嵌套循环连接的开销要小。2聚集操作。(group-by)(Sum)(Average)聚集操作是对结果集进行分组求总和、平均值、最(Max)(Min)(Count)OLAP大值、最小值以及计数等的操作。作为提高查询响应速度的关键之一，分组聚集操作已引起了广泛重视，目前也已有了一些研究成果，10111213如文献提出的新的分组聚集计算技术，而更详细的数据立方体计算技术将在后面的章节中详细说明。6对于聚集操作的并行计算，文献中提出可以分布地处理聚集计算，以此提高OLAP查询的并行度，减少查询处理过程中的数据通讯量。通过对Oracle、SQLserver、PostgreSQL等数据库系统中聚集函数的分析，可以将OLAP查询中使用的聚集函数分为3类：(1)可分布式计算的聚集函数：包括SUM、COUNT、MAX、MIN等。对于可分布式计算的聚集函数，查询结果的每一个分组相当于一个累加器,通过将各个节点上的查询结果中相同分组的聚集值累加即可得到OLAP查询的最终结果。(2)基于代数运算的可分布式聚集计算函数：包括AVERAGE和方差类的聚集函数。(3)基于全局的不可分布式计算的聚集函数：包括基于全局位置的聚集函数，如MEDIAN、TOP(n)等。利用上述聚集函数的可分布计算特性和CUBE结构的特点，原本在单一节点中基于海量数据的OLAP查询操作，就转换成可以并行执行的多个节点子CUBE上的OLAP查询与查询结果合并运算，从而简化了系统的复杂度，提高了查询的并行执行度。于是划分的3类聚集函数转换成可并行处理的方法为：(1)对于可分布式计算的聚集函数，查询结果的每一个分组相当于一个累加器，OLAP查询的最终结果为多个节点子CUBE上相同分组查询结果的聚集值累加和。(2)基于代数运算的可分布式聚集函数可以通过可分布式计算的聚集函数的结果计算得出，比如AVERAGE计算可以转换为SUM和COUNT两个聚集函数的代数表达式。(3)对于基于全局的不可分布式计算的聚集函数，其结果为分组中全部排序记录特定位置的记录度量值，必须在全局排序的记录序列中才能得到正确的结果，不能在分布的多个分组的排序子集中分布处理。3.2.2基于物化视图的OLAP查询数据仓库的OLAP查询是面向海量数据的复杂查询，通常要对数据进行多表11贵州大学硕士学位论文连接和聚集等复杂处理，这是一个十分耗时的过程，影响了它的查询速度，然而，OLAP又要求它的查询被快速响应。为了解决这一问题，可以使用物化视图来提14高查询性能。OLAP物化视图是在数据仓库中使用冗余数据来提高查询效率的，它按照各自的分组属性预先计算一些常用查询，并保存其结果，这样，当查询执行时，就不需要查询多个基表并进行连接和聚集操作，而可以直接从保存的结果中响应查询，如此以来，大大缩减了查询响应的时间。与传统数据库中的视图不同，物化视图不是虚表，而是经过计算、包含大量数据并且存储在数据仓库中实实在在15的表。但是，物化视图也有负面作用，比如它的保存会占用一定的存储空间，而且为保持与基表数据的一致性还需要额外的维护开销。所以如何在数据仓库中选择合适的物化视图是一个重要的研究问题，物化视图的选择必须保证尽量少地16占用存储空间、较大地提高查询速度。除此之外，如何利用物化视图进行查询优化，如何维护物化视图的一致性也是这一领域研究的热点。在本节中，将详细介绍物化视图的选择问题。28DataCubeGray1996数据立方体（）由等人在年提出，它是一种用来在OLAP服务器上组织多维数据集的数据结构。有了数据立方体的概念以后，基于数据立方体的视图选择算法也就应运而生，它主要分为两类：物化视图静态选择算法和物化视图动态调整算法。1物化视图静态选择算法。物化视图静态选择算法是在给定的查询及存储空间的限制下，选择出满足算VHarinaray法目标的视图进行物化。比较典型的是等人在给出了基于维依赖17(Greed)格的代价、收益模型后提出的贪心算法，这为后来的相关研究奠定了1819BPUSPBS基础，此后也相继出现了一些改进算法，如算法、算法等。(1)贪心算法。该算法的基本思想是每次选择一个在当前看来是最优的视图，即相对于当前已经选定的物化视图集合来说效益最大的那个视图，直到所选择物化视图的总空间超过事先给定的空间限制为止。算法用数据立方格来表示视图间的依赖关系，(top它包含了所有的视图，假设一开始只有位于格最顶端的那张粒度最细的视图view)被物化，那么该视图与格中所有其它视图都是偏序关系，所以其它视图都可以由最顶端视图计算得到。但该算法有一个很大的缺点，就是其时间复杂度太高，为维的指数级，这使得时间复杂度会随着维数的增加而迅猛增加，从而无法处理维数较大的多维数据集。(2)BPUS(BenefitPerUnitSpace)算法。该算法与简单贪心算法十分类似，是一种多项式贪心算法，它是简单贪心算法的改进，由于考虑到了空间约束条件，因而每次物化选择的是单位空间内效益最大的视图，也就是说，它以单位空间效益作为判断的依据，按照单位空间效益的降序来选择视图。该算法在实际效