A compressed accessibility map for XML
A compressed accessibility map for XML
复制标题
XML 的压缩可访问性地图
DOI：
10.1145/1005566.1005570
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
H. V. Jagadish
中科院分区：
文献类型：
--
作者：
Ting Yu;D. Srivastava;L. Lakshmanan;H. V. Jagadish
XML是数据表示和交换的无可争议的标准。随着公司通过Internet进行业务交易，允许授权客户直接访问甚至修改，XML数据在成本、准确性和及时性方面提供了许多优势。考虑到公司之间复杂的业务关系和信息的敏感性，必须使用复杂的访问控制规范有选择地提供访问。直接使用规范来确定用户是否有权访问XML数据项可能效率极低。对于每个数据项，完全具体化被授权访问它的用户的替代方案可能是空间效率低下的。在本文中，我们将介绍一种压缩的可访问性映射（CAM），作为XML数据访问控制问题的一种节省空间和时间的解决方案。CAM compensation通过利用树结构数据中可访问性的结构局部性来识别用户可以访问的XML数据项。我们提出了一种CAM查找算法，用于确定用户是否可以访问一个数据项，该数据项所花费的时间与XML数据中的项的深度和CAM大小的对数的乘积成比例。我们开发了一个算法，用于建立一个最佳大小CAM，需要时间线性的XML数据集的大小。虽然最优性不能保持增量下的数据项更新，我们提供了一个算法，增量保持接近最优。最后，我们通过实验证明了CAM的有效性，为多个用户在各种真实的和合成数据集。
XML is the undisputed standard for data representation and exchange. As companies transact business over the Internet, letting authorized customers directly access, and even modify, XML data offers many advantages in terms of cost, accuracy, and timeliness. Given the complex business relationships between companies, and the sensitive nature of information, access must be provided selectively, using sophisticated access control specifications. Using the specification directly to determine if a user has access to an XML data item can be extremely inefficient. The alternative of fully materializing, for each data item, the users authorized to access it can be space-inefficient. In this article, we introduce a compressed accessibility map (CAM) as a space- and time-efficient solution to the access control problem for XML data. A CAM compactly identifies the XML data items to which a user has access, by exploiting structural locality of accessibility in tree-structured data. We present a CAM lookup algorithm for determining if a user has access to a data item that takes time proportional to the product of the depth of the item in the XML data and logarithm of the CAM size. We develop an algorithm for building an optimal size CAM that takes time linear in the size of the XML data set. While optimality cannot be preserved incrementally under data item updates, we provide an algorithm for incrementally maintaining near-optimality. Finally, we experimentally demonstrate the effectiveness of the CAM for multiple users on a variety of real and synthetic data sets.