微信服务号

微信订阅号

2025年4月4日 4:22 星期五
首页 > 过刊浏览>2004年第15卷第11期 >1661-1670
PDF HTML阅读 XML下载 导出引用 引用提醒
集合索引结构及其联接操作
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.69933010, 60303008 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2002AA4Z3430 (国家高技术研究发展计划(863))

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [14]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    集合类型是面向对象数据库和对象-关系数据库中的一种重要的数据类型.提出了集合类型数据的一种索引结构Set_struc,并提出了基于Set_struc的集合联接算法.Set_struc通过合并集合数据的公共前缀组织数据.这种方法可以减少重复数据和重复模式的存储空间,并通过基于树的联接算法提高集合数据上的联接操作的性能.其性能优于现有的算法,如PSJ(partition based join).

    Abstract:

    Set type is an important data type in object-oriented database system and object-relational database system. An index structure of set type Set_struc is presented in this paper. In Set_struc all sets are organized as a tree, and the sets with common prefix are merged. So the size of the index will be decreased for the data set with a large number of repeated data and frequent patterns. Based on Set_struc, an algorithm of join operation with Set_struc is presented. Its performance is better than other methods such as PSJ (partition based join).

    参考文献
    [1]Shi BL, Ding BK, Wang W. Database System Tutorial. 2nd ed., Beijing: Higher Education Press, 2003 (in Chinese).
    [2]Beeri C. New data models and language--The challenge. In: Proc. Of the 11th ACM SIGACT-SIGMOD-SIGART Symp. On Principles of Database Systems. New York: ACM Press, 1992. 351～362.
    [3]Cattell RGG. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1993.
    [4]Tannen V. Languages for collection Types. In: Proc. of the 13th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. New York: ACM Press, 1993. 150～154.
    [5]Shanmugasundaram J, Tufte K, Zhang C, He G, DeWitt DJ, Naughton JF. Relational databases for querying XML documents: Limitations and opportunities. In: Atkinson MP, Orlowska ME, Valduriez P, Zdonik SB, Brodie ML, eds. Proc. of the 25th Int'l Conf. on Very Large Data Bases. Morgan Kaufmann, 1999. 302～314.
    [6]Helmer S, Moerkotte G. A study of four index structure for set-valued attributes of low cardinality. Reihe Informatik 2, University of Mannheim. 2003.
    [7]Hellerstein JM, Pfeffer A. The RD-Tree: An index structure for sets. Technical Report, No.1252, University of Wisconsin, Madison, 1997.
    [8]Ramasamy K, Patel JM, Naughton JF, Kaushik R. Set containment joins: The good, the bad and the ugly. In: Abbadi AE, Brodie ML, Chakravarthy S, Dayal U, Kamel N, Schlageter G, Whang KY, eds. Proc. of the 26th Int'l Conf. on Very Large Data Bases. Morgan Kaufmann, 2000. 351～362.
    [9]Helmer S, Moerkotte G. Evaluation of main memory join algorithms for joins with subset join predicates. In: Jarke M, Carey MJ, Dittrich KR, Lochovsky FH, Loucopoulos P, Jeusfeld MA, eds. Proc. of the 23rd Int'l Conf. on Very Large Data Bases. Morgan Kaufmann, 1997. 386～395.
    [10]Mamoulis N. Efficient processing of joins on set-valued attributes. In: Halevy AY, Ives ZG, Doan AH, eds. Proc. of the 2003 ACM SIGMOD Int'l Conf. on Management of Data. ACM Press, 2003. 157～168.
    [11]Melnik S, Garcia-Molina H. Adaptive algorithms for set containment joins. ACM Trans. on Database Systems, 2003,28(2):1～38.
    [12]Garcia-Molina H, Ullman JD, Widom J. Database System Implementation. Prentice Hall, 2000.
    [13]Agrawal R, Srikant R. Fast algorithms for mining association rules in large databases. In: Bocca JB, Jarke M, Zaniolo C, eds. Proc. of the 20th Int'l Conf. on Very Large Data Bases. Morgan Kaufmann, 1994. 487～499.
    [14]施伯乐,丁宝康,汪卫.数据库系统教程.第2版,北京:高等教育出版社,2003.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

汪卫,谢闽峰,陶春,施伯乐.集合索引结构及其联接操作.软件学报,2004,15(11):1661-1670

复制
分享
文章指标
  • 点击次数:3823
  • 下载次数: 5354
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2003-05-26
  • 最后修改日期:2003-09-26
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19784123位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号