Home : Current Projects : Darpa Markup Language : Homework 2
 

DAML Homework 2

Introduction

This page describes the classes of queries an ontology representation should be able to express and answer. Since our dataset corresponds to a scheduling ontology, we will restrict our queries to the domain of air transportation scheduling.

In this description, we will use a small set of queries and gradually increase the level of complexity required to formulate and answer the queries. We identify four basic classes of queries ranging from straightforward static data retrieval to elaborated translation and retrieval mechanisms.

Queries

The purpose of an ontology is to provide a common, agreed upon, vocabulary for knowledge interchange among heterogeneous intelligent agents. It is possible to identify three or four levels of knowledge interchange that impose increasing complexity requirements on the language and interchange mechanisms. At the first level, all agents share the same vocabulary and only static data, currently explicitly represented in the repository, is interchanged. This is the simplest level and it is currently implemented by traditional database techniques. In these cases, the ontology represents both the logical data model that is shared by all agents, and the actual content of the information stored in the database. Queries would be formulated using the same terminology used to represent the data. Extending the language with some basic SQL-like languages capable of manipulating the markup tags would suffice. No major effort is required here since database theory should provide the retrieval mechanisms needed. Additional capabilities are needed to support general mathematical computations, manipulation of special types of data like dates and strings, and aggregation of the information retrieved. Examples this type of queries for the air transportation domain are:

1. What is the sum of oversize cargo in movement-requirements with origin in KWRI and destination in KADW that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-06-2001+23:59?
2. What is the total-fuel-capacity and fuel-burn-rate of airplane-type C141?
3. What are the destinations of movement-requirements with origin in KDOV that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-01-2001+23:59?

At a slightly higher level, the ontology should provide mechanism for deducing information not immediately available in the database but that could be easily computed from relations between the represented entity. A trivial example of this case is the capability of retrieving all the grandparents grandchildren pairs from a database that only represents parent-child relationships. In this case the query mechanism provides inference capabilities by applying static rules to the static data. Let's revisit our examples and modify them so that a certain level of inference is required:

1. What is the sum the total cargo in movement-requirements with origin in KWRI and destination in KADW that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-06-2001+23:59?
2. What is the maximum-travel-range for airplane-type C141?
3. What are the destinations of movement-requirements with origin in KDOV that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-01-2001+23:59, and that can completed before Jan-02-2000+00:00?

In the first query, we assume there is a rule that computes the value of total cargo by adding the values of properties outsize, oversize, and bulk for each movement-requirement instance. In the second case, we assume there is a rule that computes the maximum-travel-range of an airplane by dividing the explicitly represented value of property total-fuel-capacity by the value of property fuel-burn-rate. In the third case, we assume there is a rule that given an origin, a destination, and an airplane type, computes the duration of the flight. Then another rule adds the duration of the flight to the value of the property available-to-load-date to compute the earliest completion time.

A third type of queries we would like to perform are queries that still assume a common query language, but require some additional level of computation to be answered. In the previous case, static rules manipulating static data was sufficient. In this case we need more elaborated algorithmic capabilities. All agents are still communicating using the same ontology and same query language. The main difference here is that the result of the query cannot be immediately inferred from the static data represented in the database. External, more complex representations and algorithms are needed. Examples of these type of queries are requests for schedule generation and resource allocation. Still using our examples, we would have:

1. What is the earliest time the total cargo in movement-requirements with origin in KWRI and destination in KADW that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-06-2001+23:59 can be completed using only airplanes currently stationed at KWRI?
2. What is the total fuel needed for all airplanes of type C141 used to deliver cargo from KWRI to KADW during time-interval starting at Jan-01-2001+00:00 and ending at Jan-06-2001+23:59?
3. What are the feasible start-time for movement-requirements with origin in KDOV that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-01-2001+23:59?

To answer the queries above, we need to generate a schedule or plan to deliver all the pending movement requirements. Depending on the algorithms or systems used, the answer to these queries could be very different. Although one can argue that it is not the role of the ontology to provide answer to these type of questions, the querying agent usually does not know if the other agent providig the information is a database or a scheduling system. For example, when we type a web address in our web browser, we don't care if the pages we are requesting are static HTML pages sitting in a server somewhere, or are being dynamically generated by some transformation mechanism. All we care is that by typing an URL we should get a web page. The same reasoning is valid for queries to the ontology.

All the queries described so far have been restricted to the data represented by the ontology. We assumed all agents shared the same ontology. They were able to ask and answer questions using a common vocabulary that was understood and accepted by all agents. Considering that it is extremely difficult for people to agree on similar terminology to describe similar concepts, and considering the highly distributed and international nature of the web, translation mechanisms between ontologies seems to be the key element to achieve a productive level of information exchange. Going back to our first example, suppose that instead of stating the first query as:

• What is the sum of oversize cargo in movement-requirements with origin in KWRI and destination in KADW that are available-to-load during time-interval starting at Jan-01-2001+00:00 and ending at Jan-06-2001+23:59?

The agent requesting information stated the question as:

• What is the total weight of non-palletized cargo that need to be transported from McGuire AFB to Andrew AFB during the first week of January 2001?

  Desired Behavior:

  In this case, as previously, the query engine should select all instances of class Movement-Requirement from the database such that the value of the property available-to-load-date, the earliest start time of the movement, has values between Jan-01-2001 and Jan-06-2001, and the value of the property origin is KWRI, the icao code for McGuire, and the value of the property destination is KADW, the icao code for Andrew. Then the query engine should add the value of the property outsize for all selected movement-requirement instances.

  To answer this query, the engine should go through the following translation process:

  1. First it should identify that the expression "cargo that need to be transported" refer to instances of class Movement-Requirement.
  2. Translate the property name non-palletized cargo to oversize
  3. Understand that the value of the oversize property represents the weight for one individual movement requirement
  4. Translate the expression from to the property origin
  5. Translate the expression to to the property destination
  6. Identify that McGuire AFB and Andrew AFB are names of airports
  7. Translate the airport names to the corresponding ICAO codes
  8. Translate "during the first week of January 2001" to "during time-interval starting at Jan-01-2001+00:00 and ending at Jan-06-2001+23:59"
  9. Translate total to sum.

Examples of modified queries for the other two examples are:

1. What is the size of the fuel tank of mds C141?
2. What are the offload points of missions with origin in Dover that should be completed today?

The second and third case previously mentioned can obviously be combined with these fourth type of queries to generate very complex types of queries.

- Back to Top -

- Home - About Kestrel - Research Staff - Current Projects - Project Archive -
- Publications - Technology Transfer - Career Opportunities - Contact Kestrel -