何雪梅 唐常杰 王利强 张天庆 四川联合大学计算机系 成都（610064）
何
摘 要 本文分析了Web数据的特点以及由此引起的Web数据仓库的困难，并以我们建立的Web数据仓库原型为例讨论了Web数据仓库的解决方法，提出并实现了从Web中提取数据的Wrapper算法。 关键词 数据仓库 环球网 半结构
RESEARCH ON WEB-BASED DATA WAREHOUSE
He Xuemei,Tang Changjie,Wang Liqiang,Zhang Tianqing
Sichuan Union University, Computer Science Department ,Sichuan,Chengdu 610064
Abstract Based on the features of web data , a prototype of web data warehouse—W_Warehouse is proposed. The wrapper algorithm to extract data from web is also implemented. Key Words Data Warehouse, WWW, Semistructure
1引言
数据仓库是近几年来出现的、发展迅速的一种技术。数据仓库把一个单位的历史数据收集到一个中央仓库中以便于处理，它是支持决策过程的、面向主题的、随时间而变的、持久的数据集合。调查研究表明，大多数企业并不缺乏数据，而是受阻于过量的冗余数据和数据不一致。而且它们变得越来越难于访问、管理和用于决策支持，信息中心面临着开发决策支持应用的需求被大量积压，所要开发的应用变得越来越复杂和耗费人力，数据仓库正是解决这一矛盾的工具。
近年来，WWW成为当今网络上的信息主体,其信息传送和存储量均超过其它类型协议的工具(传送量占21%,存储量占26.3%)。WWW是一个巨大的数据源，人们自然产生了将 WWW和数据仓库相互转换的需求，并形成了当前Web数据库的研究热点。 本文分析Web数据特点，构建了一个能够获取Web数据的数据仓库原型，详细讨论了其中关键的Wrapper算法。 2 Web数据的半结构
Web中有大量丰富的数据：文本、图片、声音、图像等，这些数据多存在于HTML超文本文件中；没有严格的结构及类型定义，被称为半结构化的（semi-structured）数据。目前尚没有一个关于半结构化的精确定义，其内涵依赖于用户所处理的问题及观察数据的角度。图1是一个Web上的半结构数据的例子。
在Web中主要存在两种结构。一种是超文本结构，依据此结构，逻辑上相关联的结构信息在物理上被链接，利用标签能够将文件以及图象的区域连接到本地计算机或Internet其他地方的文档中去。另一种是由HTML文本特点决定的文本组织结构,通过HTML语言，用不同的方法将数据组织在文本中。例如，给定一个HTML页，通过HTML标签容易识别该页的标题（title)或一些复杂的结构，如表格(table)、项目列表(list)等。 Web数据仓库用户感兴趣的往往是这些半结构化的数据。在HTML文档中，数据所在的行一般是一些没有完整的语法结构的句子片段，从这种文档中提取数据不能简单套用传统的信息提取的方法。 信息提取(Information Extraction)的目标是根据文档内容来概括、总结文档。它涉及自然语言处理(Natural 1 国家自然科学基金69773051号资助项目。 唐常杰(联系人)，四川联合大学计算机系教授何雪梅，王利强 四川联合大学计算机系95级数据库方向研究生，张天庆，四川联合大学计算机系讲师 1 Language Processing ,NLP)的技术，主要任务是从文本中识别预先定义的信息类型，如用在商业领域的一个信息提取系统会提取公司名称、产品、设备、商业数据等。用自然语言处理的方法进行信息提取要求所处理的文本信息具有完整的句法、语法结构。因为Web半结构数据的特点给Web数据仓库带来了先天的困难，对此我们提出一种新的方法进行信息提取。 图1 来源http://www.internet.net 3 Web数据模型及其视图 研究表明，一般不能简单地使用自然语言处理的方法来进行Web数据的提取。根据Web数据的结构特点我们将传统的数据库技术扩展到Web数据，对Web数据源添加数据库模型的概念，引入新的视图定义语言并在其上获取数据。 3.1 数据模型 每一个Web页可视为由URL唯一确定的对象，它包含一个属性集合，这些属性对应于Web页中相应的信息段。属性的类型可以是文本(text)、图象(image)、链点(anchor)等简单类型；也可以是复杂类型，如具有嵌套结构的列表等。复杂类型属性的值是多值的，如列表属性的值又可以是文本，图象，链点等。一个Web页的数据模型可以表示为： P(A1：T1，A2：T2，…An: Tn) 其中P是Web页的名称，Ai表示属性，Ti表示类型。 图1的数据模型可以表示为： Product{ Manufacturer: TEXT; ProductList: LIST OF { Name: ANCHOR; Price: TEXT; } } 3.2 视图定义 在引入Web页的数据模型基础上定义关系视图，实现用结构化视图表示Web中的半结构数据。 一个针对Web数据模型的视图定义语言的格式为： DEFINE VIEW R(B1:data type，B2 :data type，…Bn: data type) AS SELECT A1， A2…，An ON S 其中 R是关系的名称，B1，B2…Bn是属性名，A1，A2…An是Web页数据模型中的属性，S是数据模型的名称。在定义视图时将属性的类型转化为数据仓库中数据库管理系统的数据类型，用data type表示。 2 4 W_Warehouse数据仓库原型 目前市场上的数据仓库产品解决了从关系型数据库和一些文件系统中获取数据。但是，还没有一个数据仓库系统很好地解决从Web中提取数据的问题。 W_Warehouse是一个在Windows平台上，用Viscual C++开发的，以我们已经开发的HBase for Windows为数据库管理系统的数据仓库系统原型。W_Warehouse的特点及难点都在于从Web中提取数据。 图2为W_Warehouse的结构。这个数据仓库用HBase的工作区和I/O机制表示从数据源中获取的底层详细数据，新的版本将加入多维数据管理的模块实现用多维数据模型表示综合数据。 目前W_Warehouse支持从SQL Server及Web中获取数据。Visual C++的MFC类库可以通过ODBC（开放数据库链接）和ODBC驱动程序访问数据库。而通过WinInet类可以编写使用Http协议从网络数据源（服务器）访问信息的Internet客户应用程序。 各模块的功能如下： (1) Wrapper Wrapper将查询转换为数据源系统可以理解的命令或查询，并将得到的原始的结果数据翻译为数据仓库中HBase的数据格式。对每一种数据源需要不同的Wrapper，因为Wrapper的功能依赖于数据源的类型。对于运作数据库系统（如：SQL Server），Wrapper的功能是将查询转化为在运作环境中的查询,并将数据从运作数据库中的数据模型翻译成数据仓库中的数据模型。 W_Warehouse的难点之一是获取Web数据源的Wrapper模块。它的特殊困难在于：在数据源端没有标准的查询语言，故对每一个Web页应有特定的应用程序提取数据。但是作为数据仓库数据源的Web页是不断变化和增加的，对Wrapper程序的硬编码(hard code)显然是不能接受的。使一个Wrapper程序可以适用于不同Web页的数据提取成为我们研究的主要问题，本文第5节提出了一个基于机器学习的Wrapper算法。 Data Warehouse 图2 W_Warehouse的结构 (2) View Specifier 3 MetaData Loader View Specifier Wrapper Wrapper TCP/IP ODBC WWW Data Source View Specifier的功能是提出查询，指出Web页中感兴趣的数据及其关系模型的定义。Wrapper根据View Specifier所定义的视图提取及翻译数据。 Wrapper根据定义的视图提取数据，放入.WDB数据文件。目前在W_Warehouse中用图形界面的形式实现视图的定义。 （3） Loader Loader将Wrapper获取的数据文件转化为HBase中的DBF数据库文件，装载到数据仓库。在装载从不同数据源获取的数据时Loader还应有集成数据的功能。 5 Wrapper算法 在W-Warehouse中Wrapper根据View Specifier定义的视图提取Web中相关数据，由机器来确定哪些是用户感兴趣的数据。我们采用了机器学习中基于例子进行学习的方法，给Wrapper输入Web中的数据作为训练的实例，Wrapper通过学习获得该页中用户感兴趣的数据的格式描述，然后用模式匹配的方法将此Web页中所有满足此格式描述的数据提取出来。对于不同Web的页，根据视图定义及训练实例，Wrapper均可提取出用户感兴趣的数据，这一点对于不断增加、变化的Web页是非常有意义的。 图3是此算法的描述。 Exam- ple View Definer LineDes Learner Map rules StrLine[] Delimiter Pre-processor Navi-gator WWW Extractor .WDB Loadrer .DBF 图3 Wrapper数据提取算法的描述 (1)对HTML文本预处理 HTML文件中没有明确的标记表示数据的结构，结构隐含于标签中。预处理的目的是利用标签将文本划分为逻辑上的行。各个Web站点的文档结构各不相同，体现结构所用的标签也不同。例如，在一些文本中用 表示新的一行的开始。针对标签的特点，该算法定义了两级分隔符，首先利用第一级分隔符分隔文本，若所得到的行的长度大于50个字符，则用第二级分隔符继续分隔此行。分隔符不是固定的，针对一些特殊的页面可以修改、增加、删除。 分隔符分为两级： level1: , level2: , 4 其中Preprocessor算法如下： CWrapper::GenerateLine() { pFile=OpenHttpFile(); //打开一个HTML文件 InitDelimiters(level=1); //首先用第一级分隔符 // 对文件分行 while (pFile->ReadString(sz, 2) ) //每次从文件读 //入一个字符 { if(InTag) //如果当前字符在标签中 { ReadUntillGetTag(); //获得当前标签 InTag=false; if (InDelimiters(Tag)) //如果当前标签 { //是第一级分隔符，则新的一行开始 if(strLine[LastLine].GetLength()>50) //如果上一行的长度大于50，则用二 // 级分隔符对其再次分行 { InitDelimiters(level=2); DivideLine(strLine[LastLine]); InitDelimiters(level=1); } strLine[CurrentLine]=Tag; } else strLine[CurrentLine]+=Tag; } else { if(!strcmp(sz,\"<\")) InTag=true; else strLine[CurrentLine]+=sz; } } } 经过预处理后，HTML文本被分为行，放入数组strLine[]中。 (2)Learner View Specifier 以图形界面的方式要求用户输入有关视图的定义，包括属性名称、数据类型、数据长度。接着用户输入符合此视图定义的一条记录作为Learner的训练实例。Learner在strLine[]中找到例子数据所在的行，并产生其行描述LineDes。LineDes是通过移去标签中的参数并用变量代替所有出现的自由格式文本而产生。如一个逻辑行为： 5 至此，Learner学习的结果是用户感兴趣的数据所在的行的行描述及其映射规则。 (3)Extractor Extractor在strLine[]中匹配所有满足LineDes的行，并将数据写入.WDB文件。下面是从图1提取数据得 到的.WDB文件。 … Deskpro 2000 Mt Pent-166 2.5Gb 32Mb 8X Cdrom 256K Cache Win3.1/95.......$1424.49 Deskpro 2000 Pent-133 1.2Gb-Hd 16Mb Pci/Isa 256K Cache Win3.1/95........$1009.29 Deskpro 2000 Pent-133 2.5Gb-Hd 16Mb Pci/Isa 256K Cache Win3.1/95........$1113.19… 6 W_Warehouse中的数据组织 W_Warehouse中的数据按照决策的需要组织成不同主题的数据仓库表。为了易于OLAP,DSS等数据仓库用户的操作，W_Warehouse构造了多维结构的汇总表。另外在W_Warehouse中还有对数据仓库所有组成单元的解释性数据—元数据。图4是W_Warehouse中的数据组织结构。 7 小结 目前数据仓库的研究已经越过了初期的模型研究阶段，数据仓库与WWW的结合是一项方兴未艾 环境 数据仓库 主题1… 主题表1…（关系模型） 主题表n （关系模型） 汇总表1… (多维模型) 汇总表n… (多维模型) 主题n 元数据 源数据描述文件 Wrapper产生的元数据 Loader产生的元数据 HBase 中的元数据 图4 W_Warehouse中的数据组织结构 的热点技术。我们在Web数据仓库实现方面作了探索和尝试，在数据的组织及加工方面还需要进一步的研究。 参考文献： 1 2 3 4 唐常杰、张天庆、魏志毅、周韬，数据库管理系统内部结构及其C语言实现，电子科技大学出版社，1995 Harjinder S.Gill ,数据仓库——客户/服务器计算指南，清华大学出版社，1997 Stephen Soderland,Learning to Extract Text-based Information from the World Wide Web,Proc.of Third International Conference on Knowledge Discovery and Data Mining(KDD-97) Joachim Hammer,Hetor Garcia-Molina,Template-Based Wrappers in the TSIMMIS System http://www-db.staford.edu/tsimmis 5 J.Hammer,H.Garcia-Molina,J.Chao,Extratcting Semistructured Information from the Web http://www-b.stanford.edu/tsimmis/publications.htm 6 7 因篇幅问题不能全部显示，请点此查看更多更全内容
表示新的一行的开始，而在另一些文本中用
,,
,,
, ,
,
,
,
,
Compaq