4 Network Working Group H. Chu
5 Internet-Draft Symas Corp.
6 Intended status: Informational May 2006
7 Expires: November 2, 2006
10 Ordered Entries and Values in LDAP
11 draft-chu-ldap-xordered-00.txt
15 By submitting this Internet-Draft, each author represents that any
16 applicable patent or other IPR claims of which he or she is aware
17 have been or will be disclosed, and any of which he or she becomes
18 aware will be disclosed, in accordance with Section 6 of BCP 79.
20 Internet-Drafts are working documents of the Internet Engineering
21 Task Force (IETF), its areas, and its working groups. Note that
22 other groups may also distribute working documents as Internet-
25 Internet-Drafts are draft documents valid for a maximum of six months
26 and may be updated, replaced, or obsoleted by other documents at any
27 time. It is inappropriate to use Internet-Drafts as reference
28 material or to cite them other than as "work in progress."
30 The list of current Internet-Drafts can be accessed at
31 http://www.ietf.org/ietf/1id-abstracts.txt.
33 The list of Internet-Draft Shadow Directories can be accessed at
34 http://www.ietf.org/shadow.html.
36 This Internet-Draft will expire on November 2, 2006.
40 Copyright (C) The Internet Society (2006).
55 Chu Expires November 2, 2006 [Page 1]
57 Internet-Draft LDAP Ordering Extension May 2006
62 As LDAP is used more extensively for managing various kinds of data,
63 one often encounters a need to preserve both the ordering and the
64 content of data, despite the inherently unordered structure of
65 entries and attribute values in the directory. This document
66 describes a scheme to attach ordering information to attributes in a
67 directory so that the ordering may be preserved and propagated to
68 other LDAP applications.
73 1. Introduction . . . . . . . . . . . . . . . . . . . . . 3
74 2. Conventions . . . . . . . . . . . . . . . . . . . . . 4
75 3. Ordering Extension . . . . . . . . . . . . . . . . . . 5
76 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . 5
77 3.2. Encoding . . . . . . . . . . . . . . . . . . . . . . . 5
78 3.3. Ordering Properties . . . . . . . . . . . . . . . . . 6
79 4. Examples . . . . . . . . . . . . . . . . . . . . . . . 8
80 4.1. Sample Schema . . . . . . . . . . . . . . . . . . . . 8
81 4.2. Ordered Values . . . . . . . . . . . . . . . . . . . . 8
82 4.3. Ordered Siblings . . . . . . . . . . . . . . . . . . . 10
83 5. Security Considerations . . . . . . . . . . . . . . . 13
84 6. Normative References . . . . . . . . . . . . . . . . . 14
85 Appendix A. IANA Considerations . . . . . . . . . . . . . . . . . 15
86 Author's Address . . . . . . . . . . . . . . . . . . . 16
87 Intellectual Property and Copyright Statements . . . . 17
111 Chu Expires November 2, 2006 [Page 2]
113 Internet-Draft LDAP Ordering Extension May 2006
118 Information in LDAP directories is usually handled by applications in
119 the form of ordered lists, which tends to encourage application
120 developers to assume they are maintained as such, i.e., it is assumed
121 that information stored in a particular order will always be
122 retrieved and presented in that same order. The fact that directory
123 attributes actually store sets of values, which are inherently
124 unordered, often causes grief to users migrating their data into
125 LDAP. Similar concerns arise over the order in which entries
126 themselves are stored and retrieved from the directory.
128 This document describes a schema extension that may be used in LDAP
129 attribute definitions to store ordering information along with the
130 attribute values, so that the ordering can be recovered when
131 retrieved by an LDAP client. The extension also provides automated
132 management of this ordering information to ease manipulation of the
167 Chu Expires November 2, 2006 [Page 3]
169 Internet-Draft LDAP Ordering Extension May 2006
174 Imperative keywords defined in [RFC2119] are used in this document,
175 and carry the meanings described there.
223 Chu Expires November 2, 2006 [Page 4]
225 Internet-Draft LDAP Ordering Extension May 2006
228 3. Ordering Extension
232 The "X-ORDERED" schema extension is added to an
233 AttributeTypeDescription to signify the use of this ordering
234 mechanism. The extension has two variants, selected by either the
235 'VALUES' or 'SIBLINGS' qdstrings. In general this extension is only
236 compatible with AttributeTypes that have a string-oriented syntax.
238 The "X-ORDERED 'VALUES'" extension is used with multi-valued
239 attributes to maintain the order of multiple values of a given
240 attribute. For example, this feature is useful for storing data such
241 as access control rules, which must be evaluated in a specific order.
242 If the access control information is stored in a multi-valued
243 attribute without a means of preserving the the order of the rules,
244 the access control rules cannot be evaluated properly. As the use of
245 LDAP to store security policy and access control information becomes
246 more prevalent, the necessity of this feature continues to grow.
248 The "X-ORDERED 'SIBLINGS'" extension is used with single-valued
249 attributes to maintain the order of all the onelevel children of a
250 parent entry. That is, ordering will be maintained for all the child
251 entries whose RDNs are all of the same AttributeType. The motivation
252 for this feature is much the same as for the 'VALUES' feature.
253 Sometimes the information with the ordering dependency is too complex
254 or highly structured to be conveniently stored in values of a multi-
255 valued attribute. For example, one could store a prioritized list of
256 servers as a set of separate entries, each entry containing separate
257 attributes for a URL, a set of authentication credentials, and
258 various other parameters. Using the 'SIBLINGS' feature with the
259 attribute in the entries' RDNs would ensure that when obtaining the
260 list of these entries, the list is returned in the intended order.
264 Ordering information is encoded by prepending a value's ordinal index
265 to each value, enclosed in braces. The following BNF specifies the
266 encoding. It uses elements defined in [RFC2252].
268 d = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
272 ordering-prefix = "{" numericstring "}"
274 value = <any sequence of octets>
279 Chu Expires November 2, 2006 [Page 5]
281 Internet-Draft LDAP Ordering Extension May 2006
284 ordered-value = ordering-prefix value
286 The ordinals are zero-based and increment by one for each value.
288 Note that when storing ordered-values into the directory, the
289 ordering-prefix can usually be omitted as it will be generated
290 automatically. But if the original value already begins with a
291 sequence of characters in the form of an ordering-prefix, then an
292 ordering-prefix must always be provided with that value, otherwise
293 the value will be processed and stored incorrectly.
295 Using this extension on an attribute requires that ordering-prefix is
296 a legal value of the LDAP syntax of that attribute.
298 3.3. Ordering Properties
300 Since the ordering-prefix is stored with the attribute values, it
301 will be propagated to any clients or servers that access the data.
303 Servers implementing this scheme SHOULD sort the values according to
304 their ordering-prefix before returning them in search results.
306 The presence of the ordering extension alters the matching rules that
307 apply to the attribute:
309 When presented with an AssertionValue that does not have an
310 ordering-prefix, the ordering-prefix in the AttributeValue is
313 When presented with an AssertionValue that consists solely of an
314 ordering-prefix, only the ordering-prefix of the AttributeValue is
315 compared; the remainder of the value is ignored.
317 When presented with an AssertionValue containing both the
318 ordering-prefix and a value, both components are compared to
321 A side effect of these properties is that even attributes that
322 normally would have no equality matching rule can be matched by an
325 The ordering-prefix may also be used in Modification requests to
326 specify which values to delete, and in which position values should
327 be added. When processing deletions and insertions, all of the
328 ordinals are recounted after each individual modification.
330 If a value being added does not have an ordering-prefix, it is simply
331 appended to the list and the appropriate ordering-prefix is
335 Chu Expires November 2, 2006 [Page 6]
337 Internet-Draft LDAP Ordering Extension May 2006
340 automatically generated. Likewise if an ordering-prefix is provided
341 that is greater than or equal to the number of existing values.
343 See the examples in the next section.
391 Chu Expires November 2, 2006 [Page 7]
393 Internet-Draft LDAP Ordering Extension May 2006
400 This schema is used for all of the examples:
402 ( EXAMPLE_AT.1 NAME 'olcDatabase'
403 EQUALITY caseIgnoreMatch
404 SYNTAX 1.3.6.1.4.1.1466.115.121.1.15
405 SINGLE-VALUE X-ORDERED 'SIBLINGS' )
407 ( EXAMPLE_AT.2 NAME 'olcSuffix'
408 EQUALITY distinguishedNameMatch
409 SYNTAX 1.3.6.1.4.1.1466.115.121.1.12
412 ( EXAMPLE_OC.1 NAME 'olcDatabaseConfig'
414 MAY ( olcDatabase $ olcSuffix ) )
420 dn: olcDatabase={1}bdb,cn=config
422 objectClass: olcDatabaseConfig
423 olcSuffix: {0}dc=example,dc=com
424 olcSuffix: {1}o=example.com
425 olcSuffix: {2}o=The Example Company
426 olcSuffix: {3}o=example,c=us
428 We can perform these Modify operations:
430 1. dn: olcDatabase={1}bdb,cn=config
435 This operation deletes the first olcSuffix, regardless of its
436 value. All other values are bumped up one position. The
437 olcSuffix attribute will end up containing:
438 olcSuffix: {0}o=example.com
439 olcSuffix: {1}o=The Example Company
440 olcSuffix: {2}o=example,c=us
442 2. Starting from the original entry, we could issue this change
447 Chu Expires November 2, 2006 [Page 8]
449 Internet-Draft LDAP Ordering Extension May 2006
453 olcSuffix: o=example.com
455 This operation deletes the olcSuffix that matches the value,
456 regardless of its ordering-prefix. The olcSuffix attribute will
458 olcSuffix: {0}dc=example,dc=com
459 olcSuffix: {1}o=The Example Company
460 olcSuffix: {2}o=example,c=us
462 3. Again, starting from the original entry, we could issue this
465 olcSuffix: {2}o=The Example Company
467 Here both the ordering-prefix and the value must match, otherwise
468 the Modify would fail with noSuchAttribute. In this case the
469 olcSuffix attribute results in:
470 olcSuffix: {0}dc=example,dc=com
471 olcSuffix: {1}o=example.com
472 olcSuffix: {2}o=example,c=us
474 4. Adding a new value without an ordering-prefix simply appends:
476 olcSuffix: o=example.org
478 The resulting attribute would be:
479 olcSuffix: {0}dc=example,dc=com
480 olcSuffix: {1}o=example.com
481 olcSuffix: {2}o=The Example Company
482 olcSuffix: {3}o=example,c=us
483 olcSuffix: {4}o=example.org
485 5. Adding a new value with an ordering-prefix inserts into the
488 olcSuffix: {0}o=example.org
490 The resulting attribute would be:
491 olcSuffix: {0}o=example.org
492 olcSuffix: {1}dc=example,dc=com
493 olcSuffix: {2}o=example.com
494 olcSuffix: {3}o=The Example Company
495 olcSuffix: {4}o=example,c=us
497 6. Modifying multiple values in one operation:
499 olcSuffix: {0}ou=Dis,o=example.com
503 Chu Expires November 2, 2006 [Page 9]
505 Internet-Draft LDAP Ordering Extension May 2006
508 olcSuffix: {0}ou=Dat,o=example,com
514 The resulting attribute would be:
515 olcSuffix: {0}ou=Dat,o=example,com
516 olcSuffix: {1}dc=example,dc=com
517 olcSuffix: {2}o=example.com
518 olcSuffix: {3}o=The Example Company
519 olcSuffix: {4}o=example,c=us
521 7. If the Adds and Deletes in the previous example were done in the
528 olcSuffix: {0}ou=Dis,o=example.com
529 olcSuffix: {0}ou=Dat,o=example,com
532 olcSuffix: {0}ou=Dat,o=example,com
533 olcSuffix: {1}ou=Dis,o=example.com
534 olcSuffix: {2}o=example.org
535 olcSuffix: {3}o=The Example Company
536 olcSuffix: {4}o=example,c=us
538 Note that matching against an ordering-prefix can also be done in
539 Compare operations and Search filters. E.g., the filter
540 "(olcSuffix={4})" would match all entries with at least 5 olcSuffix
543 4.3. Ordered Siblings
545 The rules for Ordered Siblings are basically the same as for Ordered
546 Values, except instead of working primarily with the Modify request,
547 the operations of interest here are Add, Delete, and ModRDN.
551 dn: olcDatabase={0}config,cn=config
552 olcDatabase: {0}config
553 objectClass: olcDatabaseConfig
554 olcSuffix: {0}cn=config
559 Chu Expires November 2, 2006 [Page 10]
561 Internet-Draft LDAP Ordering Extension May 2006
564 dn: olcDatabase={1}bdb,cn=config
566 objectClass: olcDatabaseConfig
567 olcSuffix: {0}dc=example,dc=com
569 We can perform these operations:
571 1. Add a new entry with no ordering-prefix:
572 dn: olcDatabase=hdb,cn=config
575 objectClass: olcDatabaseConfig
576 olcSuffix: {0}dc=example,dc=org
577 The resulting entry will be:
578 dn: olcDatabase={2}hdb,cn=config
580 objectClass: olcDatabaseConfig
581 olcSuffix: {0}dc=example,dc=org
583 2. Continuing on with these three entries, we can add another entry
584 with a specific ordering-prefix:
585 dn: olcDatabase={1}ldif,cn=config
588 objectClass: olcDatabaseConfig
589 olcSuffix: {0}o=example.com
590 This would give us four entries, whose DNs are:
592 dn: olcDatabase={0}config,cn=config
594 dn: olcDatabase={1}ldif,cn=config
596 dn: olcDatabase={2}bdb,cn=config
598 dn: olcDatabase={3}hdb,cn=config
600 3. Issuing a ModRDN request will cause multiple entries to be
602 dn: olcDatabase={1}ldif,cn=config
604 newrdn: olcDatabase={99}ldif
606 The resulting entries would be named:
608 dn: olcDatabase={0}config,cn=config
610 dn: olcDatabase={1}bdb,cn=config
615 Chu Expires November 2, 2006 [Page 11]
617 Internet-Draft LDAP Ordering Extension May 2006
620 dn: olcDatabase={2}hdb,cn=config
622 dn: olcDatabase={3}ldif,cn=config
624 4. As may be expected, a Delete request will also rename the
626 dn: olcDatabase={1}bdb,cn=config
628 The remaining entries would be named:
630 dn: olcDatabase={0}config,cn=config
632 dn: olcDatabase={1}hdb,cn=config
634 dn: olcDatabase={2}ldif,cn=config
671 Chu Expires November 2, 2006 [Page 12]
673 Internet-Draft LDAP Ordering Extension May 2006
676 5. Security Considerations
678 General LDAP security considerations [RFC3377] apply.
727 Chu Expires November 2, 2006 [Page 13]
729 Internet-Draft LDAP Ordering Extension May 2006
732 6. Normative References
734 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
735 Requirement Levels", BCP 14, RFC 2119, March 1997.
737 [RFC2252] Wahl, M., Coulbeck, A., Howes, T., and S. Kille,
738 "Lightweight Directory Access Protocol (v3): Attribute
739 Syntax Definitions", RFC 2252, December 1997.
741 [RFC3377] Hodges, J. and R. Morgan, "Lightweight Directory Access
742 Protocol (v3): Technical Specification", RFC 3377,
745 [RFC3383] Zeilenga, K., "Internet Assigned Numbers Authority (IANA)
746 Considerations for the Lightweight Directory Access
747 Protocol (LDAP)", RFC 3383, September 2002.
749 [X680] International Telecommunications Union, "Abstract Syntax
750 Notation One (ASN.1): Specification of basic notation",
751 ITU-T Recommendation X.680, July 2002.
783 Chu Expires November 2, 2006 [Page 14]
785 Internet-Draft LDAP Ordering Extension May 2006
788 Appendix A. IANA Considerations
790 In accordance with [RFC3383] (what needs to be done here?) . We
791 probably need an OID for advertising in supportedFeatures.
839 Chu Expires November 2, 2006 [Page 15]
841 Internet-Draft LDAP Ordering Extension May 2006
848 18740 Oxnard Street, Suite 313A
849 Tarzana, California 91356
852 Phone: +1 818 757-7087
895 Chu Expires November 2, 2006 [Page 16]
897 Internet-Draft LDAP Ordering Extension May 2006
900 Full Copyright Statement
902 Copyright (C) The Internet Society (2006).
904 This document is subject to the rights, licenses and restrictions
905 contained in BCP 78, and except as set forth therein, the authors
906 retain all their rights.
908 This document and the information contained herein are provided on an
909 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
910 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
911 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
912 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
913 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
914 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
917 Intellectual Property
919 The IETF takes no position regarding the validity or scope of any
920 Intellectual Property Rights or other rights that might be claimed to
921 pertain to the implementation or use of the technology described in
922 this document or the extent to which any license under such rights
923 might or might not be available; nor does it represent that it has
924 made any independent effort to identify any such rights. Information
925 on the procedures with respect to rights in RFC documents can be
926 found in BCP 78 and BCP 79.
928 Copies of IPR disclosures made to the IETF Secretariat and any
929 assurances of licenses to be made available, or the result of an
930 attempt made to obtain a general license or permission for the use of
931 such proprietary rights by implementers or users of this
932 specification can be obtained from the IETF on-line IPR repository at
933 http://www.ietf.org/ipr.
935 The IETF invites any interested party to bring to its attention any
936 copyrights, patents or patent applications, or other proprietary
937 rights that may cover technology that may be required to implement
938 this standard. Please address the information to the IETF at
944 Funding for the RFC Editor function is provided by the IETF
945 Administrative Support Activity (IASA).
951 Chu Expires November 2, 2006 [Page 17]