Subgraph Join: Efficient Processing Subgraph Queries on Graph-Structured XML Document

1. Introduction to Algorithms. MIT Press, Cambridge (1990)

   Google Scholar 

2. Al-Khalifa, S., Jagadish, H.V., Patel, J.M., Wu, Y., Koudas, N., Srivastava, D.: Structural joins: A primitive for efficient XML query pattern matching. In: Proceedings of the 18th International Conference on Data Engineering (ICDE 2002), pp. 141–152 (2002)

   Google Scholar 

3. Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: Optimal XML pattern matching. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (SIGMOD 2002), pp. 310–321 (2002)

   Google Scholar 

4. Chamberlin, D.D., Florescu, D., Robie, J.: XQuery: A query language for XML. W3C Working Draft (2001), http://www.w3.org/TR/xquery

5. Chien, S.-Y., Vagena, Z., Zhang, D., Tsotras, V.J., Zaniolo, C.: Efficient structural joins on indexed XML documents. In: Proceedings of 28th International Conference on Very Large Data Bases (VLDB 2002), pp. 263–274 (2002)

   Google Scholar 

6. Clark, J., DeRose, S.: XML path language (XPath). W3C Recommendation, November 16 (1999), http://www.w3.org/TR/xpath

7. Kaplan, H., Zwick, U., Cohen, E., Halperin, E.: Reachability and distance queries via 2-hop labels. In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2002), San Francisco, CA, USA, January 2002, pp. 937–946 (2002)

   Google Scholar 

8. Grust, T.: Accelerating XPath location steps. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (SIGMOD 2002), Hong Kong, China, August 2002, pp. 109–120 (2002)

   Google Scholar 

9. Shabo, R., Kaplan, H., Milo, T.: A comparison of labeling schemes for ancestor queries. In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2002), San Francisco, CA, USA, January 2002, pp. 954–963 (2002)

   Google Scholar 

10. Jiang, H., Lu, H., Wang, W., Ooi, B.C.: XR-Tree: Indexing XML data for efficient structural join. In: Proceedings of the 19th International Conference on Data Engineering (ICDE 2003), pp. 253–263 (2003)

    Google Scholar 

11. Jiang, H., Wang, W., Lu, H., Yu, J.X.: Holistic twig joins on indexed xml documents. In: Aberer, K., Koubarakis, M., Kalogeraki, V. (eds.) VLDB 2003. LNCS, vol. 2944, pp. 273–284. Springer, Heidelberg (2004)

    Google Scholar 

12. Kameda, T.: On the vector representation of the reachability in planar directed graphs. Information Process Letters 3(3), 78–80 (1975)

    Article  MathSciNet  Google Scholar 

13. Kaushik, R., Bohannon, P., Naughton, J.F., Korth, H.F.: Covering indexes for branching path queries. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data (SIGMOD 2002), pp. 133–144 (2002)

    Google Scholar 

14. Li, Q., Moon, B.: Indexing and querying XML data for regular path expressions. In: Proceedings of 27th International Conference on Very Large Data Base (VLDB 2001), pp. 361–370 (2001)

    Google Scholar 

15. Milo, T., Suciu, D.: Index structures for path expressions. In: Proceedings of the 7th International Conference on Database Theory (ICDE 1999), pp. 277–295 (1999)

    Google Scholar 

16. Jagadish, H.V., Agrawal, R., Borgida, A.: Efficient management of transitive relationships in large data and knowledge bases. In: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data (SIGMOD 1989), Portland, Oregon, May 1989, pp. 253–262 (1989)

    Google Scholar 

17. Schenkel, R., Theobald, A., Weikum, G.: HOPI: An efficient connection index for complex XML document collections. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., Böhm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol. 2992, pp. 237–255. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

18. Tollis, I.G., Tamassia, R.: Dynamic reachability in planar digraphs with one source and one sink. Theoretical Computer Science 119(2), 331–343 (1993)

    Article  MATH  MathSciNet  Google Scholar 

19. Sayed, A., Unland, R.: Indexing and querying heterogeneous xml collections. In: Proceedings of 14th International Conference on Computer Theory and Applications, Alex, Egypt (September 2004)

    Google Scholar 

20. Schenkel, R.: Flix: A flexible framework for indexing complex xml document collections. In: Proceedings of International Workshop on Database Technologies for Handling XML Information on the Web(DATAX 2004), Heraklion, Crete, Greece (March 2004)

    Google Scholar 

21. Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: XMark: A benchmark for XML data management. In: Bressan, S., Chaudhri, A.B., Li Lee, M., Yu, J.X., Lacroix, Z. (eds.) CAiSE 2002 and VLDB 2002. LNCS, vol. 2590, pp. 974–985. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

22. Rauhe, T., Alstrup, S.: Small induced-universal graphs and compact implicit graph representations. In: Proceedings of 2002 IEEE Symposium on Foundations of Computer Science (FOCS 2002), Vancouver, BC, Canada, November 2002, pp. 53–62 (2002)

    Google Scholar 

23. Sperberg-McQueen, C.M., Yergeau, F., Bray, T., Paoli, J.: Extensible markup language (xml) 1.0 (3rd edition). W3C Recommendation 2004 (February 2004), http://www.w3.org/TR/REC-xml/

24. Scholl, M., Tourtounis, S., Christophides, V., Plexousakis, D.: On labeling schemes for the semantic web. In: Proceedings of the Twelfth International World Wide Web Conference (WWW 2003), Budapest, Hungary, May 2003, pp. 544–555 (2003)

    Google Scholar 

25. Wang, W., Jiang, H., Lu, H., Yu, J.X.: PBiTree coding and efficient processing of containment joins. In: Proceedings of the 19th International Conference on Data Engineering (ICDE 2003), pp. 391–402 (2003)

    Google Scholar 

26. Gil, J., Zibin, Y.: Efficient subtyping tests with pq-encoding. In: Proceedings of the 2001 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA 2001), San Francisco, CA, USA, October 2001, pp. 96–107 (2001)

    Google Scholar 

27. Zhang, C., Naughton, J.F., DeWitt, D.J., Luo, Q., Lohman, G.M.: On supporting containment queries in relational database management systems. In: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data (SIGMOD 2001), pp. 425–436 (2001)

    Google Scholar 

28. Tsotras, V.J., Vagena, Z., Moro, M.M.: Twig query processing over graph-structured xml data. In: Proceedings of the Seventh International Workshop on the Web and Databases (WebDB 2004), pp. 43–48 (2004)

    Google Scholar 

Download references