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 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 . The list of Internet-Draft Shadow Directories can be accessed at . 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 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 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 ( DESC 'LDAPQuery' ) The syntax is described by the ASN.1 definition of the type LDAPQuery in Section 5. 8.1.2 LDAPTemplate ( 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 ( NAME 'templateInfo' EQUALITY templateMatch SYNTAX 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. ( NAME 'queryInfo' EQUALITY queryMatch SYNTAX 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. ( NAME 'searchTemplate' SYNTAX ) 8.3. Object Classes 8.3.1 cachedTemplate The following object class is used in entries representing LDAP templates in the directory. ( 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. ( 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: ( 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: ( 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: ( NAME 'queryMatch' SYNTAX ) 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: ( NAME 'templateMatch' SYNTAX ) 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: ( NAME 'queryTemplateMatch' SYNTAX ) 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: ( NAME 'queryContainmentMatch' SYNTAX ) 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: ( 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: ( NAME 'assertionValuesFilterMatch' SYNTAX ) 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: cn: query1 objectClass: cachedQuery owner: queryInfo: { filter { and:{ lessOrEqual:{ attributeDesc "age", assertionValue }, greaterOrEqual:{ attributeDesc "salary", assertionValue } } } 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: cn: template2 objectClass: cachedTemplate searchTemplate: { filter and: { equalityMatch:{ attributeDesc "owner", assertionValue }, extensibleMatch:{ matchingRule , type "queryInfo", matchValue { } } } } 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=) and an extensible match for the attribute queryInfo. The first filter restricts the search to only entries belonging to template T1. The 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 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 rule } }, item:{ attributeRef "filter.and.2.greaterOrEqual.assertionValue", assertionRef "filter.and.2.greaterOrEqual.assertionValue", ruleAssertion lessOrEqual:{ type rule } } } } 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:=)) where 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=)(objectClass=cachedQuery) (queryInfo:assertionValuesFilterMatch:= { , assertionValue })) 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 with attribute queryInfo according to . 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: objectClass: OC1 age: salary: 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>=)(salary<=)) 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) , 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) , 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 (|(&(age<=C)(age>A)(salary>=D)(salary<=E)) (&(age<=C)(salary>=D)(salary<=E)(salary= 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]