Internet DRAFT - draft-apurva-ldap-query-containment

draft-apurva-ldap-query-containment





INTERNET-DRAFT                                    	Apurva Kumar 
Intended Category: Standard Track             IBM India Research Lab
Expires November 6, 2003                                 May 6, 2003  


	Schema to Support Query Containment in LDAP Directories 
	      <draft-apurva-ldap-query-containment-01.txt>


  Status of this Memo

  This document is an Internet-Draft and is in full conformance with all
  provisions of Section 10 of RFC2026.

  Internet-Drafts are working documents of the Internet Engineering Task
  Force (IETF), its areas, and its working groups.  Note that other
  groups may also distribute working documents as Internet-Drafts.
  Internet-Drafts are draft documents valid for a maximum of six months
  and may be updated, replaced, or obsoleted by other documents at any
  time.  It is inappropriate to use Internet-Drafts as reference
  material or to cite them other than as ``work in progress.''

  The list of current Internet-Drafts can be accessed at
  <http://www.ietf.org/ietf/1id-abstracts.txt>. 
  
  The list of Internet-Draft Shadow Directories can be accessed at
  <http://www.ietf.org/shadow.html>.

  Copyright 2003, The Internet Society.  All Rights Reserved.

  Please see the Copyright section near the end of this document for
  more information.
  
Abstract

  Lightweight Directory Access Protocol (LDAP) directories are being
  used at the backend of many internet and intranet applications. LDAP
  servers that cache entries which are returned as search results
  (queries) for recently evaluated search requests, can use the semantic
  information associated with these requests, to answer subsequent
  search requests which are contained in them. This document describes
  LDAP schema for representing the semantic information and for
  supporting query containment of LDAP queries.  

Conventions

  Schema definitions are provided using LDAPv3 description formats
  [RFC2252]. Definitions provided here are formatted (line wrapped) for
  readability. 

  The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
  "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
  document are to be interpreted as described in BCP 14 [RFC2119]. 


Apurva                  Expires November 6 2003			[Page 1]

	      Schema to support query containment in LDAP


1. Table of Contents

  1. Table of contents ..............................................  2
  2. Background and Motivation ......................................  3
  3. Applicability ..................................................  3
  4. Notations ......................................................  3
  5. Definitions ....................................................  3
  6. String representation of prototype filters .....................  6
  7. Query Containment Problem ......................................  6
  8. LDAP schema for representing queries and templates .............  7
     8.1 Syntaxes ...................................................  7 
     8.2 Attribute Types ............................................  7 
     8.3 Object Classes .............................................  8
  9. Support for component based query containment ..................  9
     9.1 Comparing components representing assertion values .........  9
         9.1.1 AVCAssertion syntax ..................................  9
         9.1.2 assertionValueMatch matching rule .................... 11
     9.2 queryMatch: Equality match for queries ..................... 11
     9.3 templateMatch: Equality match for templates ................ 12
     9.4 queryTemplateMatch: Matching a query with a template ....... 13
     9.5 queryContainmentMatch: Simple query containment ............ 13
     9.6 Mechanisms to support general query containment ............ 15
         9.6.1 AVCFilter syntax ..................................... 15
         9.6.2 assertionValuesFilterMatch matching rule ............. 15
     9.7 Example: Template based query containment .................. 15
   10. Query containment based on attributes comparison ............. 18
      10.1 Storing metadata ......................................... 18
      10.2 Specifying conditions for containment .................... 19
      10.3 Generating search filter for query containment ........... 19
      10.4 Limitations .............................................. 19
   11. Security Considerations ...................................... 19
   12. IANA Considerations .......................................... 20
   13. Acknowledgments .............................................. 20
   14. Author's address ............................................. 21
   15. Normative References ......................................... 21
   16. Informative References ....................................... 22
   17. Copyright Notice ............................................. 22
   Appendix A: Conditions for Filter Containment .................... 23


2. Background and Motivation
  
  A single Lightweight Directory Access Protocol (LDAP) [RFC3377]
  directory instance is typically used at the backend by several
  enterprise applications. Applications convert user requests into LDAP
  search requests and send them to a backend LDAP server for evaluation.
  The LDAP server evaluates the search request by performing database
  queries corresponding to the request. The semantic information in an
  LDAP search request is described by the LDAP filter, scope and base of
  the search and a set of attributes requested from matching entries
  [RFC2251]. 


Apurva                  Expires November 6 2003			[Page 2]

	      Schema to support query containment in LDAP

  The backend server or an intermediate (proxy) server can provide means
  to cache directory entries to improve performance, scalability and
  availability of LDAP based services. However, caching simply the data
  (entries) does not allow answering of subsequent semantically related
  queries from the cache. Thus there is a need at LDAP proxy servers
  and/or backend server to store semantic information corresponding to
  cached entries and compare it with the semantics of an incoming query
  to determine if the request can be answered from the cache. In this
  document, schema for supporting query caching and its usage by a
  directory server to determine whether an incoming query is contained
  in any of the cached queries is described. 

3. Applicability 

  While the extensions described in this document are equally applicable
  to query caching at the backend or replica directory server, it is
  expected to be more useful in a proxy cache scenario. 

  A proxy cache acts as a proxy to the backend directory by answering
  queries locally or by fetching the results from the backend server.
  The proxy cache could itself be a directory instance which stores the
  data and metadata corresponding to LDAP queries and uses them to
  answer incoming queries.  
 
  This document covers the query containment aspect of an LDAP proxy
  cache framework. Other aspects like cache replacement, prefetching,
  consistency etc. are not discussed. 

4. Notations
  
  Syntaxes are defined using Abstract Syntax Notation 1 (ASN.1). String
  representation of LDAP filters [RFC2254] and the LDAP Data Interchange
  Format (LDIF) [RFC2849] have been used in the examples in this
  document. Generic string encoding rules [GSER] have been used for
  human readable representations of ASN.1 types in examples. 

5. Definitions

  An LDAP search request [RFC2251] is also referred to as an LDAP query
  or simply query. The semantic information associated with a query is
  referred as metadata. The metadata is defined by the following: 

  - baseObject: distinguished name (DN) of the base object of the
    search.
  - scope: specifies which objects below baseObject are to be searched. 
         - base: only the base object.  
	 - singleLevel: direct descendants of base object. 
	 - wholeSubtree: base object and the entire subtree below it.  






Apurva                  Expires November 6 2003			[Page 3]

	      Schema to support query containment in LDAP


  - filter: search criteria consisting of a boolean combination of
    simple filters using standard boolean operators AND, OR, NOT.  
  - attributes: set of attributes requested from entries matching the
    search criteria. 
  
  A query can be represented using the following ASN.1 type: 

  LDAPQuery ::= SEQUENCE {
      -- baseObject and scope are either both present or both absent
      baseObject 	LDAPDN OPTIONAL, 
      scope		ENUMERATED {
               baseObject     		(0), 
	       singleLevel 		(1), 
	       wholeSubtree		(2) } OPTIONAL, 
      attributes        AttributeDescriptionSet OPTIONAL,
      filter            Filter }

  AttributeDescriptionSet ::= SET OF
      AttributeDescription
 
  LDAPDN is the string representation of distinguished name (DN) as
  described by the <distinguishedName> rule in [RFC2253].
  AttributeDescription and Filter are defined in [RFC2251].
  'baseObject', 'scope', 'attributes' and 'filter' have the same
  semantics as components with the same names in the 'SearchRequest'
  data type of [RFC2251] except that attributes is a set rather than a
  list. The 'baseObject', 'scope' and 'attributes' components can be
  absent from a query specification only when the values of these
  components are known from the context. 
  
  An LDAP template, or simply template is used to generate queries based
  on given inputs. The template consists of a prototype filter which is
  used to generate actual query filters. The prototype filter is similar
  to a filter except that one or more assertion values are not
  specified. Different filters can be generated from the prototype by
  supplying different assertion values.  
  
  The ASN.1 type representing a template is as below: 















Apurva                  Expires November 6 2003			[Page 4]

	      Schema to support query containment in LDAP


  LDAPTemplate 	::=    SEQUENCE {
      --baseObject and scope are either both present or both absent
      baseObject 	LDAPDN OPTIONAL, 
      scope		ENUMERATED {
               baseObject     		(0), 
	       singleLevel 		(1), 
	       wholeSubtree		(2) } OPTIONAL, 
      attributes        AttributeDescriptionSet OPTIONAL, 
      prototype         PrototypeFilter }
  
  PrototypeFilter ::= CHOICE {
                and             [0] SET OF PrototypeFilter,
                or              [1] SET OF PrototypeFilter,
                not             [2] PrototypeFilter,
                equalityMatch   [3] AssertionTemplate,
                substrings      [4] SubstringTemplate,
                greaterOrEqual  [5] AssertionTemplate,
                lessOrEqual     [6] AssertionTemplate,
                present         [7] AttributeDescription,
                approxMatch     [8] AssertionTemplate,
                extensibleMatch [9] MRATemplate } 

  AssertionTemplate ::= SEQUENCE {
  		attributeDesc 		AttributeDescription, 
		assertionValue		AssertionValue OPTIONAL }  

  SubstringTemplate ::= SEQUENCE {
                type            AttributeDescription,
		-- at least one must be present 
                format  SEQUENCE OF ENUMERATED {
                        initial 	   (0), 
                        any     	   (1), 
			final              (2) } }

  MRATemplate ::= SEQUENCE {
       		-- either matchingRule or type should be present
                matchingRule    MatchingRuleId OPTIONAL,
                type            AttributeDescription OPTIONAL,
                matchValue      AssertionValue OPTIONAL,
                dnAttributes    BOOLEAN DEFAULT FALSE }

  where AssertionValue, MatchingRuleId are defined in [RFC2251].
  
  In AssertionTemplate, 'assertionValue' component is optional. The
  SubstringTemplate is similar to the SubstringFilter in [RFC2251]
  except that the sequence of substring assertion values is replaced by
  a sequence of enumeration identifiers describing the format of the
  substring filters which can be generated from it. The MRATemplate is
  similar to the MatchigRuleAssertion of [RFC2251] except that the
  'matchValue' component is optional. 



Apurva                  Expires November 6 2003			[Page 5]

	      Schema to support query containment in LDAP


  A query 'belongs' to a template, or is 'derived' from a template, if
  the template (as specified by the LDAPTemplate type) could have been
  used to generate the LDAPQuery specification of the query. This means
  that the filter of the query can be generated by supplying missing
  assertion values in the prototype filter of the template, and the
  baseObject, scope and attributes components if specified in the
  template should have the same values in the query.  

6. String representation of prototype filters

  Human readable representation for prototype filters is described
  below. The representation is merely to aid discussion of examples and
  does not correspond to an encoding rule used for transferring values
  of the syntaxes defined in Section 5. Generic String Encoding Rules
  [GSER] can be used to obtain a human readable transfer syntax. 

  The string representation of a value of the PrototypeFilter type is
  obtained by representing all missing assertions with an "_" (U+005F)
  character and encoding the value according to the <filter> rule of
  [RFC2254]. To escape from this semantics any occurrence of "_"
  (U+005F) character in an assertion value must be encoded as "\5F"
  (U+005C + U+0035 + U+0046) or "\5f" (U+005C + U+0035 + U+0066).  

7. Query Containment Problem 

  The following definition of 'query containment' is used in this
  document:  

  A query Q, is said to be 'contained' in another query Q', if (i)-(iv)
  below are true: 
  (i)  The baseObject of Q should be the same or a descendant of the
    baseObject of Q'. 
  (ii) The scope of Q' is wholeSubtree
    OR
    The scope of Q' is same as the scope of Q AND Q and Q' have the same
    baseObject. 
    OR 
    The scope of Q' is singleLevel AND the scope of Q is base AND the
    baseObject of Q is a direct descendant of the baseObject of Q'. 
  (iii) The set of attributes in Q is a subset of attributes in Q'. 
  (iv)  The filter of Q is more restrictive than (or contained in) the
    filter of Q', i.e. any entry satisfying the condition specified by
    the filter of Q also satisfies the condition specified by Q'.

  A contained query is 'answerable' (from the cache) if 'attributes' in
  the conditions above is interpreted as the union of required
  attributes and the attributes appearing in the search filter of the
  query. 
 
  A query containment algorithm can be used to determine whether an
  incoming query can be answered by the set of queries stored in the


Apurva                  Expires November 6 2003			[Page 6]

	      Schema to support query containment in LDAP

  cache. 'Completeness' refers to the property of a query containment
  algorithm to answer a query if it can be answered using any other
  algorithm. Using the schema in the following sections the metadata is
  represented without any loss of information and can be used to
  implement various query containment algorithms. 
  
  Two approaches are considered for storing metadata information in the
  directory. In both the approaches entries are used to represent
  queries and templates. In the components based approach, a single
  attribute is used to represent the complete metadata corresponding to
  a query using the LDAPQuery data type. In the attribute based approach
  a set of related attributes in an entry are used to represent the
  metadata. 

  Though any query containment algorithm can be implemented using the
  metadata information, servers MUST ensure that the query containment
  algorithm implementation is correct even if it is not 'complete'.
  Apart from requiring the correctness of the algorithm, this requires
  using the correct syntaxes and matching rules while comparing values.
  Section 9 describes mechanisms to support query containment which
  ensure that the correct syntaxes and matching rules are applied.  
  
8. LDAP schema for representing queries and templates

  The schema defined in this section for representing queries and
  templates can be used by query containment algorithms as described in
  Sections 9 and 10. 

8.1 Syntaxes

8.1.1 LDAPQuery 

  ( <IANA-ASSIGNED-OID.1> DESC 'LDAPQuery' ) 
  
  The syntax is described by the ASN.1 definition of the type LDAPQuery
  in Section 5. 
  
8.1.2 LDAPTemplate 

  ( <IANA-ASSIGNED-OID.2> DESC 'LDAPTemplate' ) 

  The syntax is described by the ASN.1 definition of the type
  LDAPTemplate in Section 5. 
  
8.2. Attribute Types 
  
8.2.1 templateInfo
  
  The attribute is used to store information corresponding to an LDAP
  template. 




Apurva                  Expires November 6 2003			[Page 7]

	      Schema to support query containment in LDAP


  ( <IANA-ASSIGNED-OID.3>
    NAME 'templateInfo' 
    EQUALITY templateMatch 
    SYNTAX <IANA-ASSIGNED-OID.2>
    SINGLE-VALUE USAGE dSAOperation ) 

  The matching rule templateMatch is defined in Section 9.3 

8.2.2 queryInfo

  The attribute is used to store the meta data corresponding to an LDAP
  query. 

  ( <IANA-ASSIGNED-OID.4> 
    NAME 'queryInfo' 
    EQUALITY queryMatch 
    SYNTAX <IANA-ASSIGNED-OID.1> 
    SINGLE-VALUE USAGE dSAOperation ) 

  The matching rule queryMatch is defined in Section 9.2. 
 
8.2.3 searchTemplate 

  This attribute type can be used as a template to generate LDAP
  queries. It has a role similar to enhancedSearchGuide described in
  [RFC2256] but also allows specification of one or more assertion
  values. The attribute type has LDAPTemplate syntax. 

  ( <IANA-ASSIGNED-OID.5>
    NAME 'searchTemplate' 
    SYNTAX <IANA-ASSIGNED-OID.2> ) 
  
8.3. Object Classes

8.3.1 cachedTemplate

  The following object class is used in entries representing LDAP
  templates in the directory. 

  ( <IANA-ASSIGNED-OID.6> NAME 'cachedTemplate' SUP top STRUCTURAL 
  MUST cn MAY ( templateInfo $ searchTemplate ) ) 

8.3.2 cachedQuery 

  The following object class is used in entries representing queries
  in the directory. 

  ( <IANA-ASSIGNED-OID.7> NAME 'cachedQuery' SUP top STRUCTURAL MUST 
  cn MAY ( queryInfo $ owner ) ) 




Apurva                  Expires November 6 2003			[Page 8]

	      Schema to support query containment in LDAP


  The 'owner' attribute type is obtained by subtyping from
  'distinguishedName' attribute type. Both attribute types are defined
  in [RFC2256]. 

9. Support for component based query containment

  The component based matching rules and syntaxes described in this
  section are used to compare queries and templates represented using
  the complex ASN.1 types LDAPQuery and LDAPTemplate. 

  The following mechanisms are defined for facilitating component based
  query containment: 
  1) Equality matching of two queries. 
  2) Equality matching of two templates. 
  3) Matching of a query with a template. 
  4) To determine if each simple filter in a query is more restrictive
     than each simple filter in another query.  
  5) Comparison of specified components of a query with specified
     components of another query.  

  These mechanisms have been provided as matching rules. The matching
  rules and supporting syntaxes are described in Sections 9.1-9.6. An
  example of a template based query containment algorithm using the
  mechanisms is described in Section 9.7.  
   
9.1 Comparing components representing assertion values 

  The LDAPQuery syntax represents metadata corresponding to a query as
  described in Section 5. Query containment algorithms typically require
  comparing assertion values in a stored query with assertion values in
  another query. A component in a complex ASN.1 type which represents an
  assertion value is termed as assertion value component (AVC). Examples
  of such components appearing in complex ASN.1 type LDAPQuery are the
  'assertionValue' component in AttributeValueAssertion and the 
  'initial', 'final' and 'any' components in SubstringFilter. Such
  component values have a syntax (typically the same as the
  corresponding attribute type syntax) and should be compared using the
  matching rules defined for the syntax. For example the query filters
  (telephoneNumber=11-2618-7589) and (telephoneNumber=1126187589) have
  assertion values which are same according to the telephoneNumberMatch
  matching rule [RFC2252].  

9.1.1 AVCAssertion syntax
  
  The type AVCAssertion is used to represent an equality, ordering or
  substring assertion about a component value which represents an AVC of
  a given attribute type. The assertion ensures that the comparison uses
  the correct syntax and matching rules based on the attribute type to
  which the AVC corresponds. The attribute type should be such that its
  syntax is same as its equality matching rule syntax. 



Apurva                  Expires November 6 2003			[Page 9]

	      Schema to support query containment in LDAP


  AVCAssertion ::= SEQUENCE {
          attributeRef   [0] ComponentReference (SIZE(1..MAX)) OPTIONAL,
          assertionRef   [1] ComponentReference (SIZE(1..MAX)) OPTIONAL,
	  ruleAssertion        CHOICE { 
	       equality       [1]  EqualityRuleAssertion,
	       lessOrEqual    [2]  OrderingRuleAssertion,
	       greaterOrEqual [3]  OrderingRuleAssertion,
	       substring      [4]  SubstringRuleAssertion,
	       superstring    [5]  SubstringRuleAssertion } } 
	  
  EqualityRuleAssertion ::= SEQUENCE {
         type     ATTRIBUTE.&oid,
         rule     ATTRIBUTE.&equality-match{@type}, 
	 value    ATTRIBUTE.&Type{@type} OPTIONAL } 
  
  OrderingRuleAssertion ::= SEQUENCE {
         type     ATTRIBUTE.&oid,
         rule     ATTRIBUTE.&ordering-match{@type}, 
	 value    ATTRIBUTE.&Type{@type} OPTIONAL }

  SubstringRuleAssertion ::= SEQUENCE { 
         type     ATTRIBUTE.&oid,
         rule 	  ATTRIBUTE.&substrings-match{@type}, 
	 value    ATTRIBUTE.&Type{@type} OPTIONAL }

  where the values of information object class ATTRIBUTE of [X.501] are
  used to define LDAP attribute types. 
  
  A value of type AVCAssertion is either applied to an AVC directly or
  an AVC component in a complex ASN.1 type (e.g. LDAPQuery) referred to
  by attributeRef, using component references as described in
  [COMPONENTS]. assertionRef is used to reference a value to compare the
  component value with. This component is optional and is used only if
  the 'value' component is absent in the selected alternative of
  'ruleAssertion'.   
  
  The required type of match (equality, less than, greater than,
  substring or superstring) is indicated by the chosen alternative in
  the 'ruleAssertion' component. The chosen component specifies the OID
  of the LDAP attribute type, matching rule to be used and the value
  which the AVC has to be compared with. The assertion evaluates to
  'TRUE' if the AVC satisfies the required type of match with the value
  according to the specified matching rule. 

  The LDAP syntax corresponding to the ASN.1 type is defined as: 
  
  ( <IANA-ASSIGNED-OID.8> DESC 'AVCAssertion' )






Apurva                  Expires November 6 2003		       [Page 10]

	      Schema to support query containment in LDAP


9.1.2 assertionValueMatch matching rule
  
  The assertion represented by a value of AVCAssertion type is applied
  to a component or attribute value using the assertionValueMatch
  matching rule. The result of the matching rule is the result of
  applying the AVCAssertion to the component or attribute value. The
  rule is defined as:  
  
 
  ( <IANA-ASSIGNED-OID.9>  NAME 'assertionValueMatch' 
    SYNTAX IANA-ASSIGNED-OID.8 )

  The rule has a syntax of AVCAssertion. The 'value' component is
  required to be present in the alternative chosen in 'ruleAssertion'.
  
9.2 queryMatch: Equality match for queries

  Used to find whether an asserted value representing an LDAP query
  matches an attribute value representing another query. 
 
  The queryMatch matching rule is derived from the allComponentsMatch
  matching rule of [COMPONENTS]. The matching rule is defined as:  

  ( <IANA-ASSIGNED-OID.10>  NAME 'queryMatch' 
    SYNTAX <IANA-ASSIGNED-OID.1> )
 
  The matching rule is a "component equality matching rule" with the
  base rule as the allComponentsMatch matching rule [COMPONENTS]. The
  matching semantics is described by the following table using the
  convention described in Section 7.3 of [COMPONENTS]. 

  ASN.1 type 				        | Matching Rule
  ==============================================+================
  LDAPDN					| distinguishedNameMatch 
  Filter.AttributeValueAssertion.assertionValue | assertionValueMatch
  Filter.SubstringsAssertion.substrings.*       | assertionValueMatch
   
  The assertionValueMatch matching rule compares an AVC in the attribute
  value (say C), with a component in the assertion value (say C') by
  constructing a value of AVCAssertion as following: 
  
  (a) Component ruleAssertion: 

  (i) The identifier equalityMatch is chosen for all cases, i.e. 

  Filter.equalityMatch.assertionValue: equalityMatch
  Filter.lessOrEqual.assertionValue: equalityMatch
  Filter.greaterOrEqual.assertionValue: equalityMatch 
  Filter.substrings.substrings.*: equalityMatch 




Apurva                  Expires November 6 2003		       [Page 11]

	      Schema to support query containment in LDAP


  (ii) type: The 'type' component in the chosen alternative above is
  obtained in the following manner: 

  Filter.AttributeValueAssertion.assertionValue: 
      The type is the OID of the corresponding
      Filter.AttributeValueAssertion.attributeDesc. 

  Filter.SubstringsAssertion.substrings.*: 
      The type is the OID of the corresponding
      Filter.SubstringsAssertion.type. 

  (iii) value: C' is taken as the 'value' component.  

  (b) Component attributeRef: Not present. 
  (c) Component assertionRef: Not present. 

9.3  templateMatch: Equality match for templates 

  Used to find whether an asserted value representing an LDAP template 
  matches an attribute value representing another template. The matching
  rule is defined as: 

  ( <IANA-ASSIGNED-OID.11>  NAME 'templateMatch' 
    SYNTAX <IANA-ASSIGNED-OID.2> )
    
  The matching rule is a "component equality matching rule" with the
  base rule as the allComponentsMatch matching rule [COMPONENTS]. The
  matching semantics is described by the following table using the
  convention described in Section 7.3 of [COMPONENTS]. 

    ASN.1 type 				        | Matching Rule
  ==============================================+================
  LDAPDN					| distinguishedNameMatch 
  Filter.AssertionTemplate.assertionValue       | assertionValueMatch

  The assertionValueMatch matching rule compares an AVC in the attribute
  value (say C), with a component in the assertion value (say C') by
  constructing a value of AVCAssertion as following:

  (a) ruleAssertion component: 
    (i) The identifier equalityMatch is selected. 
    (ii) type: The OID of the attribute type in the corresponding
       Filter.AssertionTemplate.attributeDesc. 
    (iii) value: C' is taken as the 'value' component. 
  (b) Component attributeRef: Not present. 
  (c) Component assertionRef: Not present. 







Apurva                  Expires November 6 2003		       [Page 12]

	      Schema to support query containment in LDAP


9.4 queryTemplateMatch: Matching a query with a template 

  The matching rule is used to find whether an asserted value of
  LDAPQuery syntax matches an attribute value of LDAPTemplate syntax and
  is defined as: 

  ( <IANA-ASSIGNED-OID.12>  NAME 'queryTemplateMatch' 
    SYNTAX <IANA-ASSIGNED-OID.1> )
  
  To compare the two values, the assertion value is first mapped to the
  LDAPTemplate syntax by removing AVCs in the filter component when the
  corresponding component is not present in the attribute value. This
  requires converting all SubstringFilter components into corresponding
  SubstringTemplate components and AttributeValueAssertion components
  into AssertionTemplate components.

  Once the assertion value has been mapped into LDAPTemplate syntax it
  is compared to the attribute value using the templateMatch matching
  rule. 

9.5 queryContainmentMatch: Simple query containment 
  
  The rule can be used for determining whether a query is contained in
  another query belonging to the same template. It returns TRUE if
  each simple filters in the attribute value is less restrictive than
  the corresponding simple filter in the assertion value. The matching
  rule definition is as below:  

  ( <IANA-ASSIGNED-OID.13>  NAME 'queryContainmentMatch'
    SYNTAX <IANA-ASSIGNED-OID.1> )

  A 'FALSE' value is returned if either the query in the assertion is
  not contained in the cached query or it is not possible to
  conclusively determine semantic containment using the matching rule.
  The filter components of the queries should be identical except for
  the assertion values, otherwise FALSE is returned. This means that the
  matching rule can only be used for finding query containment of two
  queries generated using the same prototype filter. Moreover, it
  returns 'FALSE' if any 'not' component is encountered during
  comparison.   

  The matching rule is a "component equality matching rule" with the
  base rule as the allComponentsMatch matching rule [COMPONENTS]. The
  matching semantics is described by the following table using the
  convention described in Section 7.3 of [COMPONENTS].   








Apurva                  Expires November 6 2003		       [Page 13]

	      Schema to support query containment in LDAP


    ASN.1 type 				          |Matching Rule
  ================================================+=====================
  baseObject			          	  | (see Rule 1)
  scope					  	  | (see Rule 1) 
  attributes				  	  | (see Rule 2) 
  Filter.AttributeValueAssertion.assertionValue   | assertionValueMatch
  Filter.SubstringsAssertion.substrings.any 	  | assertionValueMatch
  Filter.MatchingRuleAssertion.matchValue 	  | assertionValueMatch
  Filter.not				  	  | (see Rule 3) 
 
  Rule: 
  1) The rule evaluates to TRUE if the following two conditions are
  satisfied: 
     i) the number of name-components [RFC2253] (say m) in the assertion
     values is greater than the number of name-components (say n) in the
     attribute value and the last n name components of the assertion
     value represent the attribute value. 
     ii) the scope in the attribute value should be wholeSubtree except
     that it can also be singleLevel if m=n+1 and the scope in the
     assertion value is baseObject. 
  2) The component represents a set. The rule returns TRUE if all the
  distinct elements in the assertion value set are present at least once
  in the attribute value set. 
  3) The rule always returns FALSE.  

  The assertionValueMatch matching rule compares an AVC in the attribute
  value (say C), with a component in the assertion value (say C') by
  constructing a value of AVCAssertion as following: 
  
  (a) Component 'ruleAssertion': 

  (i) Identifier of chosen alternative: 

  Filter.equalityMatch.assertionValue: equalityMatch
  Filter.lessOrEqual.assertionValue: greaterOrEqual 
  Filter.greaterOrEqual.assertionValue: lessOrEqual 
  Filter.substrings.substrings.any: substring 
  Filter.extensibleMatch.matchValue: equalityMatch 

  (ii) type: The 'type' component in the chosen alternative above is
  obtained in the following manner: 

      Filter.AttributeValueAssertion.assertionValue: 
        The type is the OID of the corresponding
        Filter.AttributeValueAssertion.attributeDesc. 
      Filter.SubstringsAssertion.substrings.any: 
	The type is the OID of the corresponding
	Filter.SubstringsAssertion.type. 





Apurva                  Expires November 6 2003		       [Page 14]

	      Schema to support query containment in LDAP


  (iii) value: C' is taken as the 'value' component.  

  (b) Component attributeRef: Not present. 
  (c) Component assertionRef: Not present. 

9.6 Mechanisms to support general query containment

9.6.1 AVCFilter syntax
 
  A value of the type AVCFilter described below represents an assertion
  which is a boolean combination of assertions represented by
  AVCAssertion using the boolean operators AND, OR and NOT. This allows
  expressions involving multiple AVC comparisons in two values of the
  same or different ASN.1 types. 

  AVCFilter ::= SEQUENCE {
    filter     CHOICE {
		  item  [0] AVCAssertion,
		  and   [1] SET OF AVCAssertion,
		  or    [2] SET OF AVCAssertion,
		  not   [3] AVCAssertion }, 
    assertionValue      MATCHING-RULE.&AssertionType OPTIONAL }    

  where the information object class MATCHING-RULE of [X.501] is used
  to define LDAP matching rules. 
 
  The AVCFilter applies to a value of a complex ASN.1 type. Each
  AVCAssertion must have the attributeRef components which identifies an
  AVC of the complex ASN.1 type value to which the AVCAssertion applies.
  The assertionRef references a component in another complex ASN.1 type
  value which the AVC is compared against. If assertionRef is not
  present in an AVCAssertion, then the 'value' must be present in the
  selected 'ruleAssertion' alternative.  

  The reference in the assertionRef is taken with respect to the value
  provided in the 'assertionValue' component of AVCFilter. 

  The assertion evaluates to TRUE if the boolean expression represented
  by the filter component evaluates to TRUE. 

  The LDAP syntax corresponding to AVCFilter is defined as: 

   ( <IANA-ASSIGNED-OID.14> DESC 'AVCFilter' )
   
  
9.6.2 assertionValuesFilterMatch matching rule
 
  The AVCFilter can be applied to an attribute value using the
  assertionValuesFilterMatch matching rule. The result is the same as
  applying the AVCFilter to the attribute value.   



Apurva                  Expires November 6 2003		       [Page 15]

	      Schema to support query containment in LDAP


  The matching rule is defined as: 

  ( <IANA-ASSIGNED-OID.15> NAME 'assertionValuesFilterMatch'
          SYNTAX <IANA-ASSIGNED-OID.14> )

9.7 Example: Template based query containment 
 
  Consider the following two templates (using the representation
  described in Section 6) for which queries are cached at the server
  (the baseObject, scope and attributes components have some fixed
  context specific values): 

  T1: (&(age<=_)(salary>=_))
  T2: (&(age<=_)(salary>=_)(salary<=_))

  The query Q1: (&(age<=A)(salary>=B)) belonging to template T1 is
  stored in the cache.  

  It is to be determined whether an incoming query Q2:
  (&(age<=C)(salary>=D)(salary<=E)) can be answered from the cache.  

  Let entries E1 and E2 represent Q1 and T1 in the directory. The entry
  E1 representing Q1 is as below: 

  dn: <DN of E1> 
  cn: query1
  objectClass: cachedQuery
  owner: <DN of E2> 
  queryInfo: { filter { 
	       and:{ 
		  lessOrEqual:{
		    attributeDesc "age", assertionValue <A> }, 
		  greaterOrEqual:{ 
		    attributeDesc "salary", assertionValue <B> } } }
 
  queryInfo attribute contains the metadata corresponding to Q1. The
  owner attribute points to the entry representing T1. 
  
  Let the entry E3 representing template 2 be as follows: 

  dn: <DN of E3> 
  cn: template2
  objectClass: cachedTemplate
  searchTemplate: { filter and: { 
		  equalityMatch:{ 
		   attributeDesc "owner", assertionValue <DN of E2> },
		  extensibleMatch:{
		   matchingRule <IANA-ASSIGNED-OID.15>, 
		   type "queryInfo", 
		   matchValue { <condition_value> } } } }
 


Apurva                  Expires November 6 2003		       [Page 16]

	      Schema to support query containment in LDAP


  Here the searchTemplate attribute is used as a guide to form a filter
  which can be used for query containment. The filter consists of
  logical AND of (owner=<DN of E2>) and an extensible match for the
  attribute queryInfo. The first filter restricts the search to only
  entries belonging to template T1. The <condition_value> having the
  syntax of AVCFilter represents the condition required for queries of
  template T1 to answer queries of template T2. Similar conditions for
  other templates can be expressed using multiple values for
  searchTemplate. 
 
  The conditions for the query Q1: (&(age<=A)(salary>=B)), belonging to
  template T1 to contain the query Q2: (&(age<=C)(salary>=D)(salary<=E))
  belonging to template T2 is easily seen to be (assuming E >= D):  
  (i) A >= C
  (ii) B <= D  

  Appendix A describes a general method for obtaining such conditions. 

  The <condition_value> having the syntax of AVCFilter represents the
  condition required for queries of template T1 to answer queries of
  template T2: 

     { and:{ item:{
	 attributeRef "filter.and.1.lessOrEqual.assertionValue", 
	 assertionRef "filter.and.1.lessOrEqual.assertionValue", 
	 ruleAssertion greaterOrEqual:{ 
	     type <age-oid> 
	     rule <oid-integer-ordering-match> } }, 
	      item:{ 
	 attributeRef "filter.and.2.greaterOrEqual.assertionValue", 
	 assertionRef "filter.and.2.greaterOrEqual.assertionValue", 
	 ruleAssertion lessOrEqual:{ 
	     type <salary-oid> 
	     rule <oid-integer-ordering-match> } } } }
  
  With the entries E1, E3 having attribute values as described above,
  the server performs the following steps when the query Q2 arrives: 

  1) Internal search with search filter to obtain the template entry: 
  (&(objectClass=cachedTemplate)(templateInfo:queryTemplateMatch:=<Q2>)) 

  where <Q2> is the representation of Q2 in LDAPQuery syntax. 

  This will return entry E3 corresponding to template T2. 

  2) Uses the searchTemplate attribute in E3 above, to generate a filter
  to search all queries of template T1 which can answer the query: 






Apurva                  Expires November 6 2003		       [Page 17]

	      Schema to support query containment in LDAP


	(&(owner=<DN of E2>)(objectClass=cachedQuery)
	  (queryInfo:assertionValuesFilterMatch:=
		  { <condition_value>,
		    assertionValue <Q2> }))
       
  The first and second filters restrict the search to entries
  representing queries which belong to template T1. The third filter is
  an extensible match which compares the assertion value <Q2> with
  attribute queryInfo according to <condition_value>. 

  If any entry satisfies the search condition, the query Q2 is
  answerable.  
  
10. Query containment based on attributes comparison 
 
  Query containment based on component matching described in Section 9
  requires complex syntaxes and component based matching rules to be
  implemented by the server. Some directory server implementations might
  not efficiently handle complex syntaxes and matching rules. In this
  section, means are discussed to represent metadata information using a
  set of related attributes of simpler syntaxes. 

10.1 Storing metadata

  An LDAP query filter consists of several attribute, assertion value
  pairs. Entries in a directory represent a sets of attribute, value
  pairs. If the assertion syntaxes used in the filter are same as the
  corresponding attribute syntaxes, then an entry can be used to
  represent part of the metadata corresponding to a query. 

  For each template, an object class is defined which has all attributes
  with unspecified assertion values in the prototype filter of the
  template as mandatory attributes. Each entry of this object class can
  then be used to store assertion values stored in a query belonging to
  the template. 

  For e.g., consider template T1 from the example in Section 9.7, which
  has attributes age and salary in the prototype filter without
  assertions. The object class, say OC1 corresponding to the template
  will have age and salary as mandatory attributes. The entry E1
  representing Q1 using this method will be as follows: 

    dn: <DN of E1> 
    objectClass: OC1
    age: <A>
    salary: <B>
 






Apurva                  Expires November 6 2003		       [Page 18]

	      Schema to support query containment in LDAP


10.2 Specifying conditions for containment 
 
  In component based query containment, searchTemplate attribute with
  LDAPTemplate syntax has been used to specify conditions for queries of
  a template to be contained in queries of the same or other templates.
  For attribute based query containment, the searchTemplate attribute is
  used for the same purpose, but the conditions are expressed in terms
  of attributes and thus the extensible match with an
  assertionValuesFilterMatch is not required. 
  
  Continuing with the example of Section 9.7, the searchTemplate
  attribute in entry E3 (which represents template T2) is given by: 

  searchTemplate: { filter and: { 
                     equalityMatch:{ 
		      attributeDesc "objectClass", assertionValue OC1 },
		     greaterOrEqual:{
		       attributeDesc "age" }, 
		     lessOrEqual:{
		       attributeDesc "salary" } } } 

10.3 Generating search filter for query containment

  The following search filter is used to determine whether the query Q2
  is contained or not. 

  (&(objectClass=OC1)(age>=<C>)(salary<=<D>))

  If any entry is returned, the query Q2 is answerable. 

10.4 Limitations

  The attribute based containment approach has some limitations when
  compared with the components based approach. Metadata for queries
  having search filters with an attribute type appearing in more than
  one attribute value assertions can not be represented easily and thus
  can not be used to answer queries. Moreover the operations of mapping
  an incoming query to a template, referencing the correct assertion
  values while constructing searchTemplate are not defined in a matching
  rule, hence the correct operation needs to be ensured by the server. 

11. Security Considerations

  An LDAP proxy server might have to perform authentication on behalf of
  the client if it connects to the backend server using a single
  authentication identity. In addition in such situations where client
  identity is not known to the backend server or queries are answered
  from the cache, the proxy should apply the required access control
  rules. Also the proxy should either use a synchronization mechanism to
  
  


Apurva                  Expires November 6 2003		       [Page 19]

	      Schema to support query containment in LDAP


  refresh the data corresponding to cached queries or an aging mechanism
  to detect stale queries. It should also be possible to specify
  templates which are critical in nature and are not to be cached. 
  
12. IANA Considerations

  It is requested that IANA register the LDAP descriptors used in this
  document per the following registration template: 

  Subject: Request for the LDAP Descriptor Registration 
  Descriptor (short name): see comments
  Object Identifier: IANA-ASSIGNED-OID 
  Person & email address to contact for further information: 
  	Apurva Kumar (kapurva@in.ibm.com) 
  Usage: see comments
  Specification: (I-D)
  Author/Change Controller: IESG
  Comments: 

    NAME			Type 	OID
  LDAPQuery 			  S   IANA-ASSIGNED-OID.1       
  LDAPTemplate 			  S   IANA-ASSIGNED-OID.2 
  templateInfo			  A   IANA-ASSIGNED-OID.3 
  queryInfo			  A   IANA-ASSIGNED-OID.4 
  searchTemplate                  A   IANA-ASSIGNED-OID.5 
  cachedQuery			  O   IANA-ASSIGNED-OID.6 
  cachedTemplate		  O   IANA-ASSIGNED-OID.7  
  AVCAssertion		  	  S   IANA-ASSIGNED-OID.8  
  assertionValueMatch		  MR  IANA-ASSIGNED-OID.9  
  queryMatch			  MR  IANA-ASSIGNED-OID.10 
  templateMatch			  MR  IANA-ASSIGNED-OID.11 
  queryTemplateMatch		  MR  IANA-ASSIGNED-OID.12  
  queryContainmentMatch           MR  IANA-ASSIGNED-OID.13 
  AVCFilter	  		  S   IANA-ASSIGNED-OID.14 
  assertionValuesFilterMatch      MR  IANA-ASSIGNED-OID.15

  where Type A is attribute, S is syntax, O is object class and MR is
  matching rule. 

13. Acknowledgments
  
  The author acknowledges Kurt D. Zeilenga for comments and Rajeev Gupta
  for discussions during the preparation of the draft. 










Apurva                  Expires November 6 2003		       [Page 20]

	      Schema to support query containment in LDAP


14. Author's address

  Apurva Kumar 
  IBM India Research Lab
  Block I, Indian Institute of Technology, 
  New Delhi, 110 016
  India. 

  phone - +91-11-26861100
  email - kapurva@in.ibm.com
  	
15. Normative References

  [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
	     Requirement Levels", RFC 2119, March 1997. 

  [RFC3377] Hodges, J., Morgan, R., "Lightweight Directory Access
  	     Protocol (v3): Technical Specification", RFC 3377,
	     September 2002. 
  
  [RFC2251] Wahl, M., Howes, T. and S. Kille, "Lightweight Directory
             Access Protocol (v3)", RFC 2251, December 1997.

  [RFC2252] Wahl, M., Coulbeck, A., Howes, T. and S. Kille,
             "Lightweight Directory Access Protocol (v3): Attribute
             Syntax Definitions", RFC 2252, December 1997.

  [RFC2256] Wahl, M., "A Summary of the X.500(96) User Schema for use
             with LDAPv3", RFC 2256, December 1997.

  [X.501] The Directory: Models. ITU-T Recommendation X.501, 2001.
	 
  [ASN.1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1) -
             Specification of Basic Notation", 1994.

  [COMPONENTS]  Legg, S., "LDAP & X.500 Component Matching Rules",
             INTERNET DRAFT (work in progress)
             <draft-legg-ldapext-component-matching-10.txt>, April 2003.

  [RFC2253] Wahl, M., Kille S., Howes, T., "Lightweight Directory Access
             Protocol (v3): UTF-8 String Representation of Distinguished
	     Names", December 1997. 


  








Apurva                  Expires November 6 2003		       [Page 21]

	      Schema to support query containment in LDAP

16. Informative References 

  [RFC2254] Howes, T., "The String Representation of LDAP Search
             Filters", RFC 2254, December 1997. 

  [RFC2849] Good, G., "The LDAP Data Interchange Format (LDIF) - 
             Technical Specification", RFC 2849, June 2000. 
   
  [GSER] Legg, S., "Generic Encoding Rules for ASN.1 Types", INTERNET
	     DRAFT (work in progress) <draft-legg-ldap-gser-02.txt>,
	     October 2002.  



17. Full Copyright

  Copyright 2003, The Internet Society.  All Rights Reserved.

  This document and translations of it may be copied and furnished to
  others, and derivative works that comment on or otherwise explain it
  or assist in its implementation may be prepared, copied, published and
  distributed, in whole or in part, without restriction of any kind,
  provided that the above copyright notice and this paragraph are
  included on all such copies and derivative works.  However, this
  document itself may not be modified in any way, such as by removing
  the copyright notice or references to the Internet Society or other
  Internet organizations, except as needed for the  purpose of
  developing Internet standards in which case the procedures for
  copyrights defined in the Internet Standards process must be followed,
  or as required to translate it into languages other than English.

  The limited permissions granted above are perpetual and will not be
  revoked by the Internet Society or its successors or assigns.

  This document and the information contained herein is provided on an
  "AS IS" basis and THE AUTHORS, THE INTERNET SOCIETY, AND THE INTERNET
  ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
  INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
  INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
  WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
 


 










Apurva                  Expires November 6 2003		       [Page 22]

	      Schema to support query containment in LDAP

Appendix A: Conditions for Filter Containment 

  If LDAP query filters F1 and F2 consisting of a boolean combination
  (AND, OR, NOT) of atomic filters of the form (x op val), where x is an
  LDAP attribute type, op is an operator (=, >=, <=) and val is the
  assertion value, are such that (&(F1)(!F2)) is trivially inconsistent,
  then the filter F1 is semantically contained in filter F2. 
 
  Let the attribute set {x1,x2..xn} be the union of attributes sets
  appearing in the filters F1 and F2. To be trivially inconsistent there
  should not exist any set of values {v1,v2,..vn} for attributes
  {x1,x2..xn} in their valid ranges such that the condition specified by
  (&(F1)(!F2)) is satisfied.  

  If (&(F1)(!F2)) = B1 + B2 ..Bk where Bi is a conjunct of atomic
  filters, then the condition can be written in terms of Bi as follows: 

  The query F1 is contained in F2 if for all i=1..k, Bi is trivially
  inconsistent. 
  
  Example: 
  Query Q2 of the example in Section 9.7 is contained in query Q1
   
  if (&(age<=C)(salary>=D)(salary<=E))(!((age<=A)(salary>=B))) is
  inconsistent  

  => (&(age<=C)(salary>=D)(salary<=E))(|(age>A)(salary<B)) is
  inconsistent 
  
  => (|(&(age<=C)(age>A)(salary>=D)(salary<=E))
         (&(age<=C)(salary>=D)(salary<=E)(salary<B)))
  is inconsistent 

  Let the first conjunct be B1 and the second conjunct be B2. 
  Assuming E >= D: 
  For B1 to be trivially inconsistent A >= C
  For B2 to be trivially inconsistent B <= D 

  These are the conditions required for Q2 to be contained in Q1.















Apurva                  Expires November 6 2003		       [Page 23]