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


Subfilter Concept

Any filter whatsoever can be written as a sequence of subfilters separated by OR operators. This means that if just one subfilter matches a directory entry, then the filter as a whole also matches that entry.

A subfilter is a sequence of filter items or negated filter items that are separated by AND operators.

A filter can be converted into a set of subfilters by progressive expansion using deMorgan's rule. Consider a filter to be a tree where non-leaf nodes correspond to each and{}, or{}, not{}, and each leaf-node is a filter-item. Each arc represents an element in the and{}, or{}, not{}; in the case of not{}, there can be only one such arc.

First progress each not{} to the leaves by using the rules:

not{and{x,y,z}} is the same as or{not{x}, not{y}, not{z}}
not{or{x,y,z}} is the same as and{not{x}, not{y}, not{z}}
not{not{x}} is the same as x

leaving the nots to apply directly to the filter items.

Then reduce the tree by combining ands and ors and move the ands in the direction of the leaves by using the rules:

and{and{x,y,z}, p, q} is the same as and{x,y,z,p,q}
or{or{x,y,z}, p, q} is the same as or{ x,y,z,p,q}
and{or{x,y,z}, p, q} is the same as or{and{x,p,q}, and{y,p,q}, and{z,p,q}}
and (x,y,z} is the same as and{any ordering of x,y,z}
or (x,y,z} is the same as or{any ordering of x,y,z}
and{} is TRUE, so that or{and{},x,y,z} is always TRUE and and{and{},x,y,z} is the same as and{x,y,z}
or{} is FALSE, so that and{or{},x,y,z} is always FALSE and or{or{},x,y,z} is the same as or{x,y,z}
NOTE - The notation {x,y,z} (etc.) as used here means a set of zero, one, or more members, such as x, y, and z.

By progressive application of these rules, the filter is eventually converted to a canonical form:

or{and{p1, p2 ...}, and{q1, q2 ...} ...}

where each pi or qi is either a filter item F or a negated filter item not{F}.

Each and{p1, p2 ... } is then a subfilter of the original filter.

Page Actions

Recent Changes

Group & Page

Back Links