On labeling schemes for the semantic web

ABSTRACT

This paper focuses on the optimization of the navigation through voluminous subsumption hierarchies of topics employed by Portal Catalogs like Netscape Open Directory (ODP). We advocate for the use of labeling schemes for modeling these hierarchies in order to efficiently answer queries such as subsumption check, descendants, ancestors or nearest common ancestor, which usually require costly transitive closure computations. We first give a qualitative comparison of three main families of schemes, namely bit vector, prefix and interval based schemes. We then show that two labeling schemes are good candidates for an efficient implementation of label querying using standard relational DBMS, namely, the Dewey Prefix scheme [6] and an Interval scheme by Agrawal, Borgida and Jagadish [1]. We compare their storage and query evaluation performance for the 16 ODP hierarchies using the PostgreSQL engine.

References

1. R. Agrawal, A. Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In Proc. of the SIGMOD Inter. Conf. On Manag. Of Data, pages 253--262, 1989.]]
2. H. Aït-Kaci, R. Boyer, P. Lincoln, and R. Nasr. Efficient implementation of lattice operations. ACM Trans. on Progr. Languages and Systems, 11(1):115--146, 1989.]]
3. S. Alexaki, G. Karvounarakis, V. Christophides, D. Plexousakis, and K. Tolle. The ICS-FORTH RDFSuite: Managing Voluminous RDF Description Bases. In 2nd Inter. Workshop on the Semantic Web, pages 1--13, 2001.]]
4. D. Brickley and R.V. Guha. Resource Description Framework (RDF) Schema Specification 1.0, W3C Candidate Recommendation, 2000.]]
5. Y. Caseau. Efficient handling of multiple inheritance hierarchies. In OOPSLA'93, 1993.]]
6. Online Computer Library Center. Dewey decimal classification. Availiable at www.oclc.org/dewey/.]]
7. S.-Y. Chien, Z. Vagena, D. Zhang, V. J. Tsotras, and C. Zaniolo. Efficient structural joins on indexed xml documents. In Proc. of the Inter. Conf. On Very Large Data Bases (VLDB'02), 2002.]]
8. E. Cohen, H. Kaplan, and T. Milo. Labeling dynamic xml trees. In Proc. of the Twenty-first Symposium on Principles of Database Systems (PODS'02), 2002.]]
9. B. Cooper, N. Sample, M. J. Franklin, G. R. Hjaltason, and M. Shadmon. A fast index for semistructured data. In Proc. of the Inter. Conf. On Very Large Data Bases (VLDB'01), 2001.]]
10. P. F. Dietz. Maintaining order in a linked list. In Proc. of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC'82), pages 122--127, 1982.]]
11. P. F. Dietz and D. D. Sleator. Two algorithms for maintaining order in a list. In Proc. of the Sixteen Annual ACM Symposium on Theory of Computing (STOC'87), pages 365--372, 1987.]]
12. C. Gavoille and D. Peleg. Compact and localized distributed data structures. Journal of Distributed Computing, Special Issue for the Twenty Years of Distributed Computing Research, 2003.]]
13. H. Kaplan, T. Milo, R. Shabo. A comparison of labeling schemes for ancestor queries. In Proc of the Thirteen Annual Symposium on Discrete Algorithms (SODA'02), 2002.]]
14. G. Karvounarakis, S. Alexaki, V. Christophides, D. Plexousakis, and M. Scholl. RQL: A Declarative Query Language for RDF. In Proc. of the Eleventh Inter. World Wide Web Conf. (WWW'02), 2002.]]
15. A. Krall, J. Vitek, and N. Horspool. Near optimal hierarchical encoding of types. In 11th European Conf. on Object Oriented Programming (ECOOP'97), 1997.]]
16. O. Lassila and R. Swick. Resource Description Framework (RDF) Model and Syntax Specification, W3C Recommendation, 1999.]]
17. Q. Li and B. Moon. Indexing and querying XML data for regular path expressions. In Proc. of 27th Inter. Conf. on Very Large Data Bases(VLDB'02), 2001.]]
18. A. Maganaraki, S. Alexaki, V. Christophides, and D. Plexousakis. Benchmarking rdf schemas for the semantic web. In Proc. of the First Inter. Semantic Web Conf. (ISWC'02), pages 132--147, 2002.]]
19. L. K. Schubert, M. A. Papalaskaris, and J. Taugher. Accelerating deductive inference: Special methods for taxonomies, colours and times. In N. Cercone and G. McCalla, editors, The Knowledge Frontier, pages 187--220. Springer-Verlag, 1987.]]
20. N. Spyratos, Y. Tzitzikas, and V. Christophides. On personalizing the catalogs of web portals. In Proc. of the Special Track on the Semantic Web at the 15th Inter. FLAIRS'02 Conf., 2002.]]
21. I. Tatarinov, S. Viglas, K. S. Beyer, J. Shanmugasundaram, E. J. Shekita, and C. Zhang. Storing and querying ordered xml using a relational database system. In In Proc. of the SIGMOD Inter. Conf. On Manag. Of Data, 2002.]]
22. A.K. Tsakalidis. Maintaining order in a generalized linked list. Acta Informatica, 21:101--112, 1984.]]
23. S. Weibel, J. Miller, and R. Daniel. Dublin Core. In OCLC/NCSA metadata workshop report, 1995.]]
24. N. Wirth. Type extensions. ACM Trans. on Progr. Languages and Systems, 10(2):204--214, 1988.]]
25. F. Yergeau. Utf-8, a transformation format of iso 10646, 1998. Availiable at utf8.com.]]
26. C. Zhang, J. F. Naughton, D. J. DeWitt, Q. Luo, and G. M. Lohman. On supporting containment queries in relational database management systems. In Proc. of the SIGMOD Inter. Conf. On Manag. Of Data, 2001.]]

Index Terms

• Information systems

  • Data management systems

    • Query languages