]> git.sur5r.net Git - openldap/blob - doc/drafts/draft-chu-ldap-xordered-xx.txt
Merge remote-tracking branch 'origin/mdb.RE/0.9'
[openldap] / doc / drafts / draft-chu-ldap-xordered-xx.txt
1
2
3
4 Network Working Group                                             H. Chu
5 Internet-Draft                                               Symas Corp.
6 Intended status: Informational                                  May 2006
7 Expires: November 2, 2006
8
9
10                    Ordered Entries and Values in LDAP
11                      draft-chu-ldap-xordered-00.txt
12
13 Status of this Memo
14
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.
19
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-
23    Drafts.
24
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."
29
30    The list of current Internet-Drafts can be accessed at
31    http://www.ietf.org/ietf/1id-abstracts.txt.
32
33    The list of Internet-Draft Shadow Directories can be accessed at
34    http://www.ietf.org/shadow.html.
35
36    This Internet-Draft will expire on November 2, 2006.
37
38 Copyright Notice
39
40    Copyright (C) The Internet Society (2006).
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 Chu                     Expires November 2, 2006                [Page 1]
56 \f
57 Internet-Draft           LDAP Ordering Extension                May 2006
58
59
60 Abstract
61
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.
69
70
71 Table of Contents
72
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111 Chu                     Expires November 2, 2006                [Page 2]
112 \f
113 Internet-Draft           LDAP Ordering Extension                May 2006
114
115
116 1.  Introduction
117
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.
127
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
133    ordered values.
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167 Chu                     Expires November 2, 2006                [Page 3]
168 \f
169 Internet-Draft           LDAP Ordering Extension                May 2006
170
171
172 2.  Conventions
173
174    Imperative keywords defined in [RFC2119] are used in this document,
175    and carry the meanings described there.
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223 Chu                     Expires November 2, 2006                [Page 4]
224 \f
225 Internet-Draft           LDAP Ordering Extension                May 2006
226
227
228 3.  Ordering Extension
229
230 3.1.  Overview
231
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.
237
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.
247
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.
261
262 3.2.  Encoding
263
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].
267
268       d = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"
269
270       numericstring = 1*d
271
272       ordering-prefix = "{" numericstring "}"
273
274       value = <any sequence of octets>
275
276
277
278
279 Chu                     Expires November 2, 2006                [Page 5]
280 \f
281 Internet-Draft           LDAP Ordering Extension                May 2006
282
283
284       ordered-value = ordering-prefix value
285
286    The ordinals are zero-based and increment by one for each value.
287
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.
294
295    Using this extension on an attribute requires that ordering-prefix is
296    a legal value of the LDAP syntax of that attribute.
297
298 3.3.  Ordering Properties
299
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.
302
303    Servers implementing this scheme SHOULD sort the values according to
304    their ordering-prefix before returning them in search results.
305
306    The presence of the ordering extension alters the matching rules that
307    apply to the attribute:
308
309       When presented with an AssertionValue that does not have an
310       ordering-prefix, the ordering-prefix in the AttributeValue is
311       ignored.
312
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.
316
317       When presented with an AssertionValue containing both the
318       ordering-prefix and a value, both components are compared to
319       determine a match.
320
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
323    ordering-prefix.
324
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.
329
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
332
333
334
335 Chu                     Expires November 2, 2006                [Page 6]
336 \f
337 Internet-Draft           LDAP Ordering Extension                May 2006
338
339
340    automatically generated.  Likewise if an ordering-prefix is provided
341    that is greater than or equal to the number of existing values.
342
343    See the examples in the next section.
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391 Chu                     Expires November 2, 2006                [Page 7]
392 \f
393 Internet-Draft           LDAP Ordering Extension                May 2006
394
395
396 4.  Examples
397
398 4.1.  Sample Schema
399
400    This schema is used for all of the examples:
401
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' )
406
407    ( EXAMPLE_AT.2 NAME 'olcSuffix'
408    EQUALITY distinguishedNameMatch
409    SYNTAX 1.3.6.1.4.1.1466.115.121.1.12
410    X-ORDERED 'VALUES' )
411
412    ( EXAMPLE_OC.1 NAME 'olcDatabaseConfig'
413    SUP top STRUCTURAL
414    MAY ( olcDatabase $ olcSuffix ) )
415
416 4.2.  Ordered Values
417
418    Given this entry:
419
420    dn: olcDatabase={1}bdb,cn=config
421    olcDatabase: {1}bdb
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
427
428    We can perform these Modify operations:
429
430    1.  dn: olcDatabase={1}bdb,cn=config
431        changetype: modify
432        delete: olcSuffix
433        olcSuffix: {0}
434        -
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
441
442    2.  Starting from the original entry, we could issue this change
443        instead:
444
445
446
447 Chu                     Expires November 2, 2006                [Page 8]
448 \f
449 Internet-Draft           LDAP Ordering Extension                May 2006
450
451
452        delete: olcSuffix
453        olcSuffix: o=example.com
454        -
455        This operation deletes the olcSuffix that matches the value,
456        regardless of its ordering-prefix.  The olcSuffix attribute will
457        contain:
458        olcSuffix: {0}dc=example,dc=com
459        olcSuffix: {1}o=The Example Company
460        olcSuffix: {2}o=example,c=us
461
462    3.  Again, starting from the original entry, we could issue this
463        change:
464        delete: olcSuffix
465        olcSuffix: {2}o=The Example Company
466        -
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
473
474    4.  Adding a new value without an ordering-prefix simply appends:
475        add: olcSuffix
476        olcSuffix: o=example.org
477        -
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
484
485    5.  Adding a new value with an ordering-prefix inserts into the
486        specified position:
487        add: olcSuffix
488        olcSuffix: {0}o=example.org
489        -
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
496
497    6.  Modifying multiple values in one operation:
498        add: olcSuffix
499        olcSuffix: {0}ou=Dis,o=example.com
500
501
502
503 Chu                     Expires November 2, 2006                [Page 9]
504 \f
505 Internet-Draft           LDAP Ordering Extension                May 2006
506
507
508        olcSuffix: {0}ou=Dat,o=example,com
509        -
510        delete: olcSuffix:
511        olcSuffix: {2}
512        olcSuffix: {1}
513        -
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
520
521    7.  If the Adds and Deletes in the previous example were done in the
522        opposite order:
523        delete: olcSuffix:
524        olcSuffix: {2}
525        olcSuffix: {1}
526        -
527        add: olcSuffix
528        olcSuffix: {0}ou=Dis,o=example.com
529        olcSuffix: {0}ou=Dat,o=example,com
530        -
531        The result would be:
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
537
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
541    values.
542
543 4.3.  Ordered Siblings
544
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.
548
549    Given these entries:
550
551    dn: olcDatabase={0}config,cn=config
552    olcDatabase: {0}config
553    objectClass: olcDatabaseConfig
554    olcSuffix: {0}cn=config
555
556
557
558
559 Chu                     Expires November 2, 2006               [Page 10]
560 \f
561 Internet-Draft           LDAP Ordering Extension                May 2006
562
563
564    dn: olcDatabase={1}bdb,cn=config
565    olcDatabase: {1}bdb
566    objectClass: olcDatabaseConfig
567    olcSuffix: {0}dc=example,dc=com
568
569    We can perform these operations:
570
571    1.  Add a new entry with no ordering-prefix:
572        dn: olcDatabase=hdb,cn=config
573        changetype: add
574        olcDatabase: hdb
575        objectClass: olcDatabaseConfig
576        olcSuffix: {0}dc=example,dc=org
577        The resulting entry will be:
578        dn: olcDatabase={2}hdb,cn=config
579        olcDatabase: {2}hdb
580        objectClass: olcDatabaseConfig
581        olcSuffix: {0}dc=example,dc=org
582
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
586        changetype: add
587        olcDatabase: {1}ldif
588        objectClass: olcDatabaseConfig
589        olcSuffix: {0}o=example.com
590        This would give us four entries, whose DNs are:
591
592           dn: olcDatabase={0}config,cn=config
593
594           dn: olcDatabase={1}ldif,cn=config
595
596           dn: olcDatabase={2}bdb,cn=config
597
598           dn: olcDatabase={3}hdb,cn=config
599
600    3.  Issuing a ModRDN request will cause multiple entries to be
601        renamed:
602        dn: olcDatabase={1}ldif,cn=config
603        changetype: modrdn
604        newrdn: olcDatabase={99}ldif
605        deleteoldrdn: 1
606        The resulting entries would be named:
607
608           dn: olcDatabase={0}config,cn=config
609
610           dn: olcDatabase={1}bdb,cn=config
611
612
613
614
615 Chu                     Expires November 2, 2006               [Page 11]
616 \f
617 Internet-Draft           LDAP Ordering Extension                May 2006
618
619
620           dn: olcDatabase={2}hdb,cn=config
621
622           dn: olcDatabase={3}ldif,cn=config
623
624    4.  As may be expected, a Delete request will also rename the
625        remaining entries:
626        dn: olcDatabase={1}bdb,cn=config
627        changetype: delete
628        The remaining entries would be named:
629
630           dn: olcDatabase={0}config,cn=config
631
632           dn: olcDatabase={1}hdb,cn=config
633
634           dn: olcDatabase={2}ldif,cn=config
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671 Chu                     Expires November 2, 2006               [Page 12]
672 \f
673 Internet-Draft           LDAP Ordering Extension                May 2006
674
675
676 5.  Security Considerations
677
678    General LDAP security considerations [RFC3377] apply.
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727 Chu                     Expires November 2, 2006               [Page 13]
728 \f
729 Internet-Draft           LDAP Ordering Extension                May 2006
730
731
732 6.  Normative References
733
734    [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
735               Requirement Levels", BCP 14, RFC 2119, March 1997.
736
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.
740
741    [RFC3377]  Hodges, J. and R. Morgan, "Lightweight Directory Access
742               Protocol (v3): Technical Specification", RFC 3377,
743               September 2002.
744
745    [RFC3383]  Zeilenga, K., "Internet Assigned Numbers Authority (IANA)
746               Considerations for the Lightweight Directory Access
747               Protocol (LDAP)", RFC 3383, September 2002.
748
749    [X680]     International Telecommunications Union, "Abstract Syntax
750               Notation One (ASN.1): Specification of basic notation",
751               ITU-T Recommendation X.680, July 2002.
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783 Chu                     Expires November 2, 2006               [Page 14]
784 \f
785 Internet-Draft           LDAP Ordering Extension                May 2006
786
787
788 Appendix A.  IANA Considerations
789
790    In accordance with [RFC3383] (what needs to be done here?) .  We
791    probably need an OID for advertising in supportedFeatures.
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839 Chu                     Expires November 2, 2006               [Page 15]
840 \f
841 Internet-Draft           LDAP Ordering Extension                May 2006
842
843
844 Author's Address
845
846    Howard Chu
847    Symas Corp.
848    18740 Oxnard Street, Suite 313A
849    Tarzana, California  91356
850    USA
851
852    Phone: +1 818 757-7087
853    Email: hyc@symas.com
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895 Chu                     Expires November 2, 2006               [Page 16]
896 \f
897 Internet-Draft           LDAP Ordering Extension                May 2006
898
899
900 Full Copyright Statement
901
902    Copyright (C) The Internet Society (2006).
903
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.
907
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.
915
916
917 Intellectual Property
918
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.
927
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.
934
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
939    ietf-ipr@ietf.org.
940
941
942 Acknowledgment
943
944    Funding for the RFC Editor function is provided by the IETF
945    Administrative Support Activity (IASA).
946
947
948
949
950
951 Chu                     Expires November 2, 2006               [Page 17]
952 \f