1 <?xml version="1.0" encoding="UTF-8"?>
2 <!DOCTYPE rfc SYSTEM "rfc2629.dtd" [
3 <!ENTITY rfc2119 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.2119.xml'>
4 <!ENTITY rfc822 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.0822.xml'>
5 <!ENTITY rfc2222 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.2222.xml'>
6 <!ENTITY rfc2251 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.2251.xml'>
7 <!ENTITY rfc2252 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.2252.xml'>
8 <!ENTITY rfc2254 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.2254.xml'>
9 <!ENTITY rfc2255 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.2255.xml'>
10 <!ENTITY rfc3377 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.3377.xml'>
11 <!ENTITY rfc3383 PUBLIC '' 'http://xml.resource.org/public/rfc/bibxml/reference.RFC.3383.xml'>
14 <?xml-stylesheet type='text/xsl' href='http://www.greenbytes.de/tech/webdav/rfc2629.xslt' ?>
17 <?rfc tocindent="no" ?>
18 <?rfc symrefs="yes" ?>
19 <?rfc sortrefs="yes"?>
20 <?rfc iprnotified="no" ?>
22 <rfc ipr="full3978" docName="draft-chu-ldap-xordered-00.txt">
24 <title abbrev="LDAP Ordering Extension">Ordered Entries and Values in LDAP</title>
25 <author initials="H" fullname="Howard Chu" surname="Chu">
26 <organization>Symas Corp.</organization>
29 <street>18740 Oxnard Street, Suite 313A</street>
31 <region>California</region>
33 <country>USA</country>
35 <phone>+1 818 757-7087</phone>
36 <email>hyc@symas.com</email>
39 <date year="2006" month="May"/>
41 <t>As LDAP is used more extensively for managing various
42 kinds of data, one often encounters a need to preserve both the
43 ordering and the content of data, despite the inherently unordered
44 structure of entries and attribute values in the directory. This
45 document describes a scheme to attach ordering information to
46 attributes in a directory so that the ordering may be
47 preserved and propagated to other LDAP applications.</t>
53 <section title="Introduction">
54 <t>Information in LDAP directories is usually handled by
55 applications in the form of ordered lists, which tends to encourage
56 application developers to
57 assume they are maintained as such, i.e., it is assumed that information
58 stored in a particular order will always be retrieved and presented in
59 that same order. The fact that directory attributes actually store sets of
60 values, which are inherently unordered, often causes grief to users
61 migrating their data into LDAP. Similar concerns arise over the order
62 in which entries themselves are stored and retrieved from the directory.</t>
63 <t>This document describes a schema extension that may be
64 used in LDAP attribute definitions to store ordering information along
65 with the attribute values, so that the ordering can be recovered when
66 retrieved by an LDAP client. The extension also provides automated
67 management of this ordering information to ease manipulation of the
71 <section title="Conventions">
72 <t>Imperative keywords defined in <xref target="RFC2119"/> are used
73 in this document, and carry the meanings described there.</t>
76 <section title="Ordering Extension">
77 <section title="Overview">
78 <t>The "X-ORDERED" schema extension is added to an
79 AttributeTypeDescription to signify the use of this ordering mechanism. The
80 extension has two variants, selected by either the 'VALUES' or 'SIBLINGS'
81 qdstrings. In general this extension is only compatible with AttributeTypes
82 that have a string-oriented syntax.</t>
83 <t>The "X-ORDERED 'VALUES'" extension is used with multi-valued
84 attributes to maintain the order of multiple values of a given attribute.
85 For example, this feature is useful for storing data such as access control
86 rules, which must be evaluated in a specific order. If the access control
87 information is stored in a multi-valued attribute without a means of
88 preserving the the order of the rules, the access control rules cannot be
89 evaluated properly. As the use of LDAP to store security policy and access
90 control information becomes more prevalent, the necessity of this feature
91 continues to grow.</t>
93 The "X-ORDERED 'SIBLINGS'" extension is used with single-valued attributes
94 to maintain the order of all the onelevel children of a parent entry. That is,
95 ordering will be maintained for all the child entries whose RDNs are all of
96 the same AttributeType. The motivation for this feature is much the same
97 as for the 'VALUES' feature. Sometimes the information with the ordering
98 dependency is too complex or highly structured to be conveniently stored
99 in values of a multi-valued attribute. For example, one could store a
100 prioritized list of servers as a set of separate entries, each entry
101 containing separate attributes for a URL, a set of authentication
102 credentials, and various other parameters. Using the 'SIBLINGS' feature
103 with the attribute in the entries' RDNs would ensure that when obtaining
104 the list of these entries, the list is returned in the intended order.
107 <section title="Encoding">
108 <t>Ordering information is encoded by prepending a value's ordinal
109 index to each value, enclosed in braces. The following BNF specifies the
110 encoding. It uses elements defined in <xref target="RFC2252"/>.
112 <t>d = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"</t>
113 <t>numericstring = 1*d</t>
114 <t>ordering-prefix = "{" numericstring "}"</t>
115 <t>value = <any sequence of octets></t>
116 <t>ordered-value = ordering-prefix value</t>
118 <t>The ordinals are zero-based and increment by one for each value.</t>
119 <t>Note that when storing ordered-values into the directory, the
120 ordering-prefix can usually be omitted as it will be generated automatically.
121 But if the original value already begins with a sequence of characters in
122 the form of an ordering-prefix, then an ordering-prefix must always be
123 provided with that value, otherwise the value will be processed and
124 stored incorrectly.</t>
125 <t>Using this extension on an attribute requires that ordering-prefix
126 is a legal value of the LDAP syntax of that attribute.</t>
128 <section title="Ordering Properties">
129 <t>Since the ordering-prefix is stored with the attribute values,
130 it will be propagated to any clients or servers that access the data.</t>
131 <t>Servers implementing this scheme SHOULD sort the values according
132 to their ordering-prefix before returning them in search results.</t>
133 <t>The presence of the ordering extension alters the matching rules
134 that apply to the attribute:
136 <t>When presented with an AssertionValue that does not have an
137 ordering-prefix, the ordering-prefix in the AttributeValue is ignored.</t>
138 <t>When presented with an AssertionValue that consists solely of an
139 ordering-prefix, only the ordering-prefix of the AttributeValue is compared;
140 the remainder of the value is ignored.</t>
141 <t>When presented with an AssertionValue containing both the
142 ordering-prefix and a value, both components are compared to determine a match.</t>
144 <t>A side effect of these properties is that even attributes that
145 normally would have no equality matching rule can be matched by an
147 <t>The ordering-prefix may also be used in Modification requests to
148 specify which values to delete, and in which position values should be added.
149 When processing deletions and insertions, all of the ordinals are recounted
150 after each individual modification.</t>
151 <t>If a value being added does not have
152 an ordering-prefix, it is simply appended to the list and the appropriate
153 ordering-prefix is automatically generated. Likewise if an ordering-prefix
154 is provided that is greater than or equal to the number of existing values.</t>
155 <t>See the examples in the next section.</t>
158 <section title="Examples">
159 <section title="Sample Schema">
160 <t>This schema is used for all of the examples:</t>
161 <t>( EXAMPLE_AT.1 NAME 'olcDatabase'<vspace/>
162 EQUALITY caseIgnoreMatch<vspace/>
163 SYNTAX 1.3.6.1.4.1.1466.115.121.1.15<vspace/>
164 SINGLE-VALUE X-ORDERED 'SIBLINGS' )</t>
165 <t>( EXAMPLE_AT.2 NAME 'olcSuffix'<vspace/>
166 EQUALITY distinguishedNameMatch<vspace/>
167 SYNTAX 1.3.6.1.4.1.1466.115.121.1.12<vspace/>
168 X-ORDERED 'VALUES' )</t>
169 <t>( EXAMPLE_OC.1 NAME 'olcDatabaseConfig' <vspace/>
170 SUP top STRUCTURAL<vspace/>
171 MAY ( olcDatabase $ olcSuffix ) )</t>
173 <section title="Ordered Values">
174 <t>Given this entry:</t>
175 <t>dn: olcDatabase={1}bdb,cn=config<vspace/>
176 olcDatabase: {1}bdb<vspace/>
177 objectClass: olcDatabaseConfig<vspace/>
178 olcSuffix: {0}dc=example,dc=com<vspace/>
179 olcSuffix: {1}o=example.com<vspace/>
180 olcSuffix: {2}o=The Example Company<vspace/>
181 olcSuffix: {3}o=example,c=us</t>
183 <t>We can perform these Modify operations:
184 <list style="numbers">
186 <t>dn: olcDatabase={1}bdb,cn=config<vspace/>
187 changetype: modify<vspace/>
188 delete: olcSuffix<vspace/>
189 olcSuffix: {0}<vspace/>
191 This operation deletes the first olcSuffix, regardless of its
192 value. All other values are bumped up one position. The olcSuffix
193 attribute will end up containing:<vspace/>
194 olcSuffix: {0}o=example.com<vspace/>
195 olcSuffix: {1}o=The Example Company<vspace/>
196 olcSuffix: {2}o=example,c=us</t>
198 <t>Starting from the original entry, we could issue this change
200 delete: olcSuffix<vspace/>
201 olcSuffix: o=example.com<vspace/>
203 This operation deletes the olcSuffix that matches the value,
204 regardless of its ordering-prefix. The olcSuffix attribute will contain:<vspace/>
205 olcSuffix: {0}dc=example,dc=com<vspace/>
206 olcSuffix: {1}o=The Example Company<vspace/>
207 olcSuffix: {2}o=example,c=us</t>
209 <t>Again, starting from the original entry, we could issue this
211 delete: olcSuffix<vspace/>
212 olcSuffix: {2}o=The Example Company<vspace/>
214 Here both the ordering-prefix and the value must match, otherwise
215 the Modify would fail with noSuchAttribute. In this case the
216 olcSuffix attribute results in:<vspace/>
217 olcSuffix: {0}dc=example,dc=com<vspace/>
218 olcSuffix: {1}o=example.com<vspace/>
219 olcSuffix: {2}o=example,c=us</t>
221 <t>Adding a new value without an ordering-prefix simply appends:<vspace/>
222 add: olcSuffix<vspace/>
223 olcSuffix: o=example.org<vspace/>
225 The resulting attribute would be:<vspace/>
226 olcSuffix: {0}dc=example,dc=com<vspace/>
227 olcSuffix: {1}o=example.com<vspace/>
228 olcSuffix: {2}o=The Example Company<vspace/>
229 olcSuffix: {3}o=example,c=us<vspace/>
230 olcSuffix: {4}o=example.org</t>
232 <t>Adding a new value with an ordering-prefix inserts into the
233 specified position:<vspace/>
234 add: olcSuffix<vspace/>
235 olcSuffix: {0}o=example.org<vspace/>
237 The resulting attribute would be:<vspace/>
238 olcSuffix: {0}o=example.org<vspace/>
239 olcSuffix: {1}dc=example,dc=com<vspace/>
240 olcSuffix: {2}o=example.com<vspace/>
241 olcSuffix: {3}o=The Example Company<vspace/>
242 olcSuffix: {4}o=example,c=us</t>
244 <t>Modifying multiple values in one operation:<vspace/>
245 add: olcSuffix<vspace/>
246 olcSuffix: {0}ou=Dis,o=example.com<vspace/>
247 olcSuffix: {0}ou=Dat,o=example,com<vspace/>
249 delete: olcSuffix:<vspace/>
250 olcSuffix: {2}<vspace/>
251 olcSuffix: {1}<vspace/>
253 The resulting attribute would be:<vspace/>
254 olcSuffix: {0}ou=Dat,o=example,com<vspace/>
255 olcSuffix: {1}dc=example,dc=com<vspace/>
256 olcSuffix: {2}o=example.com<vspace/>
257 olcSuffix: {3}o=The Example Company<vspace/>
258 olcSuffix: {4}o=example,c=us</t>
260 <t>If the Adds and Deletes in the previous example were done
261 in the opposite order:<vspace/>
262 delete: olcSuffix:<vspace/>
263 olcSuffix: {2}<vspace/>
264 olcSuffix: {1}<vspace/>
266 add: olcSuffix<vspace/>
267 olcSuffix: {0}ou=Dis,o=example.com<vspace/>
268 olcSuffix: {0}ou=Dat,o=example,com<vspace/>
270 The result would be:<vspace/>
271 olcSuffix: {0}ou=Dat,o=example,com<vspace/>
272 olcSuffix: {1}ou=Dis,o=example.com<vspace/>
273 olcSuffix: {2}o=example.org<vspace/>
274 olcSuffix: {3}o=The Example Company<vspace/>
275 olcSuffix: {4}o=example,c=us</t>
279 <t>Note that matching against an ordering-prefix can also
280 be done in Compare operations and Search filters. E.g.,
281 the filter "(olcSuffix={4})" would match all entries with
282 at least 5 olcSuffix values.</t>
284 <section title="Ordered Siblings">
285 <t>The rules for Ordered Siblings are basically the same
286 as for Ordered Values, except instead of working primarily with the Modify
287 request, the operations of interest here are Add, Delete, and ModRDN.</t>
288 <t>Given these entries:</t>
289 <t>dn: olcDatabase={0}config,cn=config<vspace/>
290 olcDatabase: {0}config<vspace/>
291 objectClass: olcDatabaseConfig<vspace/>
292 olcSuffix: {0}cn=config</t>
294 <t>dn: olcDatabase={1}bdb,cn=config<vspace/>
295 olcDatabase: {1}bdb<vspace/>
296 objectClass: olcDatabaseConfig<vspace/>
297 olcSuffix: {0}dc=example,dc=com</t>
299 <t>We can perform these operations:
300 <list style="numbers">
301 <t>Add a new entry with no ordering-prefix:<vspace/>
302 dn: olcDatabase=hdb,cn=config<vspace/>
303 changetype: add<vspace/>
304 olcDatabase: hdb<vspace/>
305 objectClass: olcDatabaseConfig<vspace/>
306 olcSuffix: {0}dc=example,dc=org<vspace/>
307 The resulting entry will be:<vspace/>
308 dn: olcDatabase={2}hdb,cn=config<vspace/>
309 olcDatabase: {2}hdb<vspace/>
310 objectClass: olcDatabaseConfig<vspace/>
311 olcSuffix: {0}dc=example,dc=org</t>
313 <t>Continuing on with these three entries, we can add another
314 entry with a specific ordering-prefix:<vspace/>
315 dn: olcDatabase={1}ldif,cn=config<vspace/>
316 changetype: add<vspace/>
317 olcDatabase: {1}ldif<vspace/>
318 objectClass: olcDatabaseConfig<vspace/>
319 olcSuffix: {0}o=example.com<vspace/>
320 <vspace/>This would give us four entries, whose DNs are:
322 <t>dn: olcDatabase={0}config,cn=config</t>
323 <t>dn: olcDatabase={1}ldif,cn=config</t>
324 <t>dn: olcDatabase={2}bdb,cn=config</t>
325 <t>dn: olcDatabase={3}hdb,cn=config</t>
329 <t>Issuing a ModRDN request will cause multiple entries to
331 dn: olcDatabase={1}ldif,cn=config<vspace/>
332 changetype: modrdn<vspace/>
333 newrdn: olcDatabase={99}ldif<vspace/>
334 deleteoldrdn: 1<vspace/>
335 <vspace/>The resulting entries would be named:
337 <t>dn: olcDatabase={0}config,cn=config</t>
338 <t>dn: olcDatabase={1}bdb,cn=config</t>
339 <t>dn: olcDatabase={2}hdb,cn=config</t>
340 <t>dn: olcDatabase={3}ldif,cn=config</t>
344 <t>As may be expected, a Delete request will also rename the
345 remaining entries:<vspace/>
346 dn: olcDatabase={1}bdb,cn=config<vspace/>
347 changetype: delete<vspace/>
348 <vspace/>The remaining entries would be named:
350 <t>dn: olcDatabase={0}config,cn=config</t>
351 <t>dn: olcDatabase={1}hdb,cn=config</t>
352 <t>dn: olcDatabase={2}ldif,cn=config</t>
360 <section title="Security Considerations">
361 <t>General LDAP security considerations <xref target="RFC3377"/>
367 <references title="Normative References">
372 <reference anchor="X680">
374 <title>Abstract Syntax Notation One (ASN.1): Specification of basic notation</title>
376 <organization>International Telecommunications Union</organization>
378 <date month="July" year="2002"/>
380 <seriesInfo name="ITU-T" value="Recommendation X.680"/>
384 <section title="IANA Considerations">
385 <t>In accordance with <xref target="RFC3383"/> (what needs to be done here?) . We probably need an OID for advertising in supportedFeatures.