X.500 Standard status
(Implementors' Guide)

X.509 Related activities

How to be involved

More Information

Tutorial section 1
X.500 General

Tutorial section 2
X.509 specific

Other PKI organizations

edit SideBar

Search

Mapping Based Searches

Mapping prior to search
Figure 1 - Mapping prior to search

In a mapping-based search certain critical attributes of the search filter are checked up against a local table. How this table is build and maintained is purely a local matter and the table is neither visible nor accessible from the outside using directory protocols. It will not be moved from one DSA to another as a result of standard shadowing. Mapping-based searches are tied to special matching rules called mapping-based matching rules.

Figure 1 indicates the basic principle of mapping-based searching. The reasons for a mapping-based search could be:

  • The user conception of the real world may be fuzzy and in several ways different from the idealised model used by the directory.
  • In some cases certain attributes in the search filter are critical in the sense that if they are not checked for uniqueness, too much useless information is returned from the search.

To further understand the concept of mapping-based searches, it useful to consider zonal matching as an example and then later generalise to other examples.

Zonal matching

Zonal matching can be applied when geographical localities as perceived by users of the directory do not correspond to the way localities are represented in a directory database. Zonal matching is especially important for a White Pages service as described in ITU-T Rec. F.510.

Real world localities

Zonal partitioning
Figure 2 - Zonal partitioning

A Real World Locality (RWL) is locality whose name is likely to be used by the user in a directory search request.

In the traditional directory information model, it is assumed that it is possible to establish a hierarchy among RWLs. A country may be divided in to a number of states or province. A state or a province may be divided up into a number of locations, which in turn may be split up into a smaller locations, etc. This model implies that locations at the same level (e.g. states or provinces) never overlap. It also assumes that lower level locations are completely contained within a single higher level location. Accordingly, locations can be view as a pure hierarchical structure that could, if wanted, be directly mapping onto the Directory Information Tree (DIT).

However, the real world is not that simple. Locations overlap and may not always form a clean hierarchical structure. There can be several reasons for that, such as:

  • Postal districts may not follow the borders of municipalities, i.e. for postal services a country has been split up in one way, while it is split up in another way for municipality administration.
  • People may often use historically related locality names when referring to their residency. Such localities may have some relationship with more official localities, but may not coincide with the borders of such localities.
  • Even when localities do not actually overlap, people living at the border of a location may for several reasons quote an adjacent neighbouring location as their home location. Also, directory users guessing on the location of a subscriber living close to a border may guess on the adjacent neighbouring location. So, even when locations do not overlap, it may anyway be necessary to assume some overlap for the purpose of directory searches.

All the above indicate that when doing a directory search partly based on localities, no locality hierarchy can be assumed. It must be taken into account that the user may enter locality information neither represented in the DIT structure nor in the individual entries. However, the user still expects such a search to succeed.

For the purpose of zonal matching a country or another major area with well defined borders can be divided up into zones in such a way that no zone goes outside any identified RWL (as seen later, even a finer granularity may be required). This is illustrated with the quite simple example in figure 2. Here in this particular example, a major area is divided up into a several in-principle non-overlapping areas, but due to the reasons above, each such contained area is expanded somewhat beyond its official border thereby overlapping other locations. Some RWLs may even extend beyond the well-defined major area (e.g. when a town crosses country or state boundaries). The figure also illustrates the principle of splitting up into zones. A RWL is comprised of several zones.

Based on this division into zones the following table can be generated:

Real World Locality

Zones

Attributes

A

1, 2, 3, 4, 9, 10, 11, 12

---

B

2, 3, 5, 6, 7, 8

---

C

9, 10, 16, 17, 18, 20

---

D

10, 11, 12, 17, 18, 19, 21, 22, 28, 29, 30

---

E

3, 4, 6, 7, 12, 13, 14, 19, 23, 25, 30, 31, 32

---

F

7, 8, 14, 15, 23, 24, 36

---

G

18, 20, 21, 26, 27, 28

---

H

27, 28, 29, 30, 31, 32, 34, 35

---

I

23, 24, 25, 32, 33, 35

---

Figure 3 - Zonal partitioning of real world localities

Figures 2 and 3 illustrate a very simple example. In the real life, there may be many thousands of locations in the table and a corresponding very high number of zones. Such locations may overlap or be imbedded in each other in any way. The zones contained within localities indirectly reflect the imbedding and overlap. A table for RWLs as in figure 3 is called a gazetteer (a geographical dictionary).

Zones only have meaning for the administrator (or any other person responsible for generating a gazetteer) and the directory machinery. The zones can therefore have arbitrary identifiers, e.g. numbers as in our example.

Generating a useful and complete gazetteer is a major effort that may take several man months.

Directory localities

A directory database may or may not contain locality information, but if it does, then it is in a more idealised form, either as entries of their own, as attributes in entries, or both. Such localities could be called directory localities (in F.510 called subscriber localities). Such possibly idealised localities can be defined as having a clear hierarchical structure, i.e. if a locality is subdivided, it contains an integral number of subordinate localities, and localities do not overlap. Such an idealised locality structure may follow closely, but not necessarily exactly, RWLs. If in the example of figure 2 such an idealised locality structure is super-imposed upon the RWL structure, it will most likely cut through some of the zones illustrated. It would then be necessary to further refine the zonal structure in such way that a zone is not crossing any locality border, neither a RWL border nor a directory locality border. This would increase the number of zones contained by an RWL, i.e. the table in figure 3 will have to be updated.

A new table similar to the table in figure 3 can then be generated for directory localities. In the following, this table is called the directory locality table.

Matching against the gazetteer

The details on how the gazetteer is build and access is a local matter. Also, how output from the gazetteer access affects the database search is completely a local matter.

Let us also assume that a search request has in its filter one or more of its non-negated filter items RWL specifications. These filter items are then matched against the locality column in the table shown in figure 3. There are now three possible outcomes of this matching:

  1. If there is exactly one hit in this matching, the corresponding set of zones is identified from the table in figure 3. Details on how these zones are used for the database search are a local matter.
  2. If there is no hit, this filter item will not evaluate to TRUE for any entry within the scope of the search (if the gazetteer is built correctly). There is therefore no reason to make a database search. The search request is then rejected with an appropriate notification.
  3. If there are several hits, i.e. the filter items match more than one entry in the gazetteer, we have a somewhat ambiguous situation, where a database search may yield too many irrelevant entries. In stead of making a database search, the matching gazetteer entries are returned to the user in a suitable form. The user can then use this information to generate a new search request that should result in exactly one hit. This situation further expanded upon in the next subsection.

Returned localities

Returned localities
Figure 4 - Returned localities

ITU-T F.510 uses the term "Returned Localities" in the situation where the locality information provided in the filter produces ambiguous results when matched against the gazetteer. Figure 4 gives an example of such a situation. The user specifies in the filter a subscriber name and a truncated location (and country=Denmark). However, the truncated location name matches several locations in Denmark (in the figure, five locations). If based on this result a database search is performed, quite a lot of "Jack Finkelstein" entries are returned. Instead, the five location names are returned to the user, which then can select one of them for the next search.

Zonal matching rules

The zonal matching is performed using special matching rules that replace the matching rule (or possible several rules) normally used for the attribute types that go into the zonal matching.

These special matching rules specify the attribute types of the search filter that are used for the matching against the gazetteer. They also specify what type of notification is to be returned if there are multiple matches against the gazetteer.

Matching rule substitution

Matching rule substitution is a major addition to and can work together with mapping-based matching. However, matching rule substitution has other important applications.

Figure 5 illustrates the principle for matching rule substitution. A filter item specifies either implicitly or explicitly a matching rule to be used for a particular attribute type. Matching rule substitution implies that this matching rule is substituted with another matching rule. This substitution is control by search-rules or by user (through search request parameters).

Matching rule mapping
Figure 5 - Matching rule mapping

Before any database search is attempted, an initial basic substation may be performed. If the database search, possibly after a basic substitution, does not yield the desired result by either producing too few or too many matched entries, then an additional substitution can be done and a new database search performed. This procedure can be repeated several times.

The above substitution technique can very usefully be combined with zonal matching. For the initial database search the default matching rules for the locality related filter items could be substituted by a zonal matching rule (base substitution) followed by the gazetteer access before the first database search. If this result in none or very few returned entries, a new substitution could be performed. This would imply including additional neighbouring zones into the search. This process could be repeated either until sufficient entries are returned or until further attempts are deemed useless. This procedure is called search relaxation.

It is also possible to specify tightening of a search. If too many entries are returned from a database search, the scope of the search can be tightened to reduce this number.

Attribute weight

When a user enters search parameters resulting in search filter items, the user may be in doubt about the accuracy of some of the parameters. As an example, a user may be sure about the entered street name and, but may have some doubt about the entered street number. The user can then reflect that uncertainty in the search request. The intention is then that the directory attempts the search with the uncertain filter item, but if it yields no result, it then attempt a new search deleting the uncertain attribute from the search filter. In F.510 terms an attribute going into such a filter item has weight of zero.

The relaxation feature can be used for that purpose. The user then specifies in the request for the attribute type that the first (and only) relaxation shall be the Null matching rule, which is a rather simple matching rule always returning TRUE for a non-negated filter item (and FALSE for a negated filter item).

Ignore if Absent

The Ignore if Absent matching rule can be used for basic substitution. If as an example, the user specifies Given Name in a search request, that filter item would not be relevant, say, for an organizational entry. Such an entry would then fail a match on just this one filter item. If that is not desirable, the Ignore if Absent matching rule could be applied. The effect of that matching rule is that if the attribute in question is present, it is attempted matched as usual, but if absent, the filter item evaluated to TRUE (if non-negated).

Page Actions

Recent Changes

Group & Page

Back Links