数据库前沿技术

1、若干数据库前沿技术的若干数据库前沿技术的理解和思考理解和思考周傲英复旦大学2022-2-21数据库研究进展*周傲英2提纲提纲l当前数据库研究重点的变化l三个重要的数据库研究问题l对等计算环境下的数据管理l流数据管理和挖掘lXML 数据管理和 Web 服务l我们正在进行的工作2022-2-21数据库研究进展*周傲英3当前数据库研究的重点当前数据库研究的重点l静止的查询和变化的数据l连续查询（continuous query）l流数据管理和挖掘l受限制的节点处理能力和不受限制的系统动态性l传感器网络上的查询处理、传感器网络数据分析l对等计算环境下的数据管理l数据模式的复杂化和元数据管理的标准化lX

2、ML数据管理和交换lWeb服务2022-2-21数据库研究进展*周傲英4提纲提纲l当前数据库研究重点的变化l三个重要的数据库研究问题l对等计算环境下的数据管理l流数据管理和挖掘lXML 数据管理和 Web 服务l我们正在进行的工作2022-2-21数据库研究进展*周傲英5P2P 数据管理数据管理 应用背景应用背景l从简单的文件共享向复杂的查询处理功能变化l信息检索：pSearch, PlanetP, PeerISl数据库查询：PIER, PIAZZA, PeerDB, Hyperion, l连续查询：PeerCQ, Buddy-CQ, Aurora*/Medusal从消息传递向内容路由变化l基

3、于 XML 的内容路由l应用场景：l金融、科学计算和数据管理、医疗、l其它松散耦合的虚拟组织l一些紧耦合，但在地理上分布的数据管理任务2022-2-21数据库研究进展*周傲英6P2P 数据管理数据管理 主要技术（主要技术（1）l从数据访问和索引角度看l散列 分布式散列表（Distributed Hash Table, DHT）lChord, CAN, Pastry, Tapestry, Viceroy, lDHT上的区域查询（range query）基于 LSH 和 Chord 的技术、基于 CAN 的区域查询缓存、lDHT上的关系运算算子的实现PIER（Berkeley）实现了四种不同的连接

4、算法l树型索引 P-treel可以被用来进行区域查询2022-2-21数据库研究进展*周傲英7P2P 数据管理数据管理 主要技术（主要技术（2）l从数据库模式集成和查询语义看l基于视图的数据集成lPIAZZA：模式映射、查询改写和优化lP2P数据库查询的语义l局部关系模型（LRM）l映射表的逻辑语义和实现（Hyperion）l加宽可达快照（dilated-reachable snapshot）语义（PIER）2022-2-21数据库研究进展*周傲英8P2P 数据管理数据管理 主要技术（主要技术（3）l从元数据管理看l基于标准协议的方式（PIER）l多索引/目录服务器方式l全自治的方式（Peer

5、DB, PIAZZA）l从分布式数据库和分布式查询处理角度看l查询传递（query shipping）、代码传递（code shipping）和代理传递（agent shipping）（PeerDB）l基于DHT的查询处理（PIER, PeerCQ）l突变查询处理（mutant query processing）2022-2-21数据库研究进展*周傲英9提纲提纲l当前数据库研究重点的变化l三个重要的数据库研究问题l对等计算环境下的数据管理l流数据管理和挖掘lXML 数据管理和 Web 服务l我们正在进行的工作2022-2-21数据库研究进展*周傲英10流数据管理和挖掘流数据管理和挖掘 应用背景

6、应用背景l（相对）静态的查询、动态的数据l挑战l和数据量呈线性的时间复杂度l固定大小的内存l单遍扫描数据集l在任意时刻输出是准确、可靠的l模型在任意时间都可以输出l应用场景：l网络监控和交通工程l电信记录管理和分析l商业交易管理和分析l金融信息监控l制造业和供应链工程和工业过程控制l传感器信息监控lWeb日志分析l海量数据处理l2022-2-21数据库研究进展*周傲英11流数据管理和挖掘流数据管理和挖掘 研究角度研究角度l理论分析l一般采用随机算法（randomized algorithms），研究重点是算法的界l联机算法设计l重点是算法在实际数据集上的效率l模型的变化l滑动窗口模型l挖掘模型

7、的变化l研究的重点是及时的模型改变2022-2-21数据库研究进展*周傲英12流数据管理和挖掘流数据管理和挖掘 主要技术（主要技术（1）l连续查询处理l系统设计和开发lTriggerManlOpenCQ (Georgia Tech.)lNiagara-CQ (Wisconsin Madison)lCACQlAurora (MIT/Brown/Brandies)lAdaptiveCQlTelegraphCQ (U.C. Berkeley)lSTREAM (Stanford)User/ApplicationStream QueryProcessorDataStreamManagementSyste

8、m(DSMS)2022-2-21数据库研究进展*周傲英13流数据管理和挖掘流数据管理和挖掘 主要技术（主要技术（2）l连续查询算子的实现l各种流水线联接算法的实现l基本数据结构的研究lSketch 方法（基于散列的技术）l指数直方图（exponential histogram, EH）方法l抽样方法l频繁项/频繁项集挖掘lSticky sampling/lossy countingl带删除的频繁项集挖掘lCounting Bloom filter方法l考虑 false positive 的方法2022-2-21数据库研究进展*周傲英14流数据管理和挖掘流数据管理和挖掘 主要技术（主要技术（3）

9、l流数据聚类l增量式的传统聚类算法l基于 K-means 的方法（Fayyad et al./Guha et al.）l考虑聚类变化的方法：金字塔技术（Han et al.）l流数据分类l传统的增量式的决策树分类lHeoffding tree和基于它的VFDT（Gibbons et al.）l可调整的VFDT：CVFDT（Gibbons et al.）l使用整合技术（emsemble）的技术（Han et al.）2022-2-21数据库研究进展*周傲英15流数据管理和挖掘流数据管理和挖掘 主要技术（主要技术（4）l其它相关技术l时序（time series）分析l时序模式（sequentia

10、l pattern）挖掘l时序预测ll最近邻查询（Muthukrishnan et al.）l变化（change）分析（Gehrke et al.）l跳变（burst）分析（Shasha et al., Kleinberg）l相关性分析（Shasha et al.）2022-2-21数据库研究进展*周傲英16提纲提纲l当前数据库研究重点的变化l三个重要的数据库研究问题l对等计算环境下的数据管理l流数据管理和挖掘lXML 数据管理和 Web 服务l我们正在进行的工作2022-2-21数据库研究进展*周傲英17XML 数据管理和数据管理和 Web 服务服务 应用背景应用背景lWeb 服务本身是一类

11、非常重要的应用lXML 还在如下领域中有着重要的应用l数据表示和数据交换l元数据管理lXML 内容路由l2022-2-21数据库研究进展*周傲英18XML 数据管理和数据管理和 Web 服务服务 主要技术主要技术lXML 数据管理lXML 数据存储lXML 数据索引lXML 数据变换lXML 数据压缩lXML 数据更新lXML 流数据处理lXML 数据的模式和查询的语义lWeb 服务lWeb 服务架构的设计l分布式的、P2P 的 UDDI 目录设计l分布式的和 P2P 的服务使用lWeb 服务和对等计算技术、网格技术的结合2022-2-21数据库研究进展*周傲英19提纲提纲l当前数据库研究重点

12、的变化l三个重要的数据库研究问题：它们的结合l对等计算环境下的数据管理l流数据管理和挖掘lXML 数据管理和 Web 服务l我们正在进行的工作2022-2-21数据库研究进展*周傲英20当当 流数据流数据 碰到碰到 对等计算对等计算（1）l传感器网络l挑战l通讯能力和能源限制l计算能力的限制l海量（多）数据流l动态的传感器和网络环境当前的将来的(MEMS)Mote (Berkeley)Cricket (MIT)SmartLocus (HP-Labs)Mantis (UC Boulder )Smart Dust (Berkeley)2022-2-21数据库研究进展*周傲英21当当 流数据流数据

13、碰到碰到 对等计算对等计算（2）l传感器网络（续）l相关的研究项目lTinyOS/TinyDB: U.C. BerkeleylCougar: CornelllQuasar: UCIlLECS: UCLAll相关技术l即兴（ad hoc）网络和无线网络中的数据路由l动力相关（power-awareness）的计算和优化l网络中的查询处理技术聚集（aggregation）操作查询语言设计查询优化2022-2-21数据库研究进展*周傲英22当当 流数据流数据 碰到碰到 对等计算对等计算（3）l内容路由l节点：根路由器（root router）、客户机（client）、路由器（router）l数据：X

14、ML包 XML流l主要技术l基于网孔（mesh）的重叠网络（overlay network）构造lXML包的视图选择（U. Washington）lXML数据过滤2022-2-21数据库研究进展*周傲英23当当 XML 遇到遇到 流数据流数据 lXML 内容路由lXML 数据过滤l基于自动机的方法XFilter, YFilter, l基于索引的方法l基于Bloom filter的方法lXML 包的视图选择l脱机（offline）视图选择l联机（online）视图选择（open problem）2022-2-21数据库研究进展*周傲英24提纲提纲l当前数据库研究重点的变化l三个重要的数据库研究问

15、题l对等计算环境下的数据管理l流数据管理和挖掘lXML 数据管理和 Web 服务l我们正在进行的工作2022-2-21数据库研究进展*周傲英25 我们的工作我们的工作（1）lP2P 数据管理lP2P 数据管理的基本问题l资源定位和路由：small-world search CCGrid2003l重叠网络的构建和协议：C2 GCC2003lP2P 环境下的信息检索和查询l基于关键词的检索 WISE2002lSQL 查询处理：PeerDB ICDE2003, PeerViewl元数据管理：Coordinator Overlay Network (CON)l缓存和复本的管理和维护：CC-Buddy

16、WWW2004 Poster, DEXA2004l基于对等计算技术的虚拟研究平台的开发2022-2-21数据库研究进展*周傲英26 我们的工作我们的工作（2）l流数据管理和挖掘l频繁项/项集挖掘l基于 count Bloom filter 的方法 CIKM2003l考虑 false positive 的方法 VLDB2004l密度估计 DASFAA2003l流数据的聚类和分类l流数据上的跳变（burst）分析l流数据分析工具集（toolkit）的开发2022-2-21数据库研究进展*周傲英27 我们的工作我们的工作（3）lXML 数据管理和 Web 服务lXML 数据存储和查询lVXMLR WWW JournallXML DB Benchmark ICDE2003, with HKUST/CUHK/NEUlXML 存储模式设计 DASFAA2003lXML 数据索引 WAIM2002/2003, ER Workshop2003lXML 数据的规范化存储和更新 IDEAS2003lXML