TOC 
Network Working GroupH. Chu
Internet-DraftSymas Corp.
Expires: November 4, 2006May 3, 2006

Ordered Entries and Values in LDAP

draft-chu-ldap-xordered-00.txt

Status of this Memo

By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79.

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.

This Internet-Draft will expire on November 4, 2006.

Copyright Notice

Copyright © The Internet Society (2006).

Abstract

As LDAP is used more extensively for managing various kinds of data, one often encounters a need to preserve both the ordering and the content of data, despite the inherently unordered structure of entries and attribute values in the directory. This document describes a scheme to attach ordering information to attributes in a directory so that the ordering may be preserved and propagated to other LDAP applications.



Table of Contents

1.  Introduction
2.  Conventions
3.  Ordering Extension
3.1.  Overview
3.2.  Encoding
3.3.  Ordering Properties
4.  Examples
4.1.  Sample Schema
4.2.  Ordered Values
4.3.  Ordered Siblings
5.  Security Considerations
6.  Normative References
Appendix A.  IANA Considerations
§  Author's Address
§  Intellectual Property and Copyright Statements




 TOC 

1. Introduction

Information in LDAP directories is usually handled by applications in the form of ordered lists, which tends to encourage application developers to assume they are maintained as such, i.e., it is assumed that information stored in a particular order will always be retrieved and presented in that same order. The fact that directory attributes actually store sets of values, which are inherently unordered, often causes grief to users migrating their data into LDAP. Similar concerns arise over the order in which entries themselves are stored and retrieved from the directory.

This document describes a schema extension that may be used in LDAP attribute definitions to store ordering information along with the attribute values, so that the ordering can be recovered when retrieved by an LDAP client. The extension also provides automated management of this ordering information to ease manipulation of the ordered values.



 TOC 

2. Conventions

Imperative keywords defined in [RFC2119] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.) are used in this document, and carry the meanings described there.



 TOC 

3. Ordering Extension



 TOC 

3.1. Overview

The "X-ORDERED" schema extension is added to an AttributeTypeDescription to signify the use of this ordering mechanism. The extension has two variants, selected by either the 'VALUES' or 'SIBLINGS' qdstrings. In general this extension is only compatible with AttributeTypes that have a string-oriented syntax.

The "X-ORDERED 'VALUES'" extension is used with multi-valued attributes to maintain the order of multiple values of a given attribute. For example, this feature is useful for storing data such as access control rules, which must be evaluated in a specific order. If the access control information is stored in a multi-valued attribute without a means of preserving the the order of the rules, the access control rules cannot be evaluated properly. As the use of LDAP to store security policy and access control information becomes more prevalent, the necessity of this feature continues to grow.

The "X-ORDERED 'SIBLINGS'" extension is used with single-valued attributes to maintain the order of all the onelevel children of a parent entry. That is, ordering will be maintained for all the child entries whose RDNs are all of the same AttributeType. The motivation for this feature is much the same as for the 'VALUES' feature. Sometimes the information with the ordering dependency is too complex or highly structured to be conveniently stored in values of a multi-valued attribute. For example, one could store a prioritized list of servers as a set of separate entries, each entry containing separate attributes for a URL, a set of authentication credentials, and various other parameters. Using the 'SIBLINGS' feature with the attribute in the entries' RDNs would ensure that when obtaining the list of these entries, the list is returned in the intended order.



 TOC 

3.2. Encoding

Ordering information is encoded by prepending a value's ordinal index to each value, enclosed in braces. The following BNF specifies the encoding. It uses elements defined in [RFC2252] (Wahl, M., Coulbeck, A., Howes, T., and S. Kille, “Lightweight Directory Access Protocol (v3): Attribute Syntax Definitions,” December 1997.).

d = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

numericstring = 1*d

ordering-prefix = "{" numericstring "}"

value = <any sequence of octets>

ordered-value = ordering-prefix value

The ordinals are zero-based and increment by one for each value.

Note that when storing ordered-values into the directory, the ordering-prefix can usually be omitted as it will be generated automatically. But if the original value already begins with a sequence of characters in the form of an ordering-prefix, then an ordering-prefix must always be provided with that value, otherwise the value will be processed and stored incorrectly.

Using this extension on an attribute requires that ordering-prefix is a legal value of the LDAP syntax of that attribute.



 TOC 

3.3. Ordering Properties

Since the ordering-prefix is stored with the attribute values, it will be propagated to any clients or servers that access the data.

Servers implementing this scheme SHOULD sort the values according to their ordering-prefix before returning them in search results.

The presence of the ordering extension alters the matching rules that apply to the attribute:

When presented with an AssertionValue that does not have an ordering-prefix, the ordering-prefix in the AttributeValue is ignored.

When presented with an AssertionValue that consists solely of an ordering-prefix, only the ordering-prefix of the AttributeValue is compared; the remainder of the value is ignored.

When presented with an AssertionValue containing both the ordering-prefix and a value, both components are compared to determine a match.

A side effect of these properties is that even attributes that normally would have no equality matching rule can be matched by an ordering-prefix.

The ordering-prefix may also be used in Modification requests to specify which values to delete, and in which position values should be added. When processing deletions and insertions, all of the ordinals are recounted after each individual modification.

If a value being added does not have an ordering-prefix, it is simply appended to the list and the appropriate ordering-prefix is automatically generated. Likewise if an ordering-prefix is provided that is greater than or equal to the number of existing values.

See the examples in the next section.



 TOC 

4. Examples



 TOC 

4.1. Sample Schema

This schema is used for all of the examples:

( EXAMPLE_AT.1 NAME 'olcDatabase'
EQUALITY caseIgnoreMatch
SYNTAX 1.3.6.1.4.1.1466.115.121.1.15
SINGLE-VALUE X-ORDERED 'SIBLINGS' )

( EXAMPLE_AT.2 NAME 'olcSuffix'
EQUALITY distinguishedNameMatch
SYNTAX 1.3.6.1.4.1.1466.115.121.1.12
X-ORDERED 'VALUES' )

( EXAMPLE_OC.1 NAME 'olcDatabaseConfig'
SUP top STRUCTURAL
MAY ( olcDatabase $ olcSuffix ) )



 TOC 

4.2. Ordered Values

Given this entry:

dn: olcDatabase={1}bdb,cn=config
olcDatabase: {1}bdb
objectClass: olcDatabaseConfig
olcSuffix: {0}dc=example,dc=com
olcSuffix: {1}o=example.com
olcSuffix: {2}o=The Example Company
olcSuffix: {3}o=example,c=us

We can perform these Modify operations:

  1. dn: olcDatabase={1}bdb,cn=config
    changetype: modify
    delete: olcSuffix
    olcSuffix: {0}
    -
    This operation deletes the first olcSuffix, regardless of its value. All other values are bumped up one position. The olcSuffix attribute will end up containing:
    olcSuffix: {0}o=example.com
    olcSuffix: {1}o=The Example Company
    olcSuffix: {2}o=example,c=us
  2. Starting from the original entry, we could issue this change instead:
    delete: olcSuffix
    olcSuffix: o=example.com
    -
    This operation deletes the olcSuffix that matches the value, regardless of its ordering-prefix. The olcSuffix attribute will contain:
    olcSuffix: {0}dc=example,dc=com
    olcSuffix: {1}o=The Example Company
    olcSuffix: {2}o=example,c=us
  3. Again, starting from the original entry, we could issue this change:
    delete: olcSuffix
    olcSuffix: {2}o=The Example Company
    -
    Here both the ordering-prefix and the value must match, otherwise the Modify would fail with noSuchAttribute. In this case the olcSuffix attribute results in:
    olcSuffix: {0}dc=example,dc=com
    olcSuffix: {1}o=example.com
    olcSuffix: {2}o=example,c=us
  4. Adding a new value without an ordering-prefix simply appends:
    add: olcSuffix
    olcSuffix: o=example.org
    -
    The resulting attribute would be:
    olcSuffix: {0}dc=example,dc=com
    olcSuffix: {1}o=example.com
    olcSuffix: {2}o=The Example Company
    olcSuffix: {3}o=example,c=us
    olcSuffix: {4}o=example.org
  5. Adding a new value with an ordering-prefix inserts into the specified position:
    add: olcSuffix
    olcSuffix: {0}o=example.org
    -
    The resulting attribute would be:
    olcSuffix: {0}o=example.org
    olcSuffix: {1}dc=example,dc=com
    olcSuffix: {2}o=example.com
    olcSuffix: {3}o=The Example Company
    olcSuffix: {4}o=example,c=us
  6. Modifying multiple values in one operation:
    add: olcSuffix
    olcSuffix: {0}ou=Dis,o=example.com
    olcSuffix: {0}ou=Dat,o=example,com
    -
    delete: olcSuffix:
    olcSuffix: {2}
    olcSuffix: {1}
    -
    The resulting attribute would be:
    olcSuffix: {0}ou=Dat,o=example,com
    olcSuffix: {1}dc=example,dc=com
    olcSuffix: {2}o=example.com
    olcSuffix: {3}o=The Example Company
    olcSuffix: {4}o=example,c=us
  7. If the Adds and Deletes in the previous example were done in the opposite order:
    delete: olcSuffix:
    olcSuffix: {2}
    olcSuffix: {1}
    -
    add: olcSuffix
    olcSuffix: {0}ou=Dis,o=example.com
    olcSuffix: {0}ou=Dat,o=example,com
    -
    The result would be:
    olcSuffix: {0}ou=Dat,o=example,com
    olcSuffix: {1}ou=Dis,o=example.com
    olcSuffix: {2}o=example.org
    olcSuffix: {3}o=The Example Company
    olcSuffix: {4}o=example,c=us

Note that matching against an ordering-prefix can also be done in Compare operations and Search filters. E.g., the filter "(olcSuffix={4})" would match all entries with at least 5 olcSuffix values.



 TOC 

4.3. Ordered Siblings

The rules for Ordered Siblings are basically the same as for Ordered Values, except instead of working primarily with the Modify request, the operations of interest here are Add, Delete, and ModRDN.

Given these entries:

dn: olcDatabase={0}config,cn=config
olcDatabase: {0}config
objectClass: olcDatabaseConfig
olcSuffix: {0}cn=config

dn: olcDatabase={1}bdb,cn=config
olcDatabase: {1}bdb
objectClass: olcDatabaseConfig
olcSuffix: {0}dc=example,dc=com

We can perform these operations:

  1. Add a new entry with no ordering-prefix:
    dn: olcDatabase=hdb,cn=config
    changetype: add
    olcDatabase: hdb
    objectClass: olcDatabaseConfig
    olcSuffix: {0}dc=example,dc=org
    The resulting entry will be:
    dn: olcDatabase={2}hdb,cn=config
    olcDatabase: {2}hdb
    objectClass: olcDatabaseConfig
    olcSuffix: {0}dc=example,dc=org
  2. Continuing on with these three entries, we can add another entry with a specific ordering-prefix:
    dn: olcDatabase={1}ldif,cn=config
    changetype: add
    olcDatabase: {1}ldif
    objectClass: olcDatabaseConfig
    olcSuffix: {0}o=example.com

    This would give us four entries, whose DNs are:

    dn: olcDatabase={0}config,cn=config

    dn: olcDatabase={1}ldif,cn=config

    dn: olcDatabase={2}bdb,cn=config

    dn: olcDatabase={3}hdb,cn=config

  3. Issuing a ModRDN request will cause multiple entries to be renamed:
    dn: olcDatabase={1}ldif,cn=config
    changetype: modrdn
    newrdn: olcDatabase={99}ldif,cn=config
    deleteoldrdn: 1

    The resulting entries would be named:

    dn: olcDatabase={0}config,cn=config

    dn: olcDatabase={1}bdb,cn=config

    dn: olcDatabase={2}hdb,cn=config

    dn: olcDatabase={3}ldif,cn=config

  4. As may be expected, a Delete request will also rename the remaining entries:
    dn: olcDatabase={1}bdb,cn=config
    changetype: delete

    The remaining entries would be named:

    dn: olcDatabase={0}config,cn=config

    dn: olcDatabase={1}hdb,cn=config

    dn: olcDatabase={2}ldif,cn=config



 TOC 

5. Security Considerations

General LDAP security considerations [RFC3377] (Hodges, J. and R. Morgan, “Lightweight Directory Access Protocol (v3): Technical Specification,” September 2002.) apply.



 TOC 

6. Normative References

[RFC2119] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” BCP 14, RFC 2119, March 1997 (TXT, HTML, XML).
[RFC2252] Wahl, M., Coulbeck, A., Howes, T., and S. Kille, “Lightweight Directory Access Protocol (v3): Attribute Syntax Definitions,” RFC 2252, December 1997 (TXT, HTML, XML).
[RFC3377] Hodges, J. and R. Morgan, “Lightweight Directory Access Protocol (v3): Technical Specification,” RFC 3377, September 2002.
[RFC3383] Zeilenga, K., “Internet Assigned Numbers Authority (IANA) Considerations for the Lightweight Directory Access Protocol (LDAP),” BCP 64, RFC 3383, September 2002.
[X680] International Telecommunications Union, “Abstract Syntax Notation One (ASN.1): Specification of basic notation,” ITU-T Recommendation X.680, July 2002.


 TOC 

Appendix A. IANA Considerations

In accordance with [RFC3383] (Zeilenga, K., “Internet Assigned Numbers Authority (IANA) Considerations for the Lightweight Directory Access Protocol (LDAP),” September 2002.) (what needs to be done here?) . We probably need an OID for advertising in supportedFeatures.



 TOC 

Author's Address

  Howard Chu
  Symas Corp.
  18740 Oxnard Street, Suite 313A
  Tarzana, California 91356
  USA
Phone:  +1 818 757-7087
Email:  hyc@symas.com


 TOC 

Intellectual Property Statement

Disclaimer of Validity

Copyright Statement

Acknowledgment