git.sur5r.net Git - openldap/blob - doc/drafts/draft-chu-ldap-xordered-xx.xml

   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'>
  12
  13 ]>
  14 <?xml-stylesheet type='text/xsl' href='http://www.greenbytes.de/tech/webdav/rfc2629.xslt' ?>
  15 <?rfc toc="yes" ?>
  16 <?rfc tocdepth="2" ?>
  17 <?rfc tocindent="no" ?>
  18 <?rfc symrefs="yes" ?>
  19 <?rfc sortrefs="yes"?>
  20 <?rfc iprnotified="no" ?>
  21 <?rfc strict="yes" ?>
  22 <rfc ipr="full3978" docName="draft-chu-ldap-xordered-00.txt">
  23         <front>
  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>
  27                         <address>
  28                                 <postal>
  29                                         <street>18740 Oxnard Street, Suite 313A</street>
  30                                         <city>Tarzana</city>
  31                                         <region>California</region>
  32                                         <code>91356</code>
  33                                         <country>USA</country>
  34                                 </postal>
  35                                 <phone>+1 818 757-7087</phone>
  36                                 <email>hyc@symas.com</email>
  37                         </address>
  38                 </author>
  39                 <date year="2006" month="May"/>
  40                 <abstract>
  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>
  48                 </abstract>
  49         </front>
  50
  51         <middle>
  52
  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
  68 ordered values.</t>
  69                 </section>
  70
  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>
  74                 </section>
  75
  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>
  92                 <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.
 105                 </t>
 106                         </section>
 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"/>.
 111         <list style="empty">
 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 = &lt;any sequence of octets&gt;</t>
 116         <t>ordered-value = ordering-prefix value</t>
 117         </list></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>
 127                 </section>
 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:
 135         <list>
 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>
 143         </list></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
 146 ordering-prefix.</t>
 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>
 156                         </section>
 157                 </section>
 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>
 172                         </section>
 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>
 182
 183                         <t>We can perform these Modify operations:
 184                         <list style="numbers">
 185
 186                         <t>dn: olcDatabase={1}bdb,cn=config<vspace/>
 187                         changetype: modify<vspace/>
 188                         delete: olcSuffix<vspace/>
 189                         olcSuffix: {0}<vspace/>
 190                         -<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>
 197
 198                         <t>Starting from the original entry, we could issue this change
 199                         instead:<vspace/>
 200                         delete: olcSuffix<vspace/>
 201                         olcSuffix: o=example.com<vspace/>
 202                         -<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>
 208
 209                         <t>Again, starting from the original entry, we could issue this
 210                         change:<vspace/>
 211                         delete: olcSuffix<vspace/>
 212                         olcSuffix: {2}o=The Example Company<vspace/>
 213                         -<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>
 220
 221                         <t>Adding a new value without an ordering-prefix simply appends:<vspace/>
 222                         add: olcSuffix<vspace/>
 223                         olcSuffix: o=example.org<vspace/>
 224                         -<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>
 231
 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/>
 236                         -<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>
 243
 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/>
 248                         -<vspace/>
 249                         delete: olcSuffix:<vspace/>
 250                         olcSuffix: {2}<vspace/>
 251                         olcSuffix: {1}<vspace/>
 252                         -<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>
 259
 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/>
 265                         -<vspace/>
 266                         add: olcSuffix<vspace/>
 267                         olcSuffix: {0}ou=Dis,o=example.com<vspace/>
 268                         olcSuffix: {0}ou=Dat,o=example,com<vspace/>
 269                         -<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>
 276                         </list>
 277
 278                         </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>
 283                         </section>
 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>
 293
 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>
 298
 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>
 312
 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:
 321                         <list style="empty">
 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>
 326                         </list>
 327                         </t>
 328
 329                         <t>Issuing a ModRDN request will cause multiple entries to
 330                         be renamed:<vspace/>
 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:
 336                         <list style="empty">
 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>
 341                         </list>
 342                         </t>
 343
 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:
 349                         <list style="empty">
 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>
 353                         </list>
 354                         </t>
 355                         </list>
 356                         </t>
 357                         </section>
 358
 359                 </section>
 360                 <section title="Security Considerations">
 361                 <t>General LDAP security considerations <xref target="RFC3377"/>
 362                 apply.</t>
 363                 </section>
 364         </middle>
 365
 366         <back>
 367                 <references title="Normative References">
 368                         &rfc2119;
 369                         &rfc2252;
 370                         &rfc3377;
 371                         &rfc3383;
 372                         <reference anchor="X680">
 373                                 <front>
 374                                         <title>Abstract Syntax Notation One (ASN.1): Specification of basic notation</title>
 375                                         <author>
 376                                                 <organization>International Telecommunications Union</organization>
 377                                         </author>
 378                                         <date month="July" year="2002"/>
 379                                 </front>
 380                                 <seriesInfo name="ITU-T" value="Recommendation X.680"/>
 381                         </reference>
 382                 </references>
 383
 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.
 386                         </t>
 387
 388                 </section>
 389         </back>
 390 </rfc>