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 , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 2: Hassan Aït-Kaci , Robert Boyer , Patrick Lincoln , Roger Nasr, Efficient implementation of lattice operations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.115-146, Jan. 1989 [doi>10.1145/59287.59293]
• 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: Yves Caseau, Efficient handling of multiple inheritance hierarchies, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.271-287, September 26-October 01, 1993, Washington, D.C., United States
• 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: Edith Cohen , Haim Kaplan , Tova Milo, Labeling dynamic XML trees, 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.543648]
• 9: 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
• 10: Paul F. Dietz, Maintaining order in a linked list, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.122-127, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802184]
• 11: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 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: Haim Kaplan , Tova Milo , Ronen Shabo, A comparison of labeling schemes for ancestor queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.954-963, January 06-08, 2002, San Francisco, California
• 14: Gregory Karvounarakis , Sofia Alexaki , Vassilis Christophides , Dimitris Plexousakis , Michel Scholl, RQL: a declarative query language for RDF, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511524]
• 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: 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: Aimilia Magkanaraki , Sofia Alexaki , Vassilis Christophides , Dimitris Plexousakis, Benchmarking RDF Schemas for the Semantic Web, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.132-146, June 09-12, 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: Nicolas Spyratos , Yannis Tzitzikas , Vassilis Christophides, On Personalizing the Catalogs of Web Portals, Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference, p.430-434, May 14-16, 2002
• 21: Igor Tatarinov , Stratis D. Viglas , Kevin Beyer , Jayavel Shanmugasundaram , Eugene Shekita , Chun Zhang, Storing and querying ordered XML using a relational database system, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564715]
• 22: Athanasios K. Tsakalidis, Maintaining order in a generalized linked list, Acta Informatica, v.21 n.1, p.101-112, May 1984 [doi>10.1007/BF00289142]
• 23: S. Weibel, J. Miller, and R. Daniel. Dublin Core. In OCLC/NCSA metadata workshop report, 1995.
• 24: N. Wirth, Type extensions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.204-214, April 1988 [doi>10.1145/42190.46167]
• 25: F. Yergeau. Utf-8, a transformation format of iso 10646, 1998. Availiable at utf8.com.
• 26: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Management, Theory