Meta-data indexing for XPath location steps

ABSTRACT

XML is the de facto standard for data representation and exchange over the Web. Given the diversity of the information available in XML, it is very useful to annotate XML data with a wide variety of meta-data, such as quality and sensitivity. When querying such XML data, say using XPath, it is important to efficiently identify the data that meet specified constraints on the meta-data. For example, different users may be satisfied with different levels of quality guarantees, or may only have access to different parts of the XML data based on specified security policies. In this paper, we address the problem of efficiently identifying the XML elements along a location step in an XPath query, that satisfy meta-data range constraints, when the meta-data levels are specifically drawn from an ordered domain (e.g., accuracy in [0,1], recency using timestamps, multi-level security, etc.). More specifically, we develop a family of index structures, which we refer to as meta-data indexes, to address this problem. A meta-data index is easily instantiated using a multi-dimensional index structure, such as an R-tree, incorporating novel query and update algorithms. We show that the full meta-data index (FMI), based on associating each XML element with its meta-data level, has a very high update cost for modifying an element's meta-data level. We resolve this problem by designing the inheritance meta-data index (IMI), in which (i) actual meta-data levels are associated only with elements for which this value is explicitly specified, and (ii) inherited meta-data levels and inheritance source nodes are associated with non-leaf nodes of the index structure. We design efficient query (for all XPath axes) and update (of meta-data levels) algorithms for the IMI, and experimentally demonstrate the superiority of the IMI over the FMI using benchmark data sets.

REFERENCES

• 1: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 2: A. Berglund, S. Boag, D. Chamberlin, M. F. Fernandez, M. Kay, J. Robie, and J. Simeon. XML path language (XPath) 2.0. W3C Working Draft. Available from http://www.w3.org/TR/xpath20/.
• 3: Elisa Bertino , Silvana Castano , Elena Ferrari, Securing XML Documents with Author-X, IEEE Internet Computing, v.5 n.3, p.21-31, May 2001 [doi>10.1109/4236.935172 ]
• 4: D. Bhagwat, L. Chiticariu, W. C. Tan, and G. Vijayvargiya. An annotation management system for relational databases. In Proc. of VLDB, 2004.
• 5: Peter Buneman , Sanjeev Khanna , Wang-Chiew Tan, On propagation of deletions and annotations through views, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543633]
• 6: Sudarshan S. Chawathe , Serge Abiteboul , Jennifer Widom, Representing and Querying Changes in Semistructured Data, Proceedings of the Fourteenth International Conference on Data Engineering, p.4-13, February 23-27, 1998
• 7: S. Cho, S. Amer-Yahia, L.V.S. Lakshmanan, and D. Srivastava. Optimizing the secure evaluation of twig queries. In Proc. of VLDB, 2002.
• 8: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 9: Ernesto Damiani , Sabrina de Capitani di Vimercati , Stefano Paraboschi , Pierangela Samarati, Design and implementation of an access control processor for XML documents, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.59-75, June 2000
• 10: Tamraparni Dasu , Theodore Johnson, Exploratory Data Mining and Data Cleaning, John Wiley & Sons, Inc., New York, NY, 2003
• 11: Lois M. L. Delcambre , David Maier , Shawn Bowers , Mathew Weaver , Longxing Deng , Paul Gorman , Joan Ash , Mary Lavelle , Jason Lyman, Bundles in Captivity: An Application of Superimposed Information, Proceedings of the 17th International Conference on Data Engineering, p.111-120, April 02-06, 2001
• 12: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 13: Torsten Grust, Accelerating XPath location steps, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564705]
• 14: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 15: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 16: Sushil Jajodia , Ravi Sandhu, Toward a multilevel secure relational data model, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.50-59, May 29-31, 1991, Denver, Colorado, United States
• 17: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 18: G. Mihaila, L. Raschid, and M.-E. Vidal. Querying "quality of data" metadata. In Proc. of IEEE META-DATA Conference, 1999.
• 19: Sudarshan Murthy , David Maier , Lois Delcambre, Querying bi-level information, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017078]
• 20: K.V. Ravikanth, D. Agrawal, A. El-Abbadi, A.K. Singh, and T. Smith. Indexing hierarchical data. Technical Report, UCSB, CS-Tr-9514, 1995.
• 21: Harald Schöning, Tamino - A DBMS designed for XML, Proceedings of the 17th International Conference on Data Engineering, p.149-154, April 02-06, 2001
• 22: H. Wang, S. Park, W. Fan and P. S. Yu. ViST: A dynamic index method for querying XML data by tree structures. In Proc. of VLDB, 2003.
• 23: Ting Yu , Divesh Srivastava , Laks V. S. Lakshmanan , H. V. Jagadish, A compressed accessibility map for XML, ACM Transactions on Database Systems (TODS), v.29 n.2, p.363-402, June 2004 [doi>10.1145/1005566.1005570]
• 24: J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proc. of CIDR, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation

Keywords:
XML, hierarchical inheritance, meta-data index