XML函数依赖研究综述

摘要/Abstract

摘要：

函数依赖作为数据库规范化的基础在关系理论中起着重要的作用。近年来，XML得到广泛应用并已成为互联网上数据传输和交换的标准。由于XML半结构化的特性，使得如何定义XML函数依赖使其具有更强的描述能力，以及如何解决相应的逻辑蕴涵问题成为当今学术界所面临的挑战。针对这些问题，系统地描述了目前关于XML函数依赖的研究现状，特别是把分析的重点放在如何定义函数依赖、判断其蕴涵关系以及从XML文档中发现函数依赖等问题上。最后讨论了诸如类型化函数依赖关系等一些相关的研究方向。

关键词: XML, 函数依赖, 逻辑蕴涵, 依赖发现

Abstract:

The concept of functional dependencies plays an important role in database theory since it is the basis of normal forms that are used to produce welldesign schema. Due to the complexity of the semistructured XML model, it is a challenge to define the functional dependencies and study the nature of those dependencies such as their capability of representation, logical implication and corresponding normal forms. The previous works in this area are surveyed and the approaches they deployed are described. Particularly, the paper focus on the comparison of functional dependencies definitions, the problem of logical implication and the discovery of dependencies. At last, some novel problems referring to dependencies such as relationship between value and type in shortly are discussed.

Key words: XML;functional dependencies;logical implication；dependencies discovery

刘嘉，廖湖声. XML函数依赖研究综述[J]. J4, 2014, 36(02): 331-339.

LIU Jia，LIAO Husheng. A survey on XML functional dependencies [J]. J4, 2014, 36(02): 331-339.

参考文献

［1］Bray T, Jean P. Extensible markup language (XML)［J］. World Wide Web Journal,1997,2(4):2766.
［2］Murata M, Lee D, Mani M, et al. Taxonomy of XML schema languages using formal language theory［J］. ACM Transactions on Internet Technology,2005,5(4):660704.
［3］Arenas M, Libkin L. A normal form for XML documents［J］. ACM Transactions on Database Systems, 2004 ,29(1):195232.
［4］Yu Cong, Jagadish H V. Efficient discovery of XML data redundancies［C］∥Proc of the 32nd International Conference on Very Large Data Bases,2006:103114.
［5］Liu Jixue, Vincent M, Liu Chengfei. Functional dependencies, from relational to XML［C］∥Proc of the 5th International Andrei Ershov Memorial Conference,2003:531538.
［6］Liu Jixue, Vincent M, Liu Chengfei. Local XML functional dependencies［C］∥Proc of the Interntational Workshop on Web Information and Data Management,2003:2328.
［7］Shahriar M S, Liu Jixue. On defining functional dependency for XML［C］∥Proc of 2009 IEEE International Conference on Semantic Computing,2009:595600.
［8］Vincent M, Liu Jixue, Liu Chengfei. Strong functional dependencies and their application to normal forms in XML［J］. ACM Transactions on Database Systems,2004,29(3):445462.
［9］Vincent M,Liu Jixue.Functional dependencies for XML［C］∥Proc of the 5th AsianPacific Web Conference,2003:2234.
［10］Wang Junhu.A comparative study of functional dependencies for XML［C］∥Proc of the 7th AsiaPacific Web Conference on Web Technologies Research and Development,2005:308319.
［11］Lee M, Ling T, Low W. Designing functional dependencies for XML［C］∥Proc of the 8th International Conference on Extending Database Technology,2002:145158.
［12］Tan Zijing, Pang Yinming, Shi Bele. Reasoning about functional dependency for XML［J］.Journal of Software,2003,14(9):15641570. (in Chinese)
［13］Lv Teng, Yan Ping, Wan Zhenxing. Functional dependencies for XML［J］.Journal of Chinese Computer Systems,2005,26(5):864868. (in Chinese)
［14］Hartmann S,Link S.More functional dependencies for XML［C］∥Proc of ADBIS’03,2003:355369.
［15］Armstrong W W. Dependency structures of data base relationships［C］∥Proc of the International Federation for Information Processing Congress, 1974:580583.
［16］Vincent M,Liu Jixue,Liu Chengfei.The implication problem for unary functional dependencies in XML ［EB/OL］.［20130616］.http:∥citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.3716.
［17］Hartmann S, Link S, Trinh T. Efficient reasoning about XFDs with preimage semantics［C］∥Proc of the 12th International Conference on Database Systems for Adocucced Applications,2007:10701074.
［18］Kot L,White W.Characterization of the interaction of XML functional dependencies with DTDs［C］∥Proc of the 11th International Conference on Database Theory,2007:119133.
［19］Lopes S, Petit J M, Lakhal L. Efficient discovery of functional dependencies and Armstrong relations［C］∥Proc of the 7th International Conference on Extending Database Technology,2000:350364.
［20］Huhtala Y, Juha K, Porkka P,et al. TANE:An efficient algorithm for discovering functional and approximate dependencies［J］. Computer Journal,1999,42(2):100111.
［21］Nol N, Rosine C. Functional and embedded dependency inference:A data mining point of view［J］. Information Systems, 2001, 26(7):477506.
［22］Trinh T. Using transversals for discovering XML functional dependencies［C］∥ Proc of the 5th International Symposium on Foundations of Information and Knowledge Systems,2008:199218.
［23］Shi Hang,Amagasa T,Kitagawa H.Fast detection of functional dependencies in XML data［C］∥Proc of XSym’10,2010:113127.
［24］Vincent M,Liu Jixue.Multivalued dependencies and a 4NF for XML［C］∥Proc of LAISE’03,2003:1429.
［25］Karlinger M, Vincent M, Schrefl M. Inclusion dependencies in XML:Extending relational semantics［C］∥Proc of DEXA’09,2009:2337.
附中文参考文献：
［12］谈子敬，庞引明，施伯乐. XML上的函数依赖推理［J］.软件学报,2003,14(9):15641570.
［13］吕腾，闫萍，王真星. XML的函数依赖［J］.小型微型计算机系统,2005,26(5):864868.

[1]	张晓琳,郭丹丹,郝琨. 一种适用连续不确定XML数据的索引[J]. J4, 2016, 38(02): 305-311.
[2]	杨高明1，方贤进1，陆奎1，王静2. 面向函数依赖的隐私保护研究[J]. J4, 2015, 37(11): 2154-2161.
[3]	张晓琳，郑春红，刘立新，吕庆. 高效的连续不确定XML数据Top-k查询算法[J]. J4, 2014, 36(06): 1101-1107.
[4]	白燕1,2，任庆昌2. 智能建筑中央空调监控系统存储优化策略研究[J]. J4, 2014, 36(03): 558-565.
[5]	赵伟，卓伟，李占波，王志华. 基于云计算的一种新的数据交换架构[J]. J4, 2013, 35(8): 15-19.
[6]	李丁月1，刘建勋2，翟海军2. 一种增量发现条件函数依赖的算法[J]. J4, 2013, 35(8): 149-155.
[7]	魏永山1，张峰1，陈欣1，韩燕波2，孙忠林1. 一种云计算环境下的XML查询数据服务的优化方法[J]. J4, 2013, 35(6): 30-36.
[8]	张晓琳，郑珍珍，刘立新，李玉峰. 连续概率XML数据查询处理技术[J]. J4, 2012, 34(12): 134-139.
[9]	李自胜1,2,肖晓萍3,龚〓伟1,2,李光明1,2. 医学影像学诊断报告书智能化书写方法研究[J]. J4, 2011, 33(4): 186-191.
[10]	刘海燕，张占军，杨健康. 基于图元的测试信息描述技术研究[J]. J4, 2010, 32(9): 73-75.
[11]	陈海燕,刘珍,刘建勋. 基于XML的工作流模型表示及映射算法研究[J]. J4, 2010, 32(7): 147-150.
[12]	明德廷,李娟,杨珺. 对加密的XML数据查询算法的研究与实现[J]. J4, 2010, 32(4): 142-145.
[13]	程学先蒋慧婷. 异构数据源集成实现的研究[J]. J4, 2008, 30(8): 86-88.
[14]	李东刘艾芳陈朝晖. 一种Native XML数据库的数据装载器设计[J]. J4, 2008, 30(7): 122-124.
[15]	陈传波吴翅喻之斌. 一种改进的分布式并行事务处理策略研究[J]. J4, 2008, 30(5): 102-105.