Reasoning about keys for XML

被引：62
作者：
Buneman, P
Davidson, S
Fan, WF
Hara, C [1 ]
Tan, WC
机构：
[1] Univ Fed Parana, Dept Informat, BR-81531990 Curitiba, Parana, Brazil
[2] Bell Labs, Murray Hill, NJ 07974 USA
[3] Univ Calif Santa Cruz, Dept Comp Sci, Santa Cruz, CA 95064 USA
[4] Univ Penn, Dept Comp & Informat Sci, Philadelphia, PA 19104 USA
[5] Univ Edinburgh, Sch Informat, Edinburgh EH9 3JZ, Midlothian, Scotland
来源：
INFORMATION SYSTEMS | 2003年 / 28卷 / 08期
基金：
美国国家科学基金会;
关键词：
XML keys; axiomatization; logical implication; satisfiability;
D O I：
10.1016/S0306-4379(03)00028-0
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We study absolute and relative keys for XML, and investigate their associated decision problems. We argue that these keys are important to many forms of hierarchically structured data including XML documents. In contrast to other proposals of keys for XML, we show that these keys are always (finitely) satisfiable, and their (finite) implication problem is finitely axiomatizable. Furthermore, we provide a polynomial time algorithm for determining (finite) implication in the size of keys. Our results also demonstrate, among other things, that the analysis of XML keys is far more intricate than its relational counterpart. (C) 2003 Elsevier Ltd. All rights reserved.
引用
收藏
页码：1037 / 1063
页数：27
相关论文
共 41 条
  • [1] Abiteboul S., 1997, Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1997, P122, DOI 10.1145/263661.263676
  • [2] Abiteboul S., 1999, DATA WEB RELATIONS S
  • [3] Abiteboul S., 1995, Foundations of databases, V1st
  • [4] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [5] APPARAO V, 1998, DOCUMENT OBJECT MODE
  • [6] Arenas M., 2002, P INT C DAT EXP SYST, P269
  • [7] ARENAS M, 2002, P ACM S PRINC DAT SY
  • [8] The SWISS-PROT protein sequence database and its supplement TrEMBL in 2000
    Bairoch, A
    Apweiler, R
    [J]. NUCLEIC ACIDS RESEARCH, 2000, 28 (01) : 45 - 48
  • [9] The EMBL Nucleotide Sequence Database
    Baker, W
    van den Broek, A
    Camon, E
    Hingamp, P
    Sterk, P
    Stoesser, G
    Tuli, MA
    [J]. NUCLEIC ACIDS RESEARCH, 2000, 28 (01) : 19 - 23
  • [10] BENEDIKT M, 2003, P INT C DAT THEORY S
12345