TOSS: an extension of TAX with ontologies and similarity queries

ABSTRACT

TAX is perhaps the best known extension of the relational algebra to handle queries to XML databases. One problem with TAX (as with many existing relational DBMSs) is that the semantics of terms in a TAX DB are not taken into account when answering queries. Thus, even though TAX answers queries with 100% precision, the recall of TAX is relatively low. Our TOSS system improves the recall of TAX via the concept of a similarity enhanced ontology (SEO). Intuitively, an ontology is a set of graphs describing relationships (such as isa, partof, etc.) between terms in a DB. An SEO also evaluates how similarities between terms (e.g. "J. Ullman", "Jeff Ullman", and "Jeffrey Ullman") affect ontologies. Finally, we show how the algebra proposed in TAX can be extended to take SEOs into account. The result is a system that provides a much higher answer quality than TAX does alone (quality is defined as the square root of the product of precision and recall). We experimentally evaluate the TOSS system on the DBLP and SIGMOD bibliographic databases and show that TOSS has acceptable performance.

REFERENCES

• 1: Shurug Al-Khalifa , Cong Yu , H. V. Jagadish, Querying structured text in an XML database, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872761]
• 2: P. Bonatti, Y. Deng, and V. S. Subrahmanian. An ontology-extended relational algebra. In Proceedings of the IEEE International Conference on Information Reuse and Integration (IEEE IRI 2003), 2003.
• 3: P. A. Bonatti , M. L. Sapino , V. S. Subrahmanian, Merging heterogenous security orderings, Journal of Computer Security, v.5 n.1, p.3-29, Jan. 1997
• 4: D. Calvanese, G. D. Giacomo, and M. Lenzerini. A framework for ontology integration. In Proc. of the First Semantic Web Working Symposium, pages 303--316, 2001.
• 5: W. W. Cohen, P. Ravikumar, and S. E. Fienberg. A comparison of string metrics for matching names and records. In Proc. of the First Workshop on Data Cleaning, Record Linkage, and Object Consolidation, 2003.
• 6: DBLP XML records. Available at http://dblp.uni-trier.de/xml/, Nov 2003.
• 7: G. A. Miller et. al. WordNet - a lexical database for english. Cognitive Science Laboratory, Princeton University. Available at http://www.cogsci.princeton.edu/~wn/w3wn.html, 2000.
• 8: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava , Keith Thompson, TAX: A Tree Algebra for XML, Revised Papers from the 8th International Workshop on Database Programming Languages, p.149-164, September 08-10, 2001
• 9: M. A. Jaro. Probabilistic linkage of large public health data files. Statistics in Medicine, 14:491--498, 1995.
• 10: David A. Maluf , Gio Wiederhold, Abstraction of Representation for Interoperation, Proceedings of the 10th International Symposium on Foundations of Intelligent Systems, p.441-455, October 15-18, 1997
• 11: Prasenjit Mitra , Gio Wiederhold , Martin L. Kersten, A Graph-Oriented Model for Articulation of Ontology Interdependencies, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.86-100, March 27-31, 2000
• 12: A. Monge and C. Elkan. The field-matching problem: algorithm and applications. In Proc. of the Second International Conference on Knowledge Discovery and Data Mining, 1996.
• 13: SIGMOD Record in XML. Available at http://www.acm.org/sigmod/record/xml/, Nov 2002.
• 14: Vladimir G. Voiskunskii, Evaluation of search results: a new approach, Journal of the American Society for Information Science, v.48 n.2, p.133-142, Feb. 1997 [doi>10.1002/(SICI)1097-4571(199702)48:2<133::AID-ASI4>3.3.CO;2-P]
• 15: Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]
• 16: Gio Wiederhold, Intelligent integration of information, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.434-437, May 25-28, 1993, Washington, D.C., United States
• 17: G. Wiederhold. Interoperation, mediation and ontologies. In International Symp. on Fifth Generation Computer Systems, Workshop on Heterogeneous Cooperative Knowledge Bases, ICOT, pages 33--48, 1994.
• 18: Apache Xindice XML database. Available at http://xml.apache.org/xindice/.

INDEX TERMS

Keywords:
XML databases, ontologies, semantic integration of heterogeneous data, similarity enhancement