Subject: RE: Filter Items and Absent Attributes

From: "Ramsay, Ron" <[email-masked]>
Date: Wed, 27 Feb 2002 15:48:34 +1100

Kurt,

I'd just like to make two points.

Firstly, X.500 haven't changed the rules. I've always worked from the 2nd
edition (1993) and found no ambiguity in the specification of filter
handling. The note in the 4th edition may have been a clarification for
those who missed the power of the logic.

The second one relates to (foo=*). In X.500, this would be converted to
foo:present, which is not UNDEFINED when the attribute is not in the entry.
However, LDAPv3, or some implementations, I'm not sure which, allows the
passing of '*' in a filter. In this case, a strict application of the X.500
rules would result in UNDEFINED. (Although the X.500 rules would then
require you to find '*' in each entry!) X.500 gateways would be expected to
convert this filter to foo:present and so they would operate correctly.

Therefore, I see no problems for anyone correctly implementing the X.500
standards.

Ron.

-----Original Message-----
From: Kurt D. Zeilenga [mailto:[email-masked]]
Sent: Wednesday, 27 February 2002 6:12
To: [email-masked]
Cc: [email-masked]
Subject: Re: Filter Items and Absent Attributes

Ugh!

Logically, I understand the distinction being made in the
4th edition.  The problem I see is that most server implementation
likely don't implement it this way and it might be every difficult
for them to change.  Changing the logic of a filter evaluation
routine is likely simple enough, but changing the logic of
indexing supporting filter evaluation would likely be quite
complex.

Briefly (just to indicate why implementations might find it
difficult to implement the 4th edition semantics), if one has
an equality index where AVAs are used as key, the AVA selects
the set of entries which have that AVA is True (or may be True).
For all entries which are not in this set, the filter won't
evaluate to True.  However, the equality index doesn't say
whether it would evaluate to False or Undefined.  For this,
another index (such as for presence) must be used.

I've run into clients which desire the semantics which the
4th edition suggests.  They tend to use (&(foo=*)(foo=bar))
to achieve this as, I believe, most implementations do
not consistently evaluate (foo=bar) as described in the 4th
edition.

I note as well that the 4th edition statement is somewhat
problematic as it implies (not intentionally) that (foo=*)
should be Undefined if the entry doesn't contain the
attribute foo.  RFC 2251, of course, clarifies that (foo=*)
cannot evaluate to Undefined.

Anyways, I think the first thing we need to establish is
whether there are multiple interoperable implementations
of filters as clarified in the 4th Edition.  Ron states
he has one implementation, are there others?

Kurt

At 08:07 PM 2002-02-25, Steven Legg wrote:

>Folks,
>
>A statement that is in the 4th edition of X.511, but not in the 2nd
>edition, was recently brought to my attention. I found it surprising.
>I suspect I not the only one.
>
>In X.511:2001, Clause 7.8.2:
>
>  "An assertion" ... "evaluates to UNDEFINED if it relates to an attribute
>   value and the attribute type is not present in an" [ entry ] "against
>   which the assertion is being tested."
>
>This means, for example, that a filter item like (givenName=Bob) evaluates
>to UNDEFINED, rather than FALSE, if an entry doesn't have the givenName
>attribute. This affects how negated filter items are evaluated.
>For example, the filter (!(givenName=Bob)) only returns entries
>that have the givenName attribute, but not the givenName value "Bob".
>The entries that don't have the givenName attribute are not returned
>(giving the impression that they *do* have "Bob" as a givenName).
>
>Apparently this behaviour was the original intention in the 2nd edition
>of X.511 as well. It just wasn't explained properly.
>
>Personally, I think returning UNDEFINED instead of FALSE would be
>counter-intuitive to most users, and therefore a bad idea.
>
>Does anyone's server implementation evaluate filter items to UNDEFINED
>instead of FALSE when the attribute doesn't exist (obviously mine
>doesn't) ? The answer determines how I apply access controls to searches
>in my I-D on X.500 Basic Access Control for LDAP. The current specification
>is based on the assumption that everyone else is returning FALSE too.
>
>If that is the case then we have to decide whether we want to define
>LDAP searches to behave exactly like X.500 searches (and change our
>implementations), or explicitly specify that LDAP behaves differently,
>or influence the X.500 working group to change X.511.
>
>Regards,
>Steven

---

From: "Ramsay, Ron" <[email-masked]>
Date: Wed, 27 Feb 2002 18:01:08 +1100

Steven,

I believe the X.500 take is, can the question foo=bar be answered. If the
entry doesn't contain the attribute foo, the question cannot be answered.

The entry may not contain the attribute because, possibly, the attribute is
optional or not allowed by schema. The question cannot be answered. It is a
bit metaphysical to refer to the collection of all possible answers, the
practical approach is not to try to answer the question.

If I try to find everyone with a shoe size of 12, and Bob doesn't have a
shoe size attribute in his entry, shoudl I return Bob's entry? You say no
and I fail to be convinced. The only time 'no' is appropriate is if Bob's
shoe size has actually been entered into the directory. You can't say that
Bob doesn't have a shoe size just because it is not in his entry, you can
only say "don't know."

Ron. 

-----Original Message-----
From: Steven Legg [mailto:[email-masked]]
Sent: Wednesday, 27 February 2002 16:49
To: Ramsay, Ron
Cc: [email-masked]
Subject: RE: Filter Items and Absent Attributes

Ron,

Ramsay, Ron wrote:
> Our implementation treats it as UNDEFINED.
> 
> It is counter-intuitive only in the same way that all logic 
> assertions seem
> to defy logic. For example, an empty AND is TRUE.
> 
> The logic must be: Can I evaluate givenName=Bob if there is 
> no givenName
> attribute? The answer clearly is NO. Therefore, the assertion 
> is UNDEFINED.

What is "clear" critically depends on how one models the entry contents
and how one interprets the meaning of the assertions. I could model an
entry's contents as a set of (type, value) tuples and the assertion
(givenName=Bob) as the question "does the entry contain the tuple
(givenName, Bob)?" If the givenName attribute is absent then the
assertion is "clearly" FALSE. Such an interpretation is more in keeping
with LDAP, where no distinction is drawn between adding an attribute
and adding attribute values.

Given that there are multi-valued attributes and attribute subtyping,
we have a situation where the absence of an attribute could be
interpreted two ways:

(1) The value(s) of the attribute for the entity represented by the entry
are not known.

(2) There are no values of the attribute for the entity represented
by the entry.

For example, the absence of the telephoneNumber attribute could mean
that the telephone numbers for the entity are not known, or it could
mean that the entity doesn't have a phone (and hence no phone numbers).

The X.500 model doesn't provide us with a way to distinguish between
these two cases.

For the sake of argument, let us suppose that we can provide a mark for
each attribute type, whether the attribute is present or not, to indicate
whether the existing set of values (possibly empty) is complete (all values
are known) or incomplete (there may be other unknown values).

Case (1) above corresponds to an incomplete attribute with an empty
set of values. Case (2) corresponds to a complete attribute with an
empty set of values. There are two more cases: an incomplete attribute
with a non-empty set of values, and a complete attribute with a non-empty
set of values.

In reality, we don't have these complete/incomplete markers, so what we
are really talking about is whether we are to assume that an attribute is
complete or incomplete, in the absence of such indicators.

The 4th edition of X.511 treats an absent attribute as incomplete and a
present attribute as complete, which strikes me as inconsistent and
leads to some weird outcomes. Why should it be that if I add one known
value to a multi-valued attribute, it can suddenly mean that there are
no other unknown values ? Or the converse, if I remove one known value,
that it can suddenly mean there are now some unknown values as well. For
example, if the telephoneNumber attribute in a particular entry has the
value "+61 3 9999 9999" and I ask for:

	(!(telephoneNumber=+61 3 8888 8888))

I will get the entry back in the search result. If the telephoneNumber
value "+61 3 9999 9999" is removed, the entry is no longer returned by
the search filter, though the status of the entry with respect to the
particular value "+61 3 8888 8888" hasn't changed.

There are two consistent treatments: either assume every attribute
(whether or not it is empty/absent) is complete, or assume every
attribute is incomplete. The former implies that a filter item evaluates
to FALSE if the attribute is not present. The latter implies that filter
items evaluate to TRUE or UNDEFINED (never FALSE) for multi-valued
attributes that are present. My expectation is that most users will
unconsciously assume the former.

Both of the consistent treatments have the property that adding or
removing an unrelated value doesn't alter the outcome of a search.

Regards,
Steven

> The assertion !(givenName=Bob) is therefore also UNDEFINED. 
> This is logical.
> 
> I think you have been trying to apply heuristics. That is a 
> choice, but then
> logic cannot be your guide.
> 
> Ron.
> 
> From: Steven Legg [mailto:[email-masked]]
> Sent: Tuesday, 26 February 2002 15:08
> To: [email-masked]
> Subject: Filter Items and Absent Attributes
> 
> 
> 
> Folks,
>

---

From: "Ramsay, Ron" <[email-masked]>
Date: Wed, 27 Feb 2002 18:24:56 +1100

Kurt,

It's there in black and white! I'm gobsmacked!

Ron.

-----Original Message-----
From: Kurt D. Zeilenga [mailto:[email-masked]]
Sent: Wednesday, 27 February 2002 17:53
To: [email-masked]
Cc: Ramsay, Ron; [email-masked]
Subject: RE: Filter Items and Absent Attributes

I think a very strong case can be made that (foo=bar) should
evaluate to False if foo is known, has an equality rule,
the assertion value conforms to the assertion syntax, and
the attribute (or its subtypes) does contain the value "bar".

In particular, X.511(93), 7.8.2 details conditions for which
any assertion about values is only defined.  IMO, the 
assertion meets the conditions.  7.8.2 also states that
filter items are evaluated as attribute value assertions.
X.501(93) states:

  An AVA is:
     a) undefined, if any of the following hold:
        1) the attribute type is unknown,
        2) the attribute type has no equality matching rule,
        3) the value does not conform to the data type indicated
           by the syntax of the assertion of the attribute's
           equality matching rule;
     b) true, if the entry contains an attribute of that type,
        one of whose values matches that value;
     c) false, otherwise.

It appears that most server implementations in accordance
with this interpretation and not the 4th edition.

Kurt