XT 5b65x
`G q? Proceedings of the Second International Conference on
`the Practical Application of
`Intelligent Agents and Multi-Agent Technology
`
`Conference Organisation
`The Practical Application Company
`
`Conference and ProgrammeChair
`Barry Crabtree
`
`Sponsorship Co-ordinator
`Clive Spenser
`
`21st-23rd April 1997
`Westminster Central Hall, London , UK
`
`No part of this book maybe reprinted or reproduced withoutthe written
`
`
`
`consent of the organiser and publisher.
`
`
`Email: proceedings@pap.com
`
`PAAM,P.O. Box 137, Blackpool, Lancashire, FY2 9UN, UK
`Tel: +44 (0)1253 358081, Fax: +44 (0)1253 353811
`
`|
`|
`
`ISBN 0 9525554 6 8
`-
`Published by The Practical Application Company Ltd
`
`Page | of 21
`
`GOOGLEEXHIBIT 1026
`
`GOOGLE EXHIBIT 1026
`
`Page 1 of 21
`
`

`

`Information Brokering in an Agent Architecture
`
`David Martin
`
`Hiroki Oohama
`
`Artificial Intelligence Center
`SRI International
`martin@ai.sri.com
`
`Laboratory of Information Technology
`NTT Data
`hamaGlit.rd.nttdata.co.jp
`
`Douglas Moran
`Artificial Intelligence Center
`SRI International
`moran@ai.sri.com
`
`Adam Cheyer
`Artificial Intelligence Center
`SRI International
`cheyer@ai.sri.com
`
`Abstract
`
`To date, document identification based on keyword matching strategies has been
`the basis of most efforts to provide assistance in accessing information resources on
`the Internet. However, in view of the limitations on human browsing time and the
`evolution of more capable software agents, we can expect rapid expansion in the use
`of fully queryable information sources (such as databases and knowledge bases) and
`semiqueryable sources (such as form-based query pages on the World Wide Web, and
`collections of Web pages that are structured by textual markups).
`The ability to obtain information from a wide variety of queryable and semi-
`queryable sources is a prerequisite for the success of many types of software agents.
`Providing access to these sources — whether for end users or for software agents act-
`ing on behalf of users — poses a numberof interesting challenges, many of which can
`themselves be addressed using agent-based approaches.
`This paper describes a working prototype Information Broker system, developed
`within the Open Agent Architecture framework, that provides transparent access to
`a variety of information sources, each encapsulated as an independent agent. In this
`system, a broker meta-agent provides flexible mediation services, accepting queries
`expressed in broker or source schemas, gathering and integrating all available responses
`from the relevant sources, and allowing for the addition or deletion, at runtime, of
`participating information sources. Other broker features support the use of conversions,
`normalizations, and other basic domain knowledge in queries, and persistent queries (for
`which the Broker notifies requestors of changes in information sources that could affect
`their results). Source agents implement caching and retrieval strategies that alleviate
`problems related to the long access times and unreliability of Internet sources.
`
`Page 2 of 21
`
`467
`
`Page 2 of 21
`
`

`

`1
`
`Introduction
`
`The rapid growth of the World Wide Web and other formsof Internet and intranet access,
`and the need for automated assistance in making use of these resources, are now widely
`appreciated. The most immediate need, and the one receiving the greatest attention to
`date, is in the area of document retrieval; that is, the identification of textual documents
`that are relevant to some topic of interest. The topic of interest is generally indicated by
`an expression containing keywords, and the goalof the retrieval is to locate documents from
`which a human reader can extract useful information. A number of systems — such as NTT
`Data’s InterInfo' in the commercial realm and Amalthaea [11] in the realm of agent research
`— are providing increasingly sophisticated approaches to documentretrieval.
`
`1.1 Structured and Semistructured Information Sources
`
`An equally important set of challenges, but one that has not yet become as widely recognized,
`exists in the area of structured and semistructured information sources. By structured infor-
`mation sources, we mean sources that can be queried by using well-defined, general query
`languages, such as relational databases, object-oriented databases, and knowledge bases.
`By semistructured information sources, we include a variety of sources that contain sufficient
`structure to be treated as databases, even though they do not provide the full generality and
`power of a query language. In the context of the World Wide Web, this structure is usually
`provided in one (or both) of two ways: by an informal form-based query interface or by the
`presence of HTML (HyperText Markup Language) markups and other textual markers used
`according to site-specific conventions.
`
`Werefer to a semistructured source that provides an informal form-based query interface as
`a semiqueryable source. It should be apparent that, even when such an interface is provided,
`its “query” capability usually falls far short of the power and generality of a structured
`information source. When a source provides structure by textual markers, we call that a
`semistructured textual source.
`
`An example of a semistructured source — in which both types ofstructure are present —
`begins with a Web page that allows one to ask for hotels by filling in one or more of the
`following items: a location, a hotel chain, or a class of accommodation (economy, standard,
`luxury). This page is semiqueryable, because even though it allows for the construction
`of certain simple queries, there are many others that cannot be constructed.2 The result
`of this query is a list of hypertext links to hotel pages, each of which contains the same
`basic data in more or less the same format. Each of these pages is a semistructured textual
`source of information, and each can be transformedinto a set of data records, using parsing
`techniques, given that the format is known.
`
`All product names mentioned in this document are the trademarks of their respective holders.
`For instance, one cannot ask, in a single query, for luxury hotels in Amsterdam and economy hotels in
`Paris.
`
`Page 3 of 21
`
`468
`
`Page 3 of 21
`
`

`

`1.2 The Need for Information Brokering
`
`An information brokering system is one that provides coordinated access to a heterogeneous
`collection of structured and semistructured information sources. There are three key reasons
`why structured and semistructured information sources — and thus, information brokering
`systems — will be of rapidly increasing importance in the Internet andintranet worlds. First,
`human browsing time is both limited and, at least in the workplace, extremely expensive.
`Whereas documentretrieval returns a body of text from which a human browser can extract
`some required data, data retrieval from structured and semistructured sources returns the
`required data itself. Thus, in performing tasks where the data requirements are well defined,
`there is significant economic pressure to makeuse ofstructured and semistructured sources.
`
`Second, enterprises have large investments in legacy databases, and naturally want to lever-
`age these in the context of the World Wide Web. This is especially true in light of the
`decentralization of corporate resources, and other trends in business process engineering.
`Onestraightforward way to leverage existing databases is simply to make them accessible to
`employees via Web interfaces. But the potential for leverage goes much further, when one
`considers the variety of ways in which legacy databases can be used in combination with
`other enterprise information resources, and with information from sources on the Internet.
`Onerole of information brokering systemsis to facilitate the creation and maintenance of
`applications that rely on such combinations of information sources.
`
`Third, queryable information sources are an essential requirement for the evolution of soft-
`ware agents that provide services within the context of the Internet or an intranet. By
`services, we refer not just to document retrieval, but to the full gamut of services that can
`be built around networked information. To provide a travel planning service or a stock
`tracking service, an agent must be ableto retrieve data about a specific domain, in a form
`it can make use of — which requires access to structured and semistructured information.
`(Although natural language processing technologies have made impressive advancesin recent
`years, thereis still a long way to go before a program could reliably obtain this required data
`from unstructured text.) Moreover, many agents will need to access a wide and changing
`variety of information sources (consider, for example, an agent that finds the best available
`price for some product). As new sources becomeavailable, they will need to quickly acquire
`access to those sources. Information brokering systems can providethis access in a way that
`can be reused by numerous application agents.
`
`1.3
`
`Information Brokering and Agent Technology
`
`Software agents will be very active consumersof the services provided by information bro-
`kering systems. Wealso argue that agent technology yields a promising approach to con-
`structing the providers of these services. That is, the individual information sources as well
`as the brokering component(s) can very naturally be instantiated as agents, and their efforts
`coordinated by using the mechanisms of an agent architecture.
`One other general observation may be made here regarding therelationship between infor-
`
`Page 4 of 21
`
`469
`
`Page 4 of 21
`
`

`

`mation brokering and agent technology: challenges encountered in coordinating access to
`information agents may be viewed as special cases of those encountered in coordinating the
`activities of all types of agents. Thus, many of the techniques developed to coordinate the
`satisfaction of a query by multiple agents may well be applicable to the more general problem
`of facilitating the activities of agents in completing various other types of tasks.
`
`To summarize, the role of queryable information sources will expand rapidly in the context
`of Internet and intranet resources. Their use in these contexts poses several interesting chal-
`lenges. Addressing these challenges is the focus of the Information Broker project, developed
`within the framework of the Open Agent Architecture (OAA). Following a brief discussion of
`these challenges in the next section, the remainder of this paper describes the system that
`has been developed in the initial work on this project. Section 3 provides an overview of
`the system, with background information about the OAA. Section 4 describes thesystem’s
`architecture, and subsequent sections describe its individual components.
`
`2 Challenge Areas
`
`Our focus in this work has been on providing capabilities in two areas: mediation allows
`for the transparent interoperation of heterogeneous information sources; flexible retrieval
`strategies address issues such as long access times and unreliability of Internet resources.
`
`2.1 Mediation
`
`Mediation is a process that permits a requestor to get information from a wide variety of
`sources, without having to be aware of the identities, locations, schemas, access mechanisms,
`or contents of those sources. A component that performs mediation presents a single schema
`to its requestors, accepts queries expressed in that schema, and handles all the details of
`getting the appropriate data from the relevant information sources — each of which is likely
`to operate with a different schema.
`
`The capabilities provided by a mediator may be broken down into three subareas: delegation,
`translation, and optimization. Delegation is the process of selecting the appropriate sources
`from which to satisfy each subquery of a given query. Translation of each subquery into the
`schemas of the selected sources must take place before the subqueries are sent to the sources
`~- and results returned from the sources must be translated back into the schemaof the
`original query. Optimization results in a query execution plan that obtains results from the
`selected sources as efficiently as possible, and exploits parallelism wherever possible.
`
`the problems of mediation are not unique to
`It should be noted that, in their essence,
`networked environments. Some of these problems have already been studied for some time,
`under the heading of heterogeneous databases. However, the emergence of the Internet has
`triggered a renewed interest in these problems.* This is not only due to the massive volume
`
`3Other projects currently exploring these issues are describedin [1], [5], (6], [7], [8], [12], and [13].
`
`Page 5 of 21
`
`470
`
`Page 5 of 21
`
`

`

`of data that is now becoming accessible over the Internet, but also because of new aspects
`of these problems that occur in the context of the Internet.
`
`For example, the rapid creation (or discovery) of new information sources on the Internet,
`and frequent restructuring of existing sources, make it very valuable for a mediator to be
`able to accommodate new sources without going offline for reconfiguration. The absence
`of any centralized control over information sources implies that a mediator must be able
`to accommodate considerable variation in their schemas. The overhead involved in making
`HTTP connections to a numberofdifferent sites requires that a mediator be able to plan a
`retrieval so that it requires a minimal numberofdifferent sources.
`
`2.2 Retrieval Strategies
`
`In addition to the problems of mediation, Internet and intranet environments pose a number
`of other challenges for integrated information systems. For instance, the unreliability and
`uneven quality of Web sources maycall for the exploitation of redundant or overlappingsites.
`Wide variation inthe access mechanisms of semistructured sources suggests that strategies
`are needed to insulate the mediation component from this variation.
`
`The use of semistructured textual sources on the Web also introduces a new set of time
`factors, because first, a very large number of URL (Universal Resource Locator) accesses
`may be required to process a single query, and second, parsing the text from a single site
`can itself be time consuming.
`
`Our approach to addressing these issues includes the use of caching for Web-based sources,
`and several related retrieval strategies, which may be specified by information requestors.
`The use of caching raises additional issues, such as when cache updates should take place,
`and at what level of granularity.
`
`3 The Information Broker System
`
`To explore relevant issues, we created an information brokering architecture that integrates
`elements from software agent technology, database technology, and Internet retrieval tech-
`nology. To demonstrate this approach, we constructed a prototype system, in which a Broker
`agent coordinates access to a variety of information resources in the domain oftravel.
`
`The prototype system illustrates two different ways in which the Broker agent can be used:
`
`e A direct query interface allows the user to enter specific queries about hotels, relays the
`queries to the Broker, and formats the results for the user. In the prototype system,
`this interface is provided by a Web page.
`
`e A service-providing agent insulates the user from query details, and can employ a user
`model in obtaining and evaluating the information needed for a specific task. In the
`
`Page 6 of 21
`
`47]
`
`Page 6 of 21
`
`

`

`prototype system, this is demonstrated by the Travel Planner Agent (TPA), which
`accepts some basic trip constraints from the user, obtains hotel and flight data from
`the Broker, and uses that data to formulate desirable itineraries.
`
`In both cases, the Broker obtains and integrates the requested information from several
`heterogeneous sources, each of which participates in the system as an independent agent.
`These include several Web-based sources providing hotel information, a relational database
`of flight information, a Web-based source that provides the latest available rates of currency
`exchange, and a corporate databaselisting rates for hotel chains which grant a discount.
`Broker features allow for expression of queries in broker or in source schemas, the use of
`conversions, normalizations, and other basic domain knowledge in queries, flexibility in the
`meansof retrieval, and persistent query capabilities. These features are explained in greater
`detail below.
`
`The following subsection gives a brief overview of the OAA, the framework in which the
`agents of the brokering system operate.
`
`3.1 The Open Agent Architecture
`
`The Open Agent Architecture provides a framework for integrating a society of software
`agents, each possessing a high degree of independence and autonomy, within a distributed
`environment. A collection of agents satsifies requests from users, or other agents, by acting
`cooperatively, under the direction of one or more facilitators (which are themselves agents
`of a special type).
`The system’s architecture uses a hierarchical configuration in which each application agent
`connectsas a client of a facilitator. Facilitators provide content-based message routing, global
`data management, and process coordination for their set of connected agents. Facilitators
`can, in turn, be connected as clients of other facilitators.
`
`Agents share a common communication language and a numberofbasic structural charac-
`teristics and capabilities. An agent library provides this commonfunctionality. For example,
`every agent caninstall local or remote triggers on data, events or messages; manipulate global
`data stored by facilitators; and request solutions for a set of goals, to be satisfied under a
`variety of different control strategies. In addition, the agent library provides functionality
`for parsing and translating expressions in the Interagent Communication Language, and for
`managing network communication using TCP/IP.
`The OAA’s Interagent Communication Language (ICL) is the interface language shared by
`all agents, no matter what machine they are running on or what computer language they
`are programmed in. The ICL has been designed as an extension of the Prolog programming
`language, in order to take advantage of unification and backtracking during interactions
`among agents.
`
`The OAAis described in greater detail in [3], [9], and [10].
`
`Page 7 of 21
`
`472
`
`Page 7 of 21
`
`

`

`4 System Architecture
`
`As shownin Figure 1, the central functionality of the system is provided by the Information
`Broker agent, working in close cooperation with the OAA Facilitator. The Broker accepts
`requests (queries) from either a direct query interface or a service-providing (helper) agent,
`as shown at the left of the figure. While the demonstration system includes only one of each
`type, there is no limit in principle to the number of requestors the Broker can serve, except
`for the constraints imposed by processing time and communications bandwidth.
`
`
`
`
`
`HTTP Retrieval
`Agent
`—
`
`Sa,
`
`
`
`
`WWW
`sSemi-
`structured
`
`
`Source
`
`Facilitator
`
` WWW
`
`
`Structured
`Source
`
`
`
`
`
`RDB
`Source
`
`KB
`Source
`
`cme,
`
`Broker
`
`—gouco,
`
`Multimedia
`|S ce
`
`Ne
`
`Figure 1: Information Broker system architecture
`
`The Broker delegates, translates, and relays the appropriate subqueries to the available
`source agents (shown at the right of Figure 1), and then accepts the results and reintegrates
`them for return to the requestor. Each source agent is an encapsulation, as an OAAagent,
`of some information source. Web-based source agents make use of an HTTPretrieval agent,
`which is shown at the top of the figure.
`
`In the figure, BQ (Broker Query) and BR (Broker Response) refer to items expressed in
`the broker schema, whereas SQ (Source Query) and SR (Source Response) refer to items
`expressed in a source schema — as explained in the next section. RDP abbreviates Relational
`
`Page 8 of 21
`
`473
`
`Page 8 of 21
`
`

`

`DataBase, and KB abbreviates Knowledge Base.‘
`
`5 The Broker Agent
`
`The Broker agent provides transparent access to a collection of heterogeneous information
`sources in a given domain. Transparent means that an information requestor (a query in-
`terface agent or some other agent) need not be concerned with any details regarding the
`Broker’s information sources. The Broker publishes a fixed schema, the broker schema, that
`is used in constructing queries, and this schemais all that is needed by a requestor to make
`use of the Broker’s services.
`
`Schema,here, is essentially the same as a relational database schema. From the developer’s
`point of view, equivalently, it may be thought ofas a collection of Prolog predicates.? With
`respect to the broker schema, someof these predicates are implementedlocally, at the Broker,
`whereas others are implemented remotely, at the sources.
`
`Queries submitted to the Broker are expressions in the Interagent Communication Language
`(ICL), the language of the OAA. Each query is syntactically the same as a Prolog goal,
`usually a compound goal. For an OAA developer using the Broker’s services, the ICL has two
`advantages: first, it is easily understood, and familiar to anyone who knows Prolog or the
`logical style of expressing database queries; second, it allows the developer to take advantage
`of Prolog-style unification and backtracking in expressing and processing queries.
`
`When the Broker receives a query, it uses schema mapping rules to determine which parts of
`the query should go to which sources, and then to translate each subquery into the schemas
`of those sources to which it will be sent. (This process is described in greater detail below.)
`After the responses to the subqueries are received, the Broker translates them into the broker
`schema and integrates them into a single response, which is then returned to the requestor.
`
`Thus, the Broker insulates an information requestor from the heterogeneity of schemas that
`is likely to be present in any collection of information sources. The Broker has this core
`functionality in common with heterogeneous database systems. However, the Broker goes
`further than many existing systems, in that it allows for the addition or removal of in-
`formation sources at runtime. This can include sources of which the Broker has no prior
`knowledge.
`
`To permit this dynamism in the participation of available information sources, the Broker
`makes use of capabilities provided by the OAA. When an information source agent comes
`online, it registers its presence with the Broker by calling one of the Broker’s agent interface
`procedures, broker_register.source. As one of the arguments to this procedure, the source
`agent passes to the Broker a set of schema mapping rules, which contain the knowledge that
`
`4The prototype system does not currently include knowledge base or multimedia sources.
`For this reason, we use the term predicate, where some readers with a database background might prefer
`relation. In most places in this paper, these two terms can be used interchangeably.
`
`Page 9 of 21
`,
`
`474
`
`Page 9 of 21
`
`

`

`is needed by the Broker to translate between the broker schema and the source schema.®
`
`This approach to schema mapping means that the Broker need have no prior knowledge of
`the schema of any of the participating information sources. What is required is that the
`developer of the source agent be aware of the Broker’s schema, which, as mentionedearlier,
`has been fixed and “published”. Thus, to allow for the dynamic participation of sources, an
`important part of the Broker’s knowledge originates with the sources, each of which provides
`the mappingrules for its schema.
`At the same time, because the schema mapping rules are used at the Broker, rather than
`at the source agent, it is possible to bring a source online with minimal changes to the
`original data or to the original capabilities of the source. This may be done by creating an
`agent wrapper around the original source component — an approach that is supported by
`the underlying OAAlibraries and developmenttools. |
`Source agents that need to go offline maydo soin an orderly fashion by calling another of
`the Broker’s agent interface procedures, broker-unregister_source, to inform the Broker that
`the sourceis no longer available. However,it is also importantto allow for sources that may
`die or become unavailable unexpectedly. Here again, the Broker uses mechanisms provided
`by the OAA Facilitator. To do this, the Broker installs a trigger on the Facilitator, for each
`source agent, which is set to fire whenever that source agent dies or becomes unavailable for
`any reason. The effect of the trigger is to send a notification message to the Broker, so that
`it can unregister the source and retract its schema mappingrules.
`
`5.1 Domain Specialization
`
`A Broker agent may be specialized for a given domain, by incorporating domain knowledge.
`To illustrate, our prototype Broker agent is specialized with basic knowledge relevant to
`travel, such as distances between major cities— data that is not likely to be included in
`any of the participating sources, but that is very likely to be useful in conjunction with
`the sources’ data. Questions about this domain knowledge can then be included in queries
`submitted to the Broker. For example, using the direct-query hotel interface, it is possible to
`ask about hotels that are in a given city C,or in nearbycities (cities within a certain distance
`from C). Byfilling in knowledge gaps in this way, it is possible for the Broker to provide a
`retrieval capability that is greater than the sum of the individual information sources.
`Procedures for converting and normalizing units represent another type of domain knowledge
`that is useful in a Broker. For example, in the travel domain, our prototype Broker provides
`proceduresfor converting and normalizing units of currency and the formatting of addresses,
`which vary widely from country to country. These procedurescan be used in schema mapping
`rules, to ensure that results are returned in units and formats that are appropriate for the
`current user. This alleviates the need for each information source to provide these conversions
`
`6These and other communications between the Broker and the source agents are handled through theser-
`vices of the OAA Facilitator. We illustrate this, in Figure 1, by showing the Facilitator partially surrounding
`the Broker.
`
`Page 10 of 21
`
`4715
`
`Page 10 of 21
`
`

`

`and normalizations, and thus makes it easier to prepare information sources to work with
`the Broker.
`
`5.2 Schema Mapping Rules
`
`Delegation and translation of queries by the Broker are determined by schema mappingrules,
`which are provided at runtime by each information source that connects to the Broker.
`There are several types of schema mapping rules, the most important of which is the broker
`predicate rule. A broker predicate rule, which provides a partial definition of some predicate
`in the broker schema, has the syntax of a Prolog rule, and essentially the same semantics.
`Each mapping rule takes the form
`:
`
`B(X) + 51(Z),..-, Sn(Zn)
`
`where
`
`1. B(X) is a predicate in the broker schema.
`
`2. Each of 5),...,5, may be taken from any ofthe followingsets:
`
`@ predicates in the source schema(i.e., the source providing the rule)
`e broker domain predicates
`e ICL (Interagent Communication Language) built-in predicates, including
`~— standard comparison operators such as < /2, < /2, > /2, and > /2
`— asmall set of utility predicates such as member/2 and append/2
`
`3. As in an ordinary Prolog clause, each element of the argument lists X,Z1,..., Zn, may
`be a variable or an instantiated value.
`
`and most are purely
`Broker domain predicates provide domain-specific knowledge,
`the prototype
`system,
`extensional.
`For
`example,
`in the
`travel domain of
`city_distance(City1, City2, Miles) provides a table of distances between given cities.
`
`An information source may be associated with multiple rules defining the same broker pred-
`icate, and multiple sources can define the same broker predicate.
`
`Although the bodyof the broker predicate rule is characterized as a conjunction ofpredicates,
`it should be noted that in practice, these rules, like ordinary Prolog rules, are not strictly
`limited to conjunction. Disjunction, negation (that is, Prolog-style negation as failure), and a
`few other control operators are also allowed, but for any rule body containing these, standard
`equivalences of logic may be used to find an equivalent set of conjunctive rules.
`
`Page 11 of 21
`
`a6
`
`Page 11 of 21
`
`

`

`5.3 Query Processing
`
`The Broker’s strategy in handling a query is to provide all possible answers, given its current
`schema mapping rules.
`It does this in such a way as to maintain Prolog semantics in
`performing query evaluation, and incorporates several straightforward optimizations that
`are important, considering the distributed nature of the information sources.
`
`Of these optimizations, the most important is called chunking. The goal of chunking is
`simply to identify the largest subqueries that can be sent to an information source (after
`translation, as explained below) without changing the meaning of the original query. A
`chunk may contain broker predicates that are known to besatisfiable by the source, and ICL
`built-in predicates, but not broker domain predicates.
`
`Chunking has three advantages. First, it requires that fewer communications occur be-
`tween the Broker and an information source, reducing the overhead required to establish
`and complete communications. Second, it allows the information source to make better use
`of whatever optimization capabilities it may provide. Finally, it can significantly reduce
`the amount of data returned from a source, by allowing joins and other operations to be
`performed at the source, rather than at the Broker.
`
`Whenthe Broker receives a query, it takes the following steps to produce a query execution
`plan:
`
`e Determine, for each predicate in the query that is not an ICL built-in, what set of
`sources provides solutions for that predicate.
`
`— If the predicate is a broker predicate, this is done by testing for unification of the
`predicate against the heads of the broker predicate rules.
`If it unifies with the
`heads of one or more ofthe rules associated with a given source, that source is
`placed in the set of sources for the predicate.
`~ If the predicate is a broker domain predicate, then the Brokeritself is regarded
`as the sole source of solutions.
`
`e Determine which are the largest subqueries that can be treated as chunks, and which
`sources can handle each chunk. In this process, as an optimization, ICL built-in pred-
`icates (including arithmetic comparisons) are included with chunks to be solved by
`sources, wherever possible, rather than being solved by the Broker itself.
`
`e For each chunk, rewrite it as a disjunction of translated subqueries, where each disjunct
`is the translation of the subquery for one of the sources that can handle that chunk.
`The translation of a chunk for a given source is obtained by substituting, for each
`broker predicate in the chunk, the disjunction of the bodies of the broker predicate
`rules, for that source, whose heads unify with the predicate.
`
`In the resulting query execution plan, each translated subquery is labeled with the name
`of the source by which it is to be solved. The plan is then interpreted according to Pro-
`
`Page 12 of 21
`
`477
`
`Page 12 of 21
`
`

`

`log semantics, except that each translated subquery is solved remotely, by the appropriate
`information source.
`
`5.4 Persistent Queries
`
`An extremely useful service provided by the Broker agent is the persistent query. A persistent
`query is one that the Broker initially answers in the normal way, but then remembers and
`monitors against changes in the available information sources. When an information source
`is added, removed, or updated, the Broker checks the persistent queries to see if their results
`may have been affected by the change.
`
`As mentioned in section 5, the Broker detects additions of sources by calls made to bro-
`ker_register_source, and removals by calls to broker_unregister.source, or by the firing of a
`trigger installed on the Facilitator. Updates of sources are brought to the Broker’s atten-
`tion, with an indication of the source predicates involved, by meansof triggers installed on
`the sources. In each of these cases, the Broker performs a straightforward analysis of each
`persistent query, using the schema mappingrules for the source in question, to determineif
`it may have been affected.
`
`Ifso, the Broker sendsa change notification to the user or agent that submitted the persistent
`query. For example, in the case of our direct-query interface, the result of a persistent query
`changenotification is an email message to the user whoentered the query. The email message
`informsthe user th