Query Language Issues in a Distributed Indexing Environment
Peter Valkenburg <firstname.lastname@example.org>
Dan Brickley <email@example.com>
This contribution to the W3C's QL'98 workshop looks at some of the issues
of querying in the distributed indexing and searching environment available
on the Web (and Internet as a whole) today. We briefly discuss three
issues with respect to distributed querying of resources: schema discovery,
query language translation, and query routing. Drawing on experience,
some tentative requirements are formulated that we think need to be fullfilled
for the wide application of a new query language in a heterogeneous Web
metadata indexing environment.
The authors have been involved in the development of several distributed
indexing, cataloguing and searching projects, notably DESIRE ,
CHIC-Pilot [2,3], and ROADS .
The technologies involved in these were varied, since the goals included
the tying together of widely deployed services and protocols, and include
Z39.50/GILS, WHOIS++, LDAP, CIP, RDF and others.
Three issues have been persistent in these and other projects, when
trying to build services which `cross-search' multiple datasets, query
protocols, and search services:
It is likely that not all of these issues can be solved within the framework
of a query language only; for instance, query routing may presuppose registry
of search services that falls outside the domain of any particular query
language. However, a query language is very important as a mechanism
to locate distributed search services.
Schema Discovery and Translation
- how to find out what attribute(-sets) are supported by a search service
and how to map them
Query Language Translation
- translating an individual query to one in another language, and vice-versa
Query Routing and Forward Knowledge
- mechanisms to identify relevant search services for answering particular
We will touch upon each of the above issues in the following sections.
Schema Discovery and Translation
Schema discovery is obviously an important element of distributed search
systems. Clients need to be able to find out what attribute sets
are supported by various services that they search. In a distributed
context one can often not rely on all search services to support the same
syntax and semantics of attributes as those that a client would want to
Some important requirements related to this are:
Flexible support for both `home-grown' and standardised attribute sets
The query language should allow for schema definition using public standards
such as the Dublin Core, but also for derived schemas and wholly independent
ones. A mechanism for defining schemas and their attributes (or properties)
is part of the "Resource Description Framework (RDF) Schema Specification"
. An important element of this framework is the
universal identification of schemas, in this case through URIs. Through
assigning every attribute (property) a URI, some of the present ambiguity
in the distributed search environment may be removed.
Discovery of schemas
The discovery of schemas used by a particular service must be possible.
A client querying a service needs this to find out what appropriate attributes/properties
are supported by the service.
In many cases search services offer derived or overlapping sets of searchable
properties. To effectively cross-search these services, it should
be possible to build and query schema mapping services. As
an example, cross-searching document metadata with different sets of `subject
category' properties may be done using a service that maps one a subject
category property in one schema to one or more in another schema. Any web
query language framework should allow communities of expertise to define
their own resource description vocabularies (such as the Z39.50 attribute
sets), and to describe in a machine-processable manner how those
vocabularies relate to others.
Query Language Translation
The importance of query language translation lies in the observation that
the Web and the Internet are very heterogeneous environments. No
single indexing or searching technology can be expected to cover all indexing
and searching applications. Consequently, having to translate queries
and their results from one query language into another will remain to be
a fact of life.
A query language that has to fulfill the role of a universal front-end
to a variety of other query languages and protocols typically faces the
Finding a common core of distributed search functionality
End-users expect some types of search functionality to be available; in
most applications this encompasses at least unnested basic boolean operators
(AND, OR, AND-NOT), lstring (or prefix, or partial) matching and multiple
attribute searches (`search for any field'). On the other hand, advanced
applications may require SQL-type complex queries with variables etc.
A query language that can be applied in both cases and that also acts as
a front-end to multiple services should be amenable to defining profiles
of subsets of its functionality. Experience in profiling such as
WHOIS++/CHIC-Pilot , Z39.50/GILS 
and STARTS , indicates that it is quite important to
have the possibility of defining a reasonably universal, yet easily implementable
profile for distributed searching.
Discovery of search functionality
Related to the above, it should be possible to discover the supported search
functionality of a search service, in order to find out what queries can
be meaningfully thrown at it. In case a particular type of search
functionality is not available, a service may offer a feature that produces
a result which is nearly as good for the purpose of the client, so it can
choose to use that feature instead.
As an example of this, consider prefix (or lstring, or right-truncation)
versus substring searching. If a service only offers substring searching,
and the client wants to do a prefix search, than the client can rewrite
the query to do a substring search and filter the search results on matches
which do not contain prefixes. Another example is case sensitive
versus case-insensitive searching.
Simple search result syntax
In order to allow easy processing of search results by various clients,
a simple default result presentation format should be available. Other
representations may be available through format-negotiation, but it is
essential to be able to create simple clients which do not need to cope
with a variety of data formats when processing search results.
Query Routing and Forward Knowledge
The distributed nature of the Web presents a challenge for building usable
and intuitive resource discovery services. Deployment experience with
large-scale search services (eg. ) suggests that new
mechanisms are required for more effectively managing distibuted searches. If we want to
construct systems in which a user enters a single
search expression and has that request satisfied by a number of
searchable databases, it is essential to have "forward knowledge" about
the contents of those databases. Simply broadcasting all queries
to multiple databases will not scale.
There are several types of "forward knowledge" which may contribute
to a more scalable architecture for distributed searching. This data can
be used in a number of scenarios; a common approach is likely to be the
"referral" mechanism as used in the WHOIS++ and LDAP protocols. A
"referral" is an additional component of a search result which informs
the search client about alternative databases that could yield relevant
results. An alternative scenario involves a central index server or broker
that gathers forward knowledge for multiple databases, redirecting search
clients to the most appropriate target(s).
Forward knowledge requirements for effective query routing include the
following issues. These are largely independent of the choice of query
language, but nevertheless form a crucial component of any distributed
- Bulk metadata (eg. all the words in the database)
It is sometimes useful to extract summaries of the textual contents of a
database for use by search clients. This approach is used in
the WHOIS++ directory protocol, where a centroid for a database
contains in effect a list of all the unique terms in all the fields of
the database. By making use of such data, search clients can
perform simple checks (eg. word occurance) to avoid sending
unnecessary queries which are doomed to failure .
This principle has more recently been proposed in a more
generalised framework as the 'Common Indexing Protocol'(CIP) , which
allows for a variety of data formats to be used when characterising
the content of networked databases.
- Collection-level description
To give a search client enough information to decide whether a
query should be routed to a given database, or to construct an
appropriate interface to allow users to decide this, it is necessary to
also have some high level information about that database. The
vocabularies used to do so should not be a fixed and built in
component of the search infrastructure. Different communities will need
the flexibility to describe these resources using their own descriptive
schemas. In this respect, database characterisation is just a special
application of resource description.
- Description Service Location
- A PICS Rating Service 
offers an important facility. Given a URI, the service
will provide a machine-processable label, description or annotation for
the resource specified. RDF services will build upon the capability of
PICS; there are likely to be similar services using RDF which will
describe a resource given its URI. For these "description services" to
reach their full potential, a mechanism is needed that allows us to
discover, for any given URI, which services can offer descriptions, and
on what terms. For
example, there are an increasing number of catalogues which offer
library-like descriptions or reviews of Web resources . No single catalogue can offer complete coverage
of the Web, so there is a need for a 'forward knowledge' mechanism by
which search agents might discover services that offer 3rd-party
descriptions and metadata annotations for some specified Web resource.
Since the URI can be regarded as simply another field in the database,
this problem can be seen as a special case of the "bulk metadata" issue.
Three important issues with respect to distributed querying of resources
are: schema discovery, query language translation, and forward knowledge.
We believe it is worthwhile to investigate whether a framework for a query
language can be developed that deals with the issues raised and can serve
as a common ground in distributed searching of Web based metadata.
||Development of a European Service for Information on Research and Education
||TERENA CHIC-Pilot project, http://www.terena.nl/projects/chic-pilot/.
||P. Valkenburg, D. Beckett, M. Hamilton, S. Wilkinson, Standards
in the CHIC-Pilot Distributed Indexing Architecture, in: Computer Networks
and ISDN Systems special issue "Proceedings of the TERENA Networking Conference
||Resource Organisation and Discovery in Subject-Based Services (ROADS),
||D. Brickley, R.V. Guha, A. Layman, Resource Description Framework
(RDF) Schema Specification, W3C Working Draft 30 October 1998, http://www.w3.org/TR/WD-rdf-schema/.
||TERENA CHIC-Pilot Deliverable D3.1: Search Profile Based on
||Version 2 of Application Profile for GILS, http://www.gils.net/prof_v2.html.
||L. Gravano, K. Chang, H. Garcia-Molina, C. Lagoze, A. Paepcke,
Stanford Protocol Proposal for Internet Search and Retrieval, January 1997,
Chris Rusbridge,Towards the Hybrid Library, D-Lib Magazine, July/August
Jon Knight, Dan Brickley, Martin Hamilton, John Kirriemuir, Susan Welsh.
Cross-Searching Subject Gateways: The Query Routing and Forward Knowledge
Approach. D-Lib Magazine, January 1998.
The Architecture of the Common Indexing Protocol (CIP), Allen J.,
Mealling M., works-in-progress of the IETF Find working group.
Jim Miller (ed.), Paul Resnick, David Singer,
Rating Services and Rating Systems (and Their Machine Readable
Descriptions) Version 1.1, PICS Working Group, W3C.
Emma Worsfold, Subject gateways - fulfilling the DESIRE for knowledge,
Computer Networks and ISDN Systems (Vol 30
Numbers 12-18) 30th Sept 1998).