Jeff Heflin's Publications


Title: An Evaluation of Knowledge Base Systems for Large OWL Datasets
Authors: Yuanbo Guo, Zhengxiang Pan and Jeff Heflin
Abstract: In this paper, we present an evaluation of four knowledge base systems (KBS) with respect to use in large OWL applications. To our knowledge, no experiment has been done with the scale of data used here. The smallest dataset used consists of 15 OWL files totaling 8MB, while the largest dataset consists of 999 files totaling 583MB. We evaluated two memory-based systems (OWLJessKB and memory-based Sesame) and two systems with persistent storage (database-based Sesame and DLDB-OWL). We describe how we have performed the evaluation and what factors we have considered in it. We show the results of the experiment and discuss the performance of each system. In particular, we have concluded that existing systems need to place a greater emphasis on scalability.
Citation: Y. Guo, Z. Pan, and J. Heflin. An Evaluation of Knowledge Base Systems for Large OWL Datasets. Third International Semantic Web Conference, Hiroshima, Japan, LNCS 3298, Spinger, 2004, pp. 274-288.
Available: From SpringerLink, with electronic subscription to LNCS


Title: A Model Theoretic Semantics for Ontology Versioning
Authors: Jeff Heflin and Zhengxiang Pan
Abstract: We show that the SemanticWeb needs a formal semantics for the various kinds of links between ontologies and other documents.We provide a model theoretic semantics that takes into account ontology extension and ontology versioning. Since the Web is the product of a diverse community, as opposed to a single agent, this semantics accommodates different viewpoints by having different entailment relations for different ontology perspectives. We discuss how this theory can be practically applied to RDF and OWL and provide a theorem that shows how to compute perspective-based entailment using existing logical reasoners. We illustrate these concepts using examples and conclude with a discussion of future work.
Citation: J. Heflin, Z. Pan. A Model Theoretic Semantics for Ontology Versioning. Third International Semantic Web Conference, Hiroshima, Japan, LNCS 3298 Springer, 2004, pp. 62-76.
Available: From SpringerLink, with electronic subscription to LNCS


Title: An Initial Investigation into Querying an Inconsistent and Untrustworthy Web
Authors: Yuanbo Guo and Jeff Heflin
Abstract: The Semantic Web is bound to be untrustworthy and inconsistent. In this paper, we present an initial approach for obtaining useful information in such an environment. In particular, we replace the question of whether an assertion is entailed by the entire Semantic Web with two other queries. The first asks if a specific statement is entailed given an identification of the trusted documents. The second asks for the document sets that entail a specific statement. We propose a mechanism for efficiently computing and representing the contexts of the statements and managing inconsistency. This system could be seen as a component in an overall trust system.
Citation: Y. Guo and J. Heflin. An Initial Investigation into Querying an Inconsistent and Untrustworthy Web. In Workshop on Trust, Security, and Reputation on the Semantic Web, ISWC 2004.
Formats: PDF (82K)


Title: Efficient Source Discovery and Service Composition for Ubiquitous Computing Environments
Authors: Abir Qasem, Jeff Heflin and Hector Muņoz-Avila
Abstract: To be truly pervasive the devices in a ubiquitous computing environment have to be able to form a "coalition" without human intervention. The Semantic Web provides the infrastructure for discovery and composition of device functionalities. AI planning has been a popular technology for automatic service discovery and composition in the Semantic Web. However, because the Web is so vast and changes so rapidly, a planning agent cannot make a closed-world assumption. This condition makes it difficult for an agent to know when it has gathered all relevant information or when additional searches may be redundant. To avoid redundancy we incorporate Local Closed World reasoning with HTN planning to compose Semantic Web services. In addition, when performing information gathering tasks on the Semantic Web, we use Local Closed World reasoning and a concept of "source relevance" to control the search process. We also describe a prototype agent that we have developed.
Citation:

A. Qasem, J. Heflin and H. Muņoz-Avila. Efficient Source Discovery and Service Composition for Ubiquitous Computing Environments. In Workshop on Semantic Web Technology for Mobile and Ubiquitous Applications, ISWC 2004.

Formats: PDF (304K)


Title: Choosing the Best Knowledge Base System for Large Semantic Web Applications
Authors: Yuanbo Guo, Zhengxiang Pan, and Jeff Heflin
Abstract: We present an evaluation of four knowledge base systems with respect to use in large Semantic Web applications. We discuss the performance of each system. In particular, we show that existing systems need to place a greater emphasis on scalability.
Citation: Y. Guo, Z. Pan, and J. Heflin. Choosing the Best Knowledge Base System for Large Semantic Web Applications. Thirteenth International World Wide Web Conference (WWW2004), pp. 302-303, 2004.
Formats: PDF (34K)


Title: DLDB: Extending Relational Databases to Support Semantic Web Queries
Authors: Zhengxiang Pan and Jeff Heflin
Abstract: We present DLDB, a knowledge base system that extends a relational database management system with additional capabilities for DAML+OIL inference. We discuss a number of database schemas that can be used to store RDF data and discuss the tradeoffs of each. Then we describe how we extend our design to support DAML+OIL entailments. The most significant aspect of our approach is the use of a description logic reasoner to precompute the subsumption hierarchy. We describe a lightweight implementation that makes use of a common RDBMS (MS Access) and the FaCT description logic reasoner. Surprisingly, this simple approach provides good results for extensional queries over a large set of DAML+OIL data that commits to a representative ontology of moderate complexity. As such, we expect such systems to be adequate for personal or small-business usage.
Citation: Z. Pan and J. Heflin. DLDB: Extending Relational Databases to Support Semantic Web Queries. Technical Report LU-CSE-04-006, Dept. of Computer Science and Engineering, Lehigh University, 2004.
Formats: PDF (95K)


Title: Integrating HTN Planning and Semantic Web Ontologies for Efficient Information Integration
Authors: Jeff Heflin and Hector Munoz-Avila
Abstract: We integrate HTN planning and Semantic Web ontologies for efficient information integration. HTNs is a hierarchical plan representation that refines high-level tasks into simpler tasks. In the context of information integration, high-level tasks indicate complex queries whereas low-level tasks indicate concrete information-gathering actions such as requests to an information source. Semantic Web ontologies allow software agents to intelligently process and integrate information in distributed and heterogeneous environments such as the world wide web. The integration of HTNs and Semantic Web ontologies allow agents to answer complex queries by processing and integrating information in such environments. We also propose to use local closed world (LCW) information to assist these agents. LCW information can be obtained by accessing sources that are described in a Semantic Web language with LCW extensions, or by executing operators that provide exhaustive information. We demonstrate how the Semantic Web language SHOE can be augmented with the ability to state LCW information.
Citation: Heflin, J. and Munoz-Avila, H. Integrating HTN Planning and Semantic Web Ontologies for Efficient Information Integration. Technical Report LU-CSE-04-002, Dept. of Computer Science and Engineering, Lehigh University. 2004.
Formats: PDF (465K)


Title: Benchmarking DAML+OIL Repositories
Authors: Yuanbo Guo, Jeff Heflin, and Zhengxiang Pan
Abstract: We present a benchmark that facilitates the evaluation of DAML+OIL repositories in a standard and systematic way. This benchmark is intended to evaluate the performance of DAML+OIL repositories with respect to extensional queries over a large data set that commits to a single realistic ontology. It consists of the ontology, customizable synthetic data, a set of test queries, and several performance metrics. Main features of the benchmark include simulated data for the university domain, a repeatable data set that can be scaled to an arbitrary size, and an approach for measuring the degree to which a repository returns complete query answers. We also show a benchmark experiment for the evaluation of DLDB, a DAML+OIL repository that extends a relational database management system with description logic inference capabilities.
Citation:

Guo, Y.; Heflin, J; and Pan, Z. Benchmarking DAML+OIL Repositories. The Semantic Web - ISWC 2003, LNCS 2870. Springer, 2003, pp. 613-627.

Formats: PDF (136K)


Title: DLDB: Extending Relational Databases to Support Semantic Web Queries
Authors: Zhengxiang Pan and Jeff Heflin
Abstract: We present DLDB, a knowledge base system that extends a relational database management system with additional capabilities for DAML+OIL inference. We discuss a number of database schemas that can be used to store RDF data and discuss the tradeoffs of each. Then we describe how we extend our design to support DAML+OIL entailments. The most significant aspect of our approach is the use of a description logic reasoner to precompute the subsumption hierarchy. We describe a lightweight implementation that makes use of a common RDBMS (MS Access) and the FaCT description logic reasoner. Surprisingly, this simple approach provides good results for extensional queries over a large set of DAML+OIL data that commits to a representa-tive ontology of moderate complexity. As such, we expect such systems to be adequate for personal or small-business usage.
Citation:

Pan, Z and Heflin, J. DLDB: Extending Relational Databases to Support Semantic Web Queries. In Workshop on Practical and Scaleable Semantic Web Systms, ISWC 2003, pp. 109-113.

Formats: PDF (50K)


Title: Semantic Web Technologies for Aerospace
Authors: Paul Kogut and Jeff Heflin
Abstract: Emerging Semantic Web technology such as the DARPA Agent Markup Language (DAML) will support advanced semantic interoperability in the next generation of aerospace architectures. The basic idea of DAML is to mark up artifacts (e.g., documents, sensors, databases, legacy software) so that software agents can interpret and reason with the information. DAML will support the representation of ontologies (which include taxonomies of terms and semantic relations) via extensions to XML. XML alone is not sufficient for agents because it provides only syntactic interoperability that depends on implicit semantic agreements. DAML is the official starting point for the Web Ontology Language, an emerging standard from the World Wide Web Consortium. This paper will cover promising aerospace applications and significant challenges for Semantic Web technologies. Potential applications include higher-level information fusion, collaboration in both operational and engineering environments and rapid systems integration. The challenges that will be discussed include the complexity of ontology development, automation of markup, semantic mismatch between current object-oriented models and Semantic Web ontologies, scalability issues related to reasoning with large knowledge bases and technology transition issues. The paper will explain ongoing research that is focused on addressing these challenges.
Citation: Kogut, P. and Heflin, J. Semantic Web Technologies for Aerospace. IEEE Aerospace Conference, March 2003, Big Sky, MT.
Formats: PDF (336K)


Title: SHOE: A Blueprint for the Semantic Web
Authors: Jeff Heflin, James Hendler, and Sean Luke
Abstract: The term Semantic Web was coined by Tim Berners-Lee to describe his proposal for "a web of meaning," as opposed to the "web of links" that currently exists on the Internet. To achieve this vision, we need to develop languages and tools that enable machine understandable web pages. The SHOE project, begun in 1995, was one of the first efforts to explore these issues. In this paper, we describe our experiences developing and using the SHOE language. We begin by describing the unique features of the World Wide Web and how they must influence potential Semantic Web languages. Then we present SHOE, a language which allows web pages to be annotated with semantics, describe its syntax and semantics, and discuss our approaches to handling the problems of interoperability in distributed environments and ontology evolution. Finally, we provide an overview of a suite of tools for the Semantic Web, and discuss the application of the language and tools to two different domains.
Citation: Heflin, J., Hendler, J., and Luke, S. SHOE: A Blueprint for the Semantic Web. In Fensel, D., Hendler, J., Lieberman, H., and Wahlster, W. (Eds.), Spinning the Semantic Web. MIT Press, Cambridge, MA, 2003.
Formats: PDF (preprint) (616K)


Title: LCW-Based Agent Planning for the Semantic Web
Authors: Jeff Heflin and Hector Munoz-Avila
Abstract: The Semantic Web has the potential to allow software agents to intelligently process and integrate the Web's wealth of information. These agents must plan how to achieve their goals in light of the information available. However, because the Web is so vast and changes so rapidly, the agent cannot make a closed-world assumption. This condition makes it difficult for an agent to know when it has gathered all relevant information or when additional searches may be redundant. We propose to use local closed world (LCW) information to assist these agents. LCW information can be obtained by accessing sources that are described in a Semantic Web language with LCW extensions, or by executing operators that provide exhaustive information. In this paper, we demonstrate how two Semantic Web languages (DAML+OIL and SHOE) can be augmented with the ability to state LCW information. We also show that DAML+OIL can represent many kinds of LCW information even without additional language features. Finally, we describe how ordered task decomposition can be used with LCW information to efficiently plan in distributed information environments.
Citation: Heflin, J. and Munoz-Avila, H. LCW-Based Agent Planning for the Semantic Web. In Ontologies and the Semantic Web. Papers from the 2002 AAAI Workshop WS-02-11. AAAI Press, Menlo Park, CA, 1998. pp. 63-70.
Formats: PDF (128K)


Title: Towards the Semantic Web: Knowledge Representation in a Dynamic, Distributed Environment
Authors: Jeff Heflin
Abstract: The World Wide Web is an information resource with virtually unlimited potential. However, this potential is relatively untapped because it is difficult for machines to process and integrate this information meaningfully. Recently, researchers have begun to explore the potential of associating web content with explicit meaning, in order to create a Semantic Web. Rather than rely on natural language processing to extract this meaning from existing documents, this approach requires authors to describe documents using a knowledge representation language.

Although knowledge representation can solve many of the Web's problems, existing research cannot be directly applied to the Semantic Web. Unlike most traditional knowledge bases, the Web is highly decentralized, changes rapidly, and contains a staggering amount of information. This thesis examines how knowledge representation must change to accommodate these factors. It presents a new method for integrating web data sources based on ontologies, where the sources explicitly commit to one or more autonomously developed ontologies. In addition to specifying the semantics of a set of terms, the ontologies can extend or revise one another. This technique permits automatic integration of sources that commit to ontologies with a common descendant, and when appropriate, of sources that commit to different versions of the same ontology.

The potential of the Semantic Web is demonstrated using SHOE, a prototype ontology language for the Web. SHOE is used to develop extensible shared ontologies and create assertions that commit to particular ontologies. SHOE can be reduced to datalog, allowing it to scale to the extent allowed by the optimized algorithms developed for deductive databases. To demonstrate the feasibility of the SHOE approach, we describe a basic architecture for a SHOE system and a suite of general purpose tools that allow SHOE to be created, discovered, and queried. Additionally, we examine the potential uses and difficulties associated with the SHOE approach by applying it to two problems in different domains.

Citation: Heflin, J. Towards the Semantic Web: Knowledge Representation in a Dynamic, Distributed Environment. Ph.D. Thesis, University of Maryland, College Park. 2001.
Formats: This dissertation is available in two versions: the official version follows the formatting conventions of the University of Maryland and is identical to the original dissertation. The reformatted version uses single-line spacing and smaller margins to reduce the number of pages of the document.

Official - Compressed Postscript (504K)
Official - PDF (976K)
Reformatted - Compressed Postscript (512K)
Reformatted - PDF (928K)


Title: A Portrait of the Semantic Web in Action
Authors: Jeff Heflin and James Hendler
Abstract: Without semantically enriched content, the Web cannot reach its full potential. The authors discuss tools and techniques for generating and processing such content, thus setting a foundation upon which to build the Semantic Web. In particular, they put a Semantic Web language through its paces and try to answer questions about how people can use it, such as, How do authors generate semantic descriptions? How do agents discover these descriptions? How can agents integrate information from different sites? How can users query the Semantic Web? The authors present a system that addresses these questions and describe tools that help users interact with the Semantic Web. They motivate the design of their system with a specific application: semantic markup for computer science.
Citation: Heflin, J. and Hendler, J. A Portrait of the Semantic Web in Action. IEEE Intelligent Systems, 16(2):54-59, 2001.
Available: From IEEE Intelligent Systems, with electronic subscription


Title: Semantic Interoperability on the Web
Authors: Jeff Heflin and James Hendler
Abstract: XML will have a profound impact on the way data is exchanged on the Internet. An important feature of this language is the separation of content from presentation, which makes it easier to select and/or reformat the data. However, due to the likelihood of numerous industry and domain specific DTDs, those who wish to integrate information will still be faced with the problem of semantic interoperability. In this paper we discuss why this is not solved by XML, and then discuss why the Resource Description Framework is only a partial solution. We then present the SHOE language, which we feel has many of the features necessary to enable a semantic web, describe an existing set of tools that make it easy to use the language.
Citation: Heflin, J. and Hendler, J. Semantic Interoperability on the Web. In Proceedings of Extreme Markup Languages 2000. Graphic Communications Association, 2000. pp. 111-120.
Formats: Compressed Postscript (91K)
PDF (89K)


Title: Dynamic Ontologies on the Web
Authors: Jeff Heflin and James Hendler
Abstract: We discuss the problems associated with managing ontologies in distributed environments such as the Web. The Web poses unique problems for the use of ontologies because of the rapid evolution and autonomy of web sites. We present SHOE, a web-based knowledge representation language that supports multiple versions of ontologies. We describe SHOE in the terms of a logic that separates data from ontologies and allows ontologies to provide different perspectives on the data. We then discuss the features of SHOE that address ontology versioning, the effects of ontology revision on SHOE web pages, and methods for implementing ontology integration using SHOE's extension and version mechanisms.
Citation: Heflin, J. and Hendler, J. Dynamic Ontologies on the Web. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000). AAAI/MIT Press, Menlo Park, CA, 2000. pp. 443-449.
Formats: Compressed Postscript (62K)
PDF (62K)


Title: Searching the Web with SHOE
Authors: Jeff Heflin and James Hendler
Abstract: Although search engine technology has improved in recent years, there are still many types of searches that return unsatisfactory results. This situation can be greatly improved if web pages use a semantic markup language to describe their content. We have developed SHOE, a language for this purpose, and in this paper describe a scenario for how the language could be used by search engines of the future. A major challenge to this system is designing a query tool that can exploit the power of a knowledge base while still being simple enough for the casual user. We present the SHOE Search tool, which allows the user to specify a context for his or her query, and then uses the context to help the user build a query by example.
Citation: Heflin, J. and Hendler, J. Searching the Web with SHOE. In Artificial Intelligence for Web Search. Papers from the AAAI Workshop. WS-00-01. AAAI Press, Menlo Park, CA, 2000. pp. 35-40.
Formats: Compressed Postscript (70K)
PDF (60K)


Title: SHOE: A Knowledge Representation Language for Internet Applications
Authors: Jeff Heflin, James Hendler, and Sean Luke
Abstract: It is our contention that the World Wide Web poses challenges to knowledge representation systems that fundamentally change the way we should design KR languages. In this paper, we describe the Simple HTML Ontology Extensions (SHOE), a KR language which allows web pages to be annotated with semantics. We present a formalism for the language and discuss the features which make it well suited for the Web. We describe the syntax and semantics of this language, and discuss the differences from traditional KR systems that make it more suited to modern web applications. We also describe some generic tools for using the language and demonstrate its capabilities by describing two prototype systems that use it. We also discuss some future tools currently being developed for the language. The language, tools, and details of the applications are all available on the World Wide Web at http://www.cs.umd.edu/projects/plus/SHOE.
Citation: Heflin, J., Hendler, J., and Luke, S. SHOE: A Knowledge Representation Language for Internet Applications. Technical Report CS-TR-4078 (UMIACS TR-99-71), Dept. of Computer Science, University of Maryland at College Park. 1999.
Formats: Compressed Postscript (152K)
PDF (384K)


Title: Coping with Changing Ontologies in a Distributed Environment
Authors: Jeff Heflin, James Hendler, and Sean Luke
Abstract: We discuss the problems associated with versioning ontologies in distributed environments. This is an important issue because ontologies can be of great use in structuring and querying internet information, but many of the Internet's characteristics, such as distributed ownership, rapid evolution, and heterogeneity, make ontology management difficult. We present a scheme for classifying ontology revisions based upon the effect these changes would have on the data sources that reference the ontology. We also discuss how to manage these changes, especially when they are the result of integrating ontologies. Finally, we describe the simple elements of SHOE, a web-based knowledge representation language, that allow us to revise shared ontologies while maintaining consistency with web pages that already reference them.
Citation: Heflin, J., Hendler, J., and Luke, S. Coping with Changing Ontologies in a Distributed Environment. Ontology Management. Papers from the AAAI Workshop. WS-99-13. AAAI Press, 1999. pp. 74-79.
Formats: Compressed Postscript (440K)
PDF (67K)


Title: Applying Ontology to the Web: A Case Study
Authors: Jeff Heflin, James Hendler, and Sean Luke
Abstract: This paper describes the use of Simple HTML Ontology Extensions (SHOE) in a real world internet application. SHOE allows authors to add semantic content to web pages and to relate this content to common ontologies that provide contextual information about the domain. Using this information, query systems can provide more accurate responses than are possible with the search engines available on the Web. We have applied these techniques to the domain of Transmissible Spongiform Encephalopathies (TSEs), a class of diseases that include "Mad Cow Disease". We discuss our experiences and provide lessons learned from the process.
Citation: Heflin, J., Hendler, J., and Luke, S. Applying Ontology to the Web: A Case Study. In: J. Mira, J. Sanchez-Andres (Eds.), International Work-Conference on Artificial and Natural Neural Networks, IWANN'99. Proceedings, Volume II. Springer, Berlin, 1999. pp. 715-724.
Formats: Compressed Postscript (264K)
PDF (91K)


Title: Reading Between the Lines: Using SHOE to Discover Implicit Knowledge from the Web
Authors: Jeff Heflin, James Hendler, and Sean Luke
Abstract: This paper describes how SHOE, a set of Simple HTML Ontological Extensions, can be used to discover implicit knowledge from the World-Wide Wide Web (WWW). SHOE allows authors to annotate their pages with ontology-based knowledge about page contents. In previous papers, we discussed how the semantic knowledge provided by SHOE allows users to issue queries that are much more sophisticated than keyword search techniques, including queries that require retrieval of information from many sources. Here, we expand upon this idea by describing how SHOE's ontologies allow agents to understand more than what is explicitly stated in Web pages through the use of context, inheritance and inference. We use examples to illustrate the usefulness of these features to Web agents and query engines.
Citation: Heflin, J., Hendler, J., and Luke, S. Reading Between the Lines: Using SHOE to Discover Implicit Knowledge from the Web. In AI and Information Integration. Papers from the 1998 Workshop. WS-98-14. AAAI Press, 1998. pp. 51-57.
Formats: Compressed Postscript (224K)