idnits 2.17.1 draft-ietf-conneg-feature-algebra-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 36 longer pages, the longest (page 2) being 60 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([2], [3], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (7 August 1998) is 9365 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '0' is mentioned on line 1139, but not defined == Unused Reference: '12' is defined on line 1752, but no explicit reference was found in the text == Unused Reference: '15' is defined on line 1770, but no explicit reference was found in the text == Unused Reference: '16' is defined on line 1777, but no explicit reference was found in the text == Unused Reference: '17' is defined on line 1783, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' ** Obsolete normative reference: RFC 2251 (ref. '7') (Obsoleted by RFC 4510, RFC 4511, RFC 4512, RFC 4513) ** Obsolete normative reference: RFC 2254 (ref. '8') (Obsoleted by RFC 4510, RFC 4515) ** Obsolete normative reference: RFC 2068 (ref. '9') (Obsoleted by RFC 2616) ** Obsolete normative reference: RFC 2234 (ref. '10') (Obsoleted by RFC 4234) -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' -- Possible downref: Non-RFC (?) normative reference: ref. '16' -- Possible downref: Non-RFC (?) normative reference: ref. '17' Summary: 13 errors (**), 0 flaws (~~), 8 warnings (==), 15 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF media feature registration WG Graham Klyne 3 Internet draft Content Technologies/5GM 4 7 August 1998 5 Expires: February 1999 7 An algebra for describing media feature sets 8 10 Status of this memo 12 This document is an Internet-Draft. Internet-Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its areas, 14 and its working groups. Note that other groups may also distribute 15 working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six 18 months and may be updated, replaced, or obsoleted by other 19 documents at any time. It is inappropriate to use Internet-Drafts 20 as reference material or to cite them other than as ``work in 21 progress''. 23 To view the entire list of current Internet-Drafts, please check 24 the "1id-abstracts.txt" listing contained in the Internet-Drafts 25 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 26 (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 27 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US 28 West Coast). 30 Copyright (C) 1998, The Internet Society 32 Abstract 34 A number of Internet application protocols have a need to provide 35 content negotiation for the resources with which they interact [1]. 36 A framework for such negotiation is described in [2]. Part of this 37 framework is a way to describe the range of media features which 38 can be handled by the sender, recipient or document transmission 39 format of a message. A format for a vocabulary of individual media 40 features and procedures for registering media features are 41 presented in [3]. 43 This document describes an algebra and syntax that can be used to 44 define feature sets which are formed from combinations and 45 relations involving individual media features. Such feature sets 46 are used to describe the media feature handling capabilities of 47 message senders, recipients and file formats. 49 This document also outlines an algorithm for feature set matching. 51 Internet draft 5 August 1998 52 An algebra for describing media feature sets 54 Table of contents 56 1. Introduction.............................................3 57 1.1 Structure of this document ...........................4 58 1.2 Discussion of this document ..........................4 59 1.3 Amendment history ....................................5 60 1.4 Unfinished business ..................................5 61 2. Terminology and definitions..............................6 62 3. Media feature values.....................................6 63 3.1 Complexity of feature algebra ........................7 64 3.2 Sufficiency of simple types ..........................7 65 3.2.1 Unstructured data types..........................8 66 3.2.2 Cartesian product................................8 67 3.2.3 Discriminated union..............................8 68 3.2.4 Array............................................9 69 3.2.5 Powerset.........................................9 70 3.2.6 Sequence.........................................9 71 4. Feature set predicates...................................10 72 4.1 An algebra for data file format selection ............11 73 4.1.1 Describing feature sets..........................12 74 4.1.1.1 Feature value ranges 12 75 4.1.1.2 Feature value combinations 13 76 4.1.1.3 Using meta-features to group features 14 77 4.1.2 Content, sender and recipient capabilities.......15 78 4.2 Conclusion and proposal ..............................15 79 5. Indicating preferences...................................16 80 5.1 Combining preferences ................................16 81 5.2 Representing preferences .............................17 82 6. Feature set representation...............................18 83 6.1 Textual representation of predicates .................19 84 6.2 Named and auxiliary predicates .......................21 85 6.2.1 Defining a named predicate.......................21 86 6.2.2 Invoking named predicates........................22 87 6.2.3 Auxiliary predicates in a filter.................22 88 6.3 Feature set definition examples ......................22 89 6.3.1 Single predicate.................................22 90 6.3.2 Predicate with auxiliary predicate...............23 91 6.4 ASN.1 representation .................................24 92 7. Content negotiation protocol processing..................24 93 7.1 Matching feature sets ................................24 94 7.1.1 Feature set matching strategy....................26 95 7.1.2 Formulating the problem..........................27 96 7.1.3 Replace set expressions..........................27 97 7.1.4 Replace comparisons and logical negations........27 98 7.1.5 Conversion to canonical form.....................29 99 7.1.6 Grouping of feature predicates...................30 100 7.1.7 Merge single-feature constraints.................30 101 7.1.7.1 Rules for simplifying ordered values 30 102 7.1.7.2 Rules for simplifying unordered values 31 103 7.2 Effect of named predicates ...........................32 105 Internet draft 5 August 1998 106 An algebra for describing media feature sets 108 7.3 Unit designations ....................................32 109 7.4 Unknown feature value data types .....................33 110 7.5 Worked example .......................................33 111 7.6 Algorithm source code ................................33 112 8. Security considerations..................................33 113 9. Copyright................................................35 114 10. Acknowledgements........................................35 115 11. References..............................................36 116 12. Author's address........................................38 118 1. Introduction 120 A number of Internet application protocols have a need to provide 121 content negotiation for the resources with which they interact [1]. 122 A framework for such negotiation is described in [2]. A part of 123 this framework is a way to describe the range of media features 124 which can be handled by the sender, recipient or document 125 transmission format of a message. 127 Descriptions of media feature capabilities need to be based upon 128 some underlying vocabulary of individual media features. A format 129 for such a vocabulary and procedures for registering media features 130 are presented in [3]. 132 This document defines an algebra which can be used to describe 133 feature sets which are formed from combinations and relations 134 involving individual media features. Such feature sets are used to 135 describe the media handling capabilities of message senders, 136 recipients and file formats. 138 This document also outlines a syntax for describing feature sets, 139 and an algorithm for feature set matching. 141 The feature set algebra is built around the principle of using 142 feature set predicates as "mathematical relations" which define 143 constraints on feature handling capabilities. The idea is that the 144 same form of feature set expression can be used to describe sender, 145 receiver and file format capabilities. This has been loosely 146 modelled on the way that the Prolog programming language uses Horn 147 Clauses to describe a set of result values. 149 In developing the algebra, examples are given using notation drawn 150 from the Prolog programming language. Later, a syntax for 151 expressing feature predicates is suggested, based on LDAP search 152 filters. Finally, an algorithm for feature set matching is 153 described. 155 Internet draft 5 August 1998 156 An algebra for describing media feature sets 158 1.1 Structure of this document 160 The main part of this draft addresses the following main areas: 162 Section 2 introduces and references some terms which are used with 163 special meaning. 165 Section 3 discusses constraints on the data types allowed for 166 individual media feature values. 168 Section 4 introduces and describes the algebra used to construct 169 feature set descriptions with expressions containing media 170 features. The first part of this section contains a development of 171 the ideas, and the second part contains the conclusions and 172 proposed algebra. 174 Section 5 introduces and describes extensions to the algebra for 175 indicating preferences between different feature sets. 177 Section 6 contains a description of recommended representations for 178 describing feature sets based on the previously-described algebra. 180 Section 7 discusses some feature-related protocol processing 181 issues, including a description of an algorithm for feature set 182 matching. 184 1.2 Discussion of this document 186 Discussion of this document should take place on the content 187 negotiation and media feature registration mailing list hosted by 188 the Internet Mail Consortium (IMC): 190 Please send comments regarding this document to: 192 ietf-medfree@imc.org 194 To subscribe to this list, send a message with the body 'subscribe' 195 to "ietf-medfree-request@imc.org". 197 To see what has gone on before you subscribed, please see the 198 mailing list archive at: 200 http://www.imc.org/ietf-medfree/ 202 1.3 Amendment history 204 00a 11-Mar-1998 205 Document initially created. 207 Internet draft 5 August 1998 208 An algebra for describing media feature sets 210 01a 05-May-1998 211 Mainly-editorial revision of sections describing the 212 feature types and algebra. Added section on indicating 213 preferences. Added section describing feature predicate 214 syntax. Added to security considerations (based on fax 215 negotiation scenarios draft). 217 01b 25-Jun-1998 218 New Internet draft boilerplate in 'status' preface. 219 Review and rationalization of sections on feature 220 combinations. Added numeric expressions, named 221 predicates and auxiliary predicates as options in the 222 syntax. Added examples of text string predicate 223 representation. 225 02a 08-Jul-1998 226 Added chapter on protocol processing considerations, and 227 in particular outlined an algorithm for feature set 228 matching. Added restrictions to the form of arithmetic 229 expression to allow deterministic feature set matching. 231 03a 27-Jul-1998 232 Simplified feature set handling by removing options for 233 expressions on the RHS of feature comparison expressions. 234 Syntax elements have been added as placeholders for 235 possible future extensions in this area; examples have 236 been adjusted accordingly, and the feature set matching 237 algorithm greatly simplified. Add simple unit 238 designations. 240 1.4 Unfinished business 242 . Array values: are they needed? (section 3.2.4) 244 . Discuss determination of qvalues in the feature set matching 245 algorithm. 247 . Use of unknown data types for feature values (section 7.3) 249 . Add source code for feature matching implementation. 251 . Should ASN.1 representation be pursued? If so, should it be 252 aligned with LDAP filter representation? (section 6.5) 254 Internet draft 5 August 1998 255 An algebra for describing media feature sets 257 2. Terminology and definitions 259 Feature Collection 260 is a collection of different media features and 261 associated values. This might be viewed as describing a 262 specific rendering of a specific instance of a document 263 or resource by a specific recipient. 265 Feature Set 266 is a set of zero, one or more feature collections. 268 Feature set predicate 269 A function of an arbitrary feature collection value which 270 returns a Boolean result. A TRUE result is taken to mean 271 that the corresponding feature collection belongs to some 272 set of media feature handling capabilities defined by 273 this predicate. 275 Other terms used in this draft are defined in [2]. 277 3. Media feature values 279 This document assumes that individual media feature values are 280 simple atomic values: 282 . Boolean values 284 . Enumerated values 286 . Text string values (treated as atomic entities, like enumerated 287 value tokens). 289 . Numeric values 291 More complex media feature values might be accommodated, but they 292 would (a) be undesirable because they would complicate the algebra, 293 and (b) are not necessary. 295 These statements are justified in the following sub-sections. 297 NOTE 299 The following sub-sections are not part of the algebraic 300 framework description, and may be skipped by readers not 301 concerned with design rationale. 303 Internet draft 5 August 1998 304 An algebra for describing media feature sets 306 3.1 Complexity of feature algebra 308 Statement (a) above is justified as follows: predicates constructed 309 as expressions containing media feature values must ultimately 310 resolve to a logical combination of feature value tests. 312 A full range of simple tests for all of the data types listed above 313 can be performed based on just two fundamental operations: equality 314 and less-than. All other meaningful tests can be constructed as 315 predicates incorporating these two basic tests. 317 For example: 318 ( a != b ) iff !( a == b ) 319 ( a <= b ) iff !( b < a ) 320 ( a > b ) iff ( b < a ) 321 ( a >= b ) iff !( a < b ) 323 If additional (composite) data types are introduced, then 324 additional operators must be introduced to test their component 325 parts: the addition of just one further comparison operator 326 increases the number of such operators by 50%. 328 3.2 Sufficiency of simple types 330 To justify statement (b), let us first review the range of 331 composite data types that might reasonably be considered. 333 In 1972, a paper "Notes on data structuring" by C. A. R. Hoare was 334 published in the book "Structured Programming" [4]. This was an 335 early formalization of data types used in programming languages, 336 and its content has formed a sufficient basis for describing the 337 data types in almost every programming language which has been 338 developed. This gives good grounds to believe that the type 339 framework is also sufficient for media features. 341 The data types covered by Hoare's paper are: 343 . Unstructured data types: (integer, real, enumeration, ordered 344 enumeration, sub-ranges). 346 . Cartesian product (e.g. C 'struct'). 348 . Discriminated union (e.g. C 'union'). 350 . Array. 352 . Powerset (e.g. Pascal 'SET OF'). 354 . Sequence (e.g. C string, Pascal 'FILE OF'). 356 Internet draft 5 August 1998 357 An algebra for describing media feature sets 359 To demonstrate sufficiency of simple types for media features we 360 must show that the feature-set defining properties of these 361 composite types can be captured using predicates on the simple 362 types described previously. 364 3.2.1 Unstructured data types 366 The unstructured data types noted correspond closely to, and can be 367 represented by the proposed simple value types for media features. 369 3.2.2 Cartesian product 371 A Cartesian product value (e.g. resolution=[x,y]) is easily 372 captured as a collection of two or more separately named media 373 features (e.g. x-resolution=x, y-resolution=y). 375 3.2.3 Discriminated union 377 A discriminated union value is an either/or type of choice. For 378 example, a given workstation might be able to display 16K colours 379 at 1024x768 resolution, OR 256 colours at 1280x1024 resolution. 381 These possibilities are captured by a logical-OR of predicates: 382 ( ( x-resolution <= 1024 ) && 383 ( y-resolution <= 768 ) && 384 ( colours <= 16384 ) ) || 385 ( ( x-resolution <= 1280 ) && 386 ( y-resolution <= 1024 ) && 387 ( colours <= 256 ) ) 389 3.2.4 Array 391 An array represents a mapping from one data type to another. For 392 example, the availability of pens in a pen plotter might be 393 represented by an array which maps a pen number to a colour. 395 If the array index which forms the basis for defining a feature set 396 is assumed to be a constant, then each member can be designated by 397 a feature name which incorporates the index value. For example: 398 Pen-1=black, pen-2=red, etc. 400 Another example where an array might describe a media feature is a 401 colour palette: an array is used to associate a colour value (in 402 terms of RGB or some other colour model) with a colour index value. 403 In this case is possible to envisage a requirement for a particular 404 colour to be loaded in the palette without any knowledge of the 405 index which maps to it. 407 Internet draft 5 August 1998 408 An algebra for describing media feature sets 410 In this case, the colour might be treated as a named Boolean 411 attribute: if TRUE then that colour is deemed to be available in 412 the palette 414 Feature selection based on a variable array index is more 415 difficult, but it is believed that this is not required for media 416 selection. 418 [[I cannot think of any example of feature selection which involves 419 a variable index into an array. If such a feature is presented, an 420 array type could be added to the set of allowable media feature 421 types, and an array selection operator added to the algebra.]] 423 3.2.5 Powerset 425 A powerset is a collection of zero, one or more values from some 426 base set of values. A colour palette may be viewed as a powerset 427 of colour values, or the fonts available in a printer as a powerset 428 of all available fonts. 430 A powerset is very easily represented by a separate Boolean-valued 431 feature for each member of the base set. The value TRUE indicates 432 that the corresponding value is a member of the powerset value. 434 3.2.6 Sequence 436 A sequence is a list of values from some base set of values, which 437 are accessed sequentially. 439 A sequence can be modelled by an array if one assumes integer index 440 values starting at (say) 1 and incrementing by 1 for each 441 successive element of the sequence. 443 Thus, the considerations described above relating to array values 444 can be considered as also applying (in part) to sequence values. 445 That is, if arrays are deemed to be adequately handled, then 446 sequence values too can be handled. 448 4. Feature set predicates 450 A model for data file selection is proposed, based on relational 451 set definition and subset selection, using elements of the Prolog 452 programming language [5] as a descriptive notation for this 453 purpose. 455 NOTE 457 The use of Prolog as a syntax for feature description is 458 NOT being proposed; rather, the Prolog-like notation is 460 Internet draft 5 August 1998 461 An algebra for describing media feature sets 463 used to develop the semantics of an algebra. These 464 semantics could be mapped to any convenient syntax. 466 For the purposes of developing this algebra, examples are drawn 467 from the media features described in "Media Features for Display, 468 Print, and Fax" [6], which in summary are: 470 pix-x=n (Image size, in pixels) 471 pix-y=m 473 res-x=n (Image resolution, pixels per inch) 474 res-y=m 476 media= screen/screen-paged/stationary/transparency/ 477 envelope/envelope-plain/envelope-window/ 478 continuous-long/continuous-short 479 tab-stock/multi-part-form/labels/multi-layer 480 papersize= na-letter|iso-A4|iso-B4|iso-A3|na-legal 482 color=n (Colour depth in bits) 483 grey=n (Grey scale depth in bits) 485 tiff=S/F/J/C/L/M 487 4.1 An algebra for data file format selection 489 The basic idea proposed here is that a feature capability of the 490 original content, sender, data file format or recipient is 491 represented as a predicate applied to a collection of feature 492 values. Under universal quantification (i.e. selecting all 493 possible values that satisfy it), a predicate indicates a range of 494 possible combinations of feature values). 496 This idea is inherent in Prolog clause notation, which is used in 497 the example below to describe a predicate 498 'acceptable_file_format(File)', which yields a set of possible file 499 transfer formats, using other predicates which indicate the file 500 formats available to the sender and feature capabilities of the 501 file format, original content: 503 acceptable_file_format(File) :- 504 sender_available_file_format(File), 505 match_format(File). 507 (Read this statement as: 'File' is an acceptable file format IF it 508 is a format available to the sender AND it matches the requirements 509 defined by 'match_format'.) 511 match_format(File) :- 512 pix_x(File,Px), content_pix_x(Px), recipient_pix_x(Px), 514 Internet draft 5 August 1998 515 An algebra for describing media feature sets 517 pix_y(File,Py), content_pix_x(Py), recipient_pix_y(Py), 518 res_x(File,Rx), content_res_x(Rx), recipient_res_x(Rx), 519 res_y(File,Ry), content_res_y(Ry), recipient_res_y(Ry), 520 colour(File,C), content_colour(C), recipient_colour(C), 521 grey(File,G), content_grey(G), recipient_grey(G), 522 ua_media(File,M), 523 content_ua_media(M), 524 recipient_ua_media(M), 525 papersize(File,P), 526 content_papersize(P), 527 recipient_papersize(P). 529 (Read this as: 'File' satisfies the constraints of 'match_format' 530 IF there is some 'pix_x' feature value 'Px' that is supported by 531 the file format AND is suitable for representing the message 532 content to be sent AND can be displayed by the message recipient, 533 AND there is some 'pix_y' feature ...) 535 Essentially, 'acceptable_file_format' selects a set of file 536 transfer formats from those available (as defined by 537 'sender_available_file_format'), choosing any whose feature 538 capabilities have a non-empty intersection with the feature 539 capabilities of the original content and the recipient. 541 4.1.1 Describing feature sets 543 The above framework suggests file format capabilities are described 544 as enumerated feature sets. As an abstract theory, this works fine 545 but for practical use it has a couple of problems: 547 (a) description of features with a large number of possibilities 549 (b) describing features which are supported in specific 550 combinations 552 A typical case of (a) would be where a feature (e.g. size of image 553 in pixels) can take any value from a range. To present and test 554 each value separately is not a practical proposition, even if it 555 were possible. (A guide here as to what constitutes a practical 556 approach is to make a judgement about the feasibility of writing 557 the corresponding Prolog program.) 559 A typical case of (b) would be where different values for certain 560 features can occur only in combinations (e.g. allowable 561 combinations of resolution and colour depth on a given video 562 display). If the features are treated independently as suggested 563 by the framework above, all possible combinations would be allowed, 564 rather than the specifically allowable combinations. 566 Internet draft 5 August 1998 567 An algebra for describing media feature sets 569 4.1.1.1 Feature value ranges 571 The first issue can be addressed by considering the type of value 572 which can represent the allowed features of a data file format. 573 The features of a specific data file are represented as values from 574 an enumeration (e.g. ua_media, papersize), or a numeric values 575 (integer or rational). The description of allowable file format 576 feature needs to represent all the allowable values. 578 The Prolog clauses used above to describe file format features 579 already allow for multiple enumerated values. Each acts as a 580 mathematical relation to select a subset of the set of file values 581 allowed by the preceding predicates. 583 Section 3 of this document describes proposed media feature value 584 types. 586 For numeric feature values, a sequence of two numbers to represent 587 a closed interval is suggested, where either value may be replaced 588 by an empty list to indicate no limiting value. Thus: 590 [m,n] => { x : m <= x <= n } 591 [m,[]] => { x : m <= x } 592 [[],n] => { x : x <= n } 594 The following Prolog could be used to describe such range matching: 596 feature_match(X,[[],[]]). 597 feature_match(X,[L,[]]) :- L <= X. 598 feature_match(X,[[],H]) :- X <= H. 599 feature_match(X,[L,H]) :- L <= X, X <= H. 600 feature_match(X,X). 602 (This example stretches standard Prolog, which does not support 603 non-integer numbers. The final clause allows 'feature_match' to 604 deal with equality matching for the normal enumerated and text 605 string value case.) 607 Similar constructs might be used with enumeration-valued and 608 string-values features for which an ordering relationship is 609 defined. 611 4.1.1.2 Feature value combinations 613 The approach to representing allowed combinations of feature values 614 presented here is to use additional predicates to describe 615 relationship constraints between them. 617 Internet draft 5 August 1998 618 An algebra for describing media feature sets 620 For example, consider a display capable of handling any x- and y- 621 resolution between 72dpi and 600dpi. This might be represented by 622 the constraint clauses: 624 feature_match(Rx,[75,600]), 625 feature_match(Ry,[75,600]) 627 If x- and y- resolutions are to be further constrained to specific 628 related values, the following additional predicate clause might be 629 added to the feature set description: 631 feature_match(Rx,75), feature_match(Ry,75) ; 632 feature_match(Rx,75), feature_match(Ry,150) ; 633 feature_match(Rx,150), feature_match(Ry,150) ; 634 feature_match(Rx,150), feature_match(Ry,300) ; 635 feature_match(Rx,300), feature_match(Ry,300) ; 636 feature_match(Rx,300), feature_match(Ry,600) ; 637 feature_match(Rx,600), feature_match(Ry,600) 639 (Here, 'a;b' denotes 'a' OR 'b'.) 641 Another example might be a display which supports 640x480, 800x600 642 and 1024x768 image pixel sizes: 644 ( ( feature_match(Px,640), feature_match(Py,480) ) ; 645 ( feature_match(Px,600), feature_match(Py,800) ) ; 646 ( feature_match(Px,1024), feature_match(Py,768) ) ) 648 This is based on the predicates 'pix_x(File,Px)', 'pix_y(File,Py)', 649 'res_x(File,Rx)' and 'res_y(File,Ry)' from the initial framework 650 above.) 652 4.1.1.3 Using meta-features to group features 654 The expression of feature combinations can sometimes be simplified 655 by introducing "meta-features", or auxiliary predicates, to 656 describe relationship constraints between feature values. 658 Developing the previous examples, given: 660 pix_x(File,Px), 661 pix_y(File,Py), 662 res_x(File,Rx), 663 res_y(File,Ry), 665 We can define meta-features 'pix' and 'res': 667 pix(File,[Px,Py]) :- pix_x(File,Px), pix_y(File,Py). 668 res(File,[Rx,Ry]) :- res_x(File,Rx), res_y(File,Ry). 670 Internet draft 5 August 1998 671 An algebra for describing media feature sets 673 Then the additional constraints: 675 pix(File,[640, 480]). 676 pix(File,[800, 600]). 677 pix(File,[1024,768]). 679 serve to define three allowable pixel image sizes, and: 681 res(File,[Rx,Ry]) :- 682 feature_match(Rx,75), feature_match(Ry,75) ; 683 feature_match(Rx,75), feature_match(Ry,150) ; 684 feature_match(Rx,150), feature_match(Ry,150) ; 685 feature_match(Rx,150), feature_match(Ry,300) ; 686 feature_match(Rx,300), feature_match(Ry,300) ; 687 feature_match(Rx,300), feature_match(Ry,600) ; 688 feature_match(Rx,600), feature_match(Ry,600) 690 serves to represent the allowable resolutions described in the 691 previous section. 693 4.1.2 Content, sender and recipient capabilities 695 It has been shown that feature set predicates can be used to 696 describe the capabilities of a particular content file format, and 697 also to represent constraints of feature value combinations. 699 This use of feature predicates is equally applicable to describing 700 the feature handling capabilities of senders, recipients and other 701 entities involved in message transmission. 703 4.2 Conclusion and proposal 705 The previous sections show that file format capabilities can be 706 described by feature set predicates: arbitrary logical expressions 707 using AND, OR, NOT logical combining operators, and media feature 708 value matching. Data file features, original content features, 709 sender features and recipient features (and user features) can all 710 be represented in this way. 712 A key insight, which points to this conclusion, is that a 713 collection of feature values can be viewed as describing a specific 714 representation of the content of a specific document (for example, 715 when rendered by a given recipient). The capabilities that we wish 716 to describe, be they sender, file format, recipient or other 717 capabilities, are sets of such feature collections, with the 718 potential to be displayed using any of the feature value 719 collections in the set. 721 This raises a terminology problem, because the term "feature set" 722 can be used to mean a collection of specific feature values and a 724 Internet draft 5 August 1998 725 An algebra for describing media feature sets 727 range of possible feature values. Thus the more restricted 728 definitions of "feature collection" and "feature set" which appear 729 in the terminology section of this document. 731 Original content, data files and recipients (and users) all embody 732 the potential capability to deal with a "feature set". One of the 733 aims of content negotiation is to select an available data file 734 format (availability being circumscribed by the original content 735 and sender capabilities) whose feature set intersection with the 736 recipient feature set is non-empty. (The further issue of 737 preference being deferred for later consideration.) 739 The concept of a mathematical relation as a subset defined by a 740 predicate can be used to define feature sets, using universal 741 quantification (i.e. using the predicate to select from some 742 notional universe of all possible feature collections). 744 Thus, a common framework of predicates can be used to represent the 745 feature capabilities of original content, data file formats, 746 recipients and any other participating entity which may impose 747 constraints on the usable feature sets. 749 Within this framework, it is sufficient to represent individual 750 feature values as Booleans, enumerated values, text strings or 751 numeric ranges. The thesis in section 3 of his document, combined 752 with a study of "Media Features for Display, Print, and Fax" [6], 753 indicate that more complex media feature values can be handled by 754 predicates. 756 5. Indicating preferences 758 5.1 Combining preferences 760 The general problem of describing and combining preferences among 761 feature sets is very much more complex than simply describing 762 allowable feature sets. For example, given two feature sets: 763 {A1,B1} 764 {A2,B2} 766 where: 767 A1 is preferred over A2 768 B2 is preferred over B1 770 Which of the feature sets is preferred? In the absence of 771 additional information or assumptions, there is no generally 772 satisfactory answer to this. 774 Internet draft 5 August 1998 775 An algebra for describing media feature sets 777 The proposed resolution of this issue is simply to assert that 778 preference information cannot be combined. Applied to the above 779 example, any preference information about A1 in relation to A2, or 780 B1 in relation to B2 is not presumed to convey information about 781 preference of {A1,B1} in relation to {A2,B2}. 783 In practical terms, this restricts the application of preference 784 information to top-level predicate clauses. A top-level clause 785 completely defines an allowable feature set; clauses combined by 786 logical-AND operators cannot be top-level clauses. 788 5.2 Representing preferences 790 A convenient way to represent preferences is by numeric "quality 791 values", as used in HTTP "Accept" headers, etc. (see RFC 2068 [9], 792 section 3.9). 794 It has been suggested that numeric quality values are potentially 795 misleading if used as more than just a way of ranking options. 796 Attempts to perform arithmetic on quality values do seem to 797 degenerate into meaningless juggling of numbers. 799 Numeric quality values in the range 0 to 1 (as defined by RFC 2068 800 [9], section 3.9) are used to rank feature sets according to 801 preference. Higher values are preferred over lower values, and 802 equal values are presumed to be equally preferred. Beyond this, 803 the actual number used has no significance, and should not be used 804 as a basis for any arithmetic operation. 806 In the absence of any explicitly applied quality value, a value of 807 "1" is assumed, suggesting an "ideal" option that is equally or 808 more preferred than any other. 810 This approach can be represented by extending the Prolog-based 811 framework of an earlier example as follows: 813 match_format(File,Qvalue) :- 814 match_format(File), 815 Qvalue=1. 817 match_format(File) :- 818 pix(File,[1024,768], 819 res(File,[Rx,Ry]). 821 match_format(File,Qvalue) :- 822 pix(File,[800, 600]), 823 res(File,[Rx,Ry]), 824 Qvalue=0.9. 826 match_format(File,Qvalue) :- 828 Internet draft 5 August 1998 829 An algebra for describing media feature sets 831 pix(File,[640, 480]). 832 res(File,[Rx,Ry]), 833 Qvalue=0.8. 835 res(File,[Rx,Ry]) :- 836 feature_match(Rx,75), feature_match(Ry,75) ; 837 feature_match(Rx,75), feature_match(Ry,150) ; 838 feature_match(Rx,150), feature_match(Ry,150) ; 839 feature_match(Rx,150), feature_match(Ry,300) ; 840 feature_match(Rx,300), feature_match(Ry,300) ; 841 feature_match(Rx,300), feature_match(Ry,600) ; 842 feature_match(Rx,600), feature_match(Ry,600) 844 This example applies image preference ranking based solely on the 845 size of the image, provided that the resolution constraints are 846 satisfied. 848 6. Feature set representation 850 The foregoing sections have described a framework and semantics for 851 defining feature sets with predicates applied to feature 852 collections. This section proposes some concrete representations 853 for these feature set predicates. 855 Rather than invent an all-new notation, this proposal adapts a 856 notation already defined for directory access [7,8]. Observe that 857 a feature collection is similar to a directory entry, in that it 858 consists of a collection of named values. Further, the semantics 859 of the mechanism for selecting feature collections from a feature 860 set is in many respects similar to selection of directory entries 861 from a directory. 863 Differences between directory selection (per [7]) and feature set 864 selection are: 866 . Directory selection provides substring-, approximate- and 867 extensible- matching for attribute values. Directory selection 868 may also be based on the presence of an attribute without regard 869 to its value. 871 . Directory selection provides for matching rules which are 872 dependent upon the declared data type of an attribute value. 874 . Feature selection provides for the association of a quality value 875 with a feature predicate as a way of ranking the selected value 876 collections. 878 . Feature selection contains provisions for defining relationships 879 between feature values. 881 Internet draft 5 August 1998 882 An algebra for describing media feature sets 884 The idea of substring matching does not seem to be relevant to 885 feature set selection, and is excluded from these proposals. 887 The idea of extensible matching and matching rules dependent upon 888 data types are facets of a problem not addressed by this memo, but 889 which do not necessarily affect the feature selection syntax. An 890 aspect which might have a bearing on the syntax would be a 891 requirement to specify a matching rule explicitly as part of a 892 selection expression. 894 Testing for the presence of a feature may be useful in some 895 circumstances, but does not sit comfortably within the semantic 896 framework. Feature sets are described by implied universal 897 quantification over predicates, and the absence of reference to a 898 given feature means the set is not constrained by that feature. 899 Against this, it is difficult to define what might be meant by 900 "presence" of a feature, so the "test for presence" option is not 901 included in these proposals. An effect similar to testing for the 902 presence of a feature can be achieved by a Boolean-valued feature. 904 6.1 Textual representation of predicates 906 The text representation of a feature set is based on RFC 2254 "The 907 String Representation of LDAP Search Filters" [8], excluding those 908 elements not relevant to feature set selection (discussed above), 909 and adding elements specific to feature set selection (e.g. options 910 to associate quality values with predicates). 912 The format of a feature predicate is defined by the production for 913 "filter" in the following, using the syntax notation and core rules 914 of [10]: 916 filter = "(" filtercomp *( ";" parameter ) )" 917 parameter = "q" "=" qvalue 918 / ext-param "=" ext-value 919 qvalue = ( "0" [ "." 0*3DIGIT ] ) 920 / ( "1" [ "." 0*3("0") ] ) 921 ext-param = ALPHA *( ALPHA / DIGIT / "-" ) 922 ext-value = 923 filtercomp = and / or / not / item 924 and = "&" filterlist 925 or = "|" filterlist 926 not = "!" filter 927 filterlist = 1*filter 928 item = simple / set / ext-pred 929 set = attr "=" "[" setentry *( "," setentry ) "]" 930 setentry = value "/" range 931 range = value ".." value 933 Internet draft 5 August 1998 934 An algebra for describing media feature sets 936 simple = attr filtertype value 937 filtertype = equal / greater / less 938 equal = "=" 939 approx = "~=" 940 greater = ">=" 941 less = "<=" 942 attr = ftag 943 value = fvalue 944 ftag = 945 fvalue = number / token / string 946 number = integer / rational 947 integer = 1*DIGIT 948 rational = 1*DIGIT "." 1*DIGIT 949 token = ALPHA *( ALPHA / DIGIT / "-" ) 950 string = DQUOTE *(%x20-21 / %x23-7E) DQUOTE 951 ; quoted string of SP and VCHAR without DQUOTE 952 ext-pred = 954 (Subject to constraints imposed by the protocol that carries a 955 feature predicate, whitespace characters may appear between any 956 pair of syntax elements or literals that appear on the right hand 957 side of these productions.) 959 As described, the syntax permits parameters (including quality 960 values) to be attached to any "filter" value in the predicate (not 961 just top-level values). Only top-level quality values are 962 recognized. If no explicit quality value is given, a value of 963 '1.0' is applied. 965 NOTE 967 The flexible approach to quality values and other 968 parameter values in this syntax has been adopted for two 969 reasons: (a) to make it easy to combine separately 970 constructed feature predicates, and (b) to provide an 971 extensible tagging mechanism (for example, to incorporate 972 a conceivable requirement to explicitly specify a 973 matching rule). 975 6.2 Named and auxiliary predicates 977 Named and auxiliary predicates can serve two purposes: 979 (a) making complex predicates easier to write and understand, and 981 (b) providing a possible basis for naming and registering feature 982 sets. 984 Internet draft 5 August 1998 985 An algebra for describing media feature sets 987 6.2.1 Defining a named predicate 989 A named predicate definition has the following form: 991 named-pred = "(" fname *pname ")" ":-" filter 992 fname = ftag ; Feature predicate name 993 pname = token ; Formal parameter name 995 'fname' is the name of the predicate. 997 'pname' is the name of a formal parameter which may appear in the 998 predicate body, and which is replaced by some supplied value when 999 the predicate is invoked. 1001 'filter' is the predicate body. It may contain references to the 1002 formal parameters, and may also contain references to feature tags 1003 and other values defined in the environment in which the predicate 1004 is invoked. References to formal parameters may appear anywhere 1005 where a reference to a feature tag ('ftag') is permitted by the 1006 syntax for 'filter'. 1008 The only specific mechanism defined by this memo for introducing a 1009 named predicate into a feature set definition is the "auxiliary 1010 predicate" described later. Specific negotiating protocols or 1011 other memos may define other mechanisms. 1013 NOTE 1015 There has been some discussion of creating a registry for 1016 feature sets as well as individual feature values. Such 1017 a registry might be used to introduce named predicates 1018 corresponding to these feature sets into the environment 1019 of a capability assertion. Further discussion of this 1020 idea is beyond the scope of this memo. 1022 6.2.2 Invoking named predicates 1024 Assuming a named predicate has been introduced into the environment 1025 of some other predicate, it can be invoked by a filter 'ext-pred' 1026 of the form: 1028 ext-pred = fname *param 1029 param = expr 1031 The number of parameters must match the definition of the named 1032 predicate that is invoked. 1034 Internet draft 5 August 1998 1035 An algebra for describing media feature sets 1037 6.2.3 Auxiliary predicates in a filter 1039 A auxiliary predicate is attached to a filter definition by the 1040 following extension to the "filter" syntax: 1042 filter =/ "(" filtercomp *( ";" parameter ) ")" 1043 "where" 1*( named-pred ) "end" 1045 The named predicates introduced by "named-pred" are visible from 1046 the body of the "filtercomp" of the filter to which they are 1047 attached, but are not visible from each other. They all have 1048 access to the same environment as "filter", plus their own formal 1049 parameters. (Normal scoping rules apply: a formal parameter with 1050 the same name as a value in the environment of "filter" effectively 1051 hides the environment value from the body of the predicate to which 1052 it applies.) 1054 NOTE 1056 Recursive predicates are not permitted. The scoping 1057 rules should ensure this. 1059 6.3 Feature set definition examples 1061 This section re-casts the Prolog example given in section 5.2 using 1062 the textual form syntax described in sections 6.1 and 6.2. 1064 6.3.1 Single predicate 1066 (| (& (Pix_x=1024) 1067 (Pix_y=768) 1068 (| (& (Res_x=75) (Res_y=75) ) 1069 (& (Res_x=75) (Res_y=150) ) 1070 (& (Res_x=150) (Res_y=150) ) 1071 (& (Res_x=150) (Res_y=300) ) 1072 (& (Res_x=300) (Res_y=300) ) 1073 (& (Res_x=300) (Res_y=600) ) 1074 (& (Res_x=600) (Res_y=600) ) ) 1075 (& (Pix_x=800) 1076 (Pix_y=600) 1077 (| (& (Res_x=75) (Res_y=75) ) 1078 (& (Res_x=75) (Res_y=150) ) 1079 (& (Res_x=150) (Res_y=150) ) 1080 (& (Res_x=150) (Res_y=300) ) 1081 (& (Res_x=300) (Res_y=300) ) 1082 (& (Res_x=300) (Res_y=600) ) 1083 (& (Res_x=600) (Res_y=600) ) ) ;q=0.9 1084 (& (Pix_x=640) 1085 (Pix_y=480) 1086 (| (& (Res_x=75) (Res_y=75) ) 1088 Internet draft 5 August 1998 1089 An algebra for describing media feature sets 1091 (& (Res_x=75) (Res_y=150) ) 1092 (& (Res_x=150) (Res_y=150) ) 1093 (& (Res_x=150) (Res_y=300) ) 1094 (& (Res_x=300) (Res_y=300) ) 1095 (& (Res_x=300) (Res_y=600) ) 1096 (& (Res_x=600) (Res_y=600) ) ) ;q=0.8 1098 6.3.2 Predicate with auxiliary predicate 1100 (| (& (Pix_x=1024) (Pix_y=768) (Res Res_x Res_y) ) 1101 (& (Pix_x=800) (Pix_y=600) (Res Res_x Res_y) );q=0.9 1102 (& (Pix_x=640) (Pix_y=480) (Res Res_x Res_y) );q=0.8 ) 1103 where 1104 (Res Res_x Res_y) :- 1105 (| (& (Res_x=75) (Res_y=75) ) 1106 (& (Res_x=75) (Res_y=150) ) 1107 (& (Res_x=150) (Res_y=150) ) 1108 (& (Res_x=150) (Res_y=300) ) 1109 (& (Res_x=300) (Res_y=300) ) 1110 (& (Res_x=300) (Res_y=600) ) 1111 (& (Res_x=600) (Res_y=600) ) ) 1112 end 1114 Note that the formal parameters of "Res", "Res_x" and "Res_y", 1115 prevent the body of the named predicate from referencing similarly- 1116 named feature values. 1118 6.4 ASN.1 representation 1120 Should it be required, the LDAP search filter model provides the 1121 basis for an ASN.1 representation of a feature predicate. 1123 The following ASN.1 is adapted from RFC 2251 "Lightweight Directory 1124 Access Protocol (v3)" [7] (also contained in RFC 2254 "The String 1125 Representation of LDAP Search Filters" [8]) to mirror the 1126 adaptation of the string representation presented above 1128 [[The following ASN.1 fragment does not include provision for 1129 quality value (and possibly other parameter values). Also, if 1130 using an ASN.1-derived representation it would seem appropriate to 1131 use an ISO object identifier for the feature tag, and an ASN.1 type 1132 for the feature value. Such changes would remove any semblance of 1133 compatibility with LDAP, but that may not matter.]] 1135 Internet draft 5 August 1998 1136 An algebra for describing media feature sets 1138 Filter ::= CHOICE { 1139 and [0] SET OF Filter, 1140 or [1] SET OF Filter, 1141 not [2] Filter, 1142 equalityMatch [3] AttributeValueAssertion, 1143 greaterOrEqual [5] AttributeValueAssertion, 1144 lessOrEqual [6] AttributeValueAssertion 1145 } 1147 AttributeValueAssertion ::= SEQUENCE { 1148 featureTag OCTET STRING, 1149 featureValue OCTET STRING 1150 } 1152 7. Content negotiation protocol processing 1154 This section addresses some issues that may arise when using 1155 feature set predicates as part of some content negotiation or file 1156 selection protocol. 1158 7.1 Matching feature sets 1160 Matching a feature set to some given feature collection is 1161 esentially very straightforward: the feature set predicate is 1162 simply evaluated for the given feature collection, and the result 1163 indicates whether the feature collection matches the capabilities, 1164 and the associated quality value can be used for selecting among 1165 alternative feature collections. 1167 Matching a feature set to some other feature set is less 1168 straightforward. Here, the problem is to determine whether or not 1169 there is at least one feature collection that matches both feature 1170 sets (e.g. is there an overlap between the feature capabilities of 1171 a given file format and the feature capabilities of a given 1172 recipient?) 1174 This feature set matching is accomplished by logical manipulation 1175 of the predicate expressions as described in the following 1176 sections. 1178 For this procedure to work reliably, the predicates must be reduced 1179 to a canonical form. One such form is "clausal form", and 1180 procedures for converting general expressions in predicate calculus 1181 are given in [5] (section 10.2), [11] (section 2.13), [13] (chapter 1182 4) and [14] (section 5.3.2). 1184 "Clausal form" for a predicate is similar to "conjunctive normal 1185 form" for a proposition, which consists of a conjunction (logical 1186 ANDs) of disjunctions (logical ORs). A related form that is better 1188 Internet draft 5 August 1998 1189 An algebra for describing media feature sets 1191 suited to feature set matching is "disjunctive normal form", which 1192 consists of a logical disjunction (OR) of conjunctions (ANDs). In 1193 this form, it is sufficient to show that at least one of the 1194 disjunctions can be satisfied by some feature collection. 1196 A syntax for disjunctive normal form is: 1198 filter = orlist 1199 orlist = "(" "|" andlist ")" / term 1200 andlist = "(" "&" termlist ")" / term 1201 termlist = 1*term 1202 term = "(" "!" simple ")" / simple 1204 where "simple" is as described previously in section 6.1. Thus, 1205 the canonicalized form has at most three levels: an outermost 1206 "(|...)" disjunction of "(&...)" conjunctions of possibly negated 1207 feature value tests. 1209 NOTE (a theoretical diversion): 1211 Is this consideration of "clausal form" really required? 1212 After all, the feature predicates are just Boolean 1213 expressions, aren't they? 1215 Well, no. A feature predicate is a Boolean expression 1216 containing primitive feature value tests (comparisons), 1217 represented by 'item' in the feature predicate syntax. 1218 If these tests could all be assumed to be independently 1219 'true' or 'false', then each could be regarded as an 1220 atomic proposition, and the whole predicate could be 1221 dealt with according to the (relatively simple) rules of 1222 the Propositional Calculus. 1224 But, in general, the same feature tag may appear in more 1225 than one predicate 'item', so the tests cannot be 1226 regarded as independent. Indeed, interdependence is 1227 needed in any meaningful application of feature set 1228 matching, and it is important to capture these 1229 dependencies (e.g. does the set of resolutions that a 1230 sender can supply overlap the set of resolutions that a 1231 recipient can handle?). Thus, we have to deal with 1232 elements of the Predicate Calculus, with its additional 1233 rules for algebraic manipulation. 1235 This section aims to show that these additional rules are 1236 more unfamiliar than complicated. In practice, the way 1237 that feature predicates are constructed and used actually 1238 avoids some of the complexity of dealing with fully- 1239 generalized Predicate Calculus. 1241 Internet draft 5 August 1998 1242 An algebra for describing media feature sets 1244 7.1.1 Feature set matching strategy 1246 The overall strategy for matching feature sets, expanded in the 1247 following sections, is: 1249 1. Formulate the feature set match hypothesis. 1251 2. Replace "set" expressions with equivalent comparisons. 1253 3. Eliminate logical negations, and express all feature comparisons 1254 in terms of just four comparison operators 1256 4. Reduce the hypothesis to canonical disjunctive normal form (a 1257 disjunction of conjunctions). 1259 5. For each of the conjunctions, attempt to show that it can be 1260 satisfied by some feature collection. Any that cannot be 1261 satisfied are discarded. 1263 5.1 Separate the feature value tests into independent groups, 1264 such that each group contains tests involving just one 1265 feature value. That is: no group contains a predicate 1266 involving any feature tag that also appears in a predicate 1267 in some other group. 1269 5.2 For each group, merge the various constraints to a minimum 1270 form. This process either yields a reduced expression for 1271 the allowable range of feature values, or an indication that 1272 no value can satisfy the constraints (in which case the 1273 corresponding conjucntion can never be satisfied). 1275 6. If the remaining disjunction is non-empty, then the constraints 1276 are shown to be satisfiable. Further, it can be used as a 1277 statement of the resulting feature set for possible further 1278 matching operations. 1280 7.1.2 Formulating the goal predicate 1282 A formal statement of the problem we need to solve can be given as: 1283 given two feature set predicates, '(P x)' and '(Q x)', where 'x' is 1284 some feature collection, we wish to establish the truth or 1285 otherwise of the proposition: 1287 EXISTS(x) : (P x) AND (Q x) 1289 i.e. does there exist a feature collection that satisfies both 1290 predicates, 'P' and 'Q'? 1292 Internet draft 5 August 1998 1293 An algebra for describing media feature sets 1295 Then, if feature sets to be matched are described by predicates 'P' 1296 and 'Q', the problem is to determine if there is any feature set 1297 satisfying the goal predicate: 1299 (& P Q) 1301 i.e. to determine whether the set thus described is non-empty. 1303 7.1.3 Replace set expressions 1305 Replace all "set" instances in the goal predicate with equivalent 1306 "simple" forms: 1308 T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) ) 1309 (T=[R1..R2]) --> (& (T>=R1) (T<=R2) ) 1310 (T=[E]) --> (T=E) 1312 7.1.4 Replace comparisons and logical negations 1314 The predicates are derived from the syntax described previously, 1315 and contain primitive value testing functions '=', '<=', '>='. The 1316 primitive tests have a number of well known properties that are 1317 exploited to reach a useful conclusion; e.g. 1319 (A = B) & (B = C) => (A = C) 1320 (A <= B) & (B <= C) => (A <= C) 1322 These rules form a core body of logic statements against which the 1323 goal predicate can be evaluated. The form in which these 1324 statements are expressed is important to realizing an effective 1325 predicate matching algorithm (i.e. one that doesn't loop or fail to 1326 find a valid result). The first step in forumulating these rules 1327 is to simplify the framework of primitive predicates. 1329 The primitive predicates from which feature set definitions are 1330 constructed are '=', '<=' and '>='. Observe that, given any pair 1331 of feature values, the relationship between them must be exactly 1332 one of the following: 1334 (LT a b): 'a' is less than 'b'. 1335 (EQ a b): 'a' is equal to 'b'. 1336 (GT a b): 'a' is greater than 'b'. 1337 (NE a b): 'a' is not equal and not related to 'b'. 1339 (The final case arises when two values are compared for which no 1340 ordering relationship is defined, and the values are not equal; 1341 e.g. two unequal string values.) 1343 These four cases can be captured by a pair of primitive predicates: 1345 Internet draft 5 August 1998 1346 An algebra for describing media feature sets 1348 (LE a b): 'a' is less than or equal to 'b'. 1349 (GE a b): 'a' is greater than or equal to 'b'. 1351 The four cases described above are prepresented by the following 1352 combinations of primitive predicate values: 1354 (LE a b) (GE a b) | relationship 1355 ---------------------------------- 1356 TRUE FALSE | (LT a b) 1357 TRUE TRUE | (EQ a b) 1358 FALSE TRUE | (GT a b) 1359 FALSE FALSE | (NE a b) 1361 Thus, the original 3 primitive tests can be translated to 1362 combinations of just LE and GE, reducing the number of additional 1363 relationships that must be subsequently captured: 1365 (a <= b) --> (LE a b) 1366 (a >= b) --> (GE a b) 1367 (a = b) --> (& (LE a b) (GE a b) ) 1369 Further, logical negations of the original 3 primitive tests can be 1370 eliminated by the introduction of 'not-greater' and 'not-less' 1371 primitives 1373 (NG a b) == (! (GE a b) ) 1374 (NL a b) == (! (LE a b) ) 1376 using the following transformation rules: 1378 (! (a = b) ) --> (| (NL a b) (NG a b) ) 1379 (! (a <= b) ) --> (NL a b) 1380 (! (a >= b) ) --> (NG a b) 1382 Thus, we have rules to transform all comparisons and logical 1383 negations into combinations of just 4 relational operators. 1385 7.1.5 Conversion to canonical form 1387 Expand bracketed disjunctions, and flatten bracketed conjunctions 1388 and disjunctions: 1390 (& (| A1 A2 ... Am ) B1 B2 ... Bn ) 1391 --> (| (& A1 B1 B2 ... Bn ) 1392 (& A2 B1 B2 ... Bn ) 1393 : 1394 (& Am B1 B2 ... Bn ) ) 1395 (& (& A1 A2 ... Am ) B1 B2 ... Bn ) 1396 --> (& A1 A2 ... Am B1 B2 ... Bn ) 1397 (| (| A1 A2 ... Am ) B1 B2 ... Bn ) 1399 Internet draft 5 August 1998 1400 An algebra for describing media feature sets 1402 --> (| A1 A2 ... Am B1 B2 ... Bn ) 1404 The result is a "disjunctive normal form", a disjunction of 1405 conjunctions: 1407 (| (& S11 S12 ... ) 1408 (& S21 S22 ... ) 1409 : 1410 (& Sm1 Sm2 ... Smn ) ) 1412 where the "Sij" elements are simple feature comparison forms 1413 constructed during the step at section 7.1.4. Each term within the 1414 top-level "(|...)" construct represents a single possible feature 1415 set that satisfies the goal. Note that the order of entries within 1416 the top-level '(|...)', and within each '(&...)', is immaterial. 1418 From here on, each conjunction '(&...)' is processed separately. 1419 Only one of these needs to be satisfiable for the original goal to 1420 be satisfiable. 1422 (A textbook conversion to clausal form [5,11] uses slightly 1423 different rules to yield a "conjunctive normal form".) 1425 7.1.6 Grouping of feature predicates 1427 NOTE: remember that from here on, each conjunction is 1428 treated separately. 1430 Each simple feature predicate contains a "left-hand" feature tag 1431 and a "right-hand" feature value with which it is compared. 1433 To arrange these into independent groups, simple predicates are 1434 grouped according to their left hand feature tag ('f'). 1436 7.1.7 Merge single-feature constraints 1438 Within each group, apply the predicate simplification rules given 1439 below to eliminate redundant single-feature constraints. All 1440 single-feature predicates are reduced to an equality or range 1441 constraint on that feature, possibly combined with a number of non- 1442 equality statements. 1444 If the constraints on any feature are found to be contradictory 1445 (i.e. resolved to FALSE according to the applied rules), the 1446 current conjunction is removed from the feature set description. 1447 Otherwise, the resulting description is a minimal form of the 1448 particular conjunction of the feature set definition. 1450 Internet draft 5 August 1998 1451 An algebra for describing media feature sets 1453 7.1.7.1 Rules for simplifying ordered values 1455 These rules are applicable where there is an ordering relationship 1456 between the given values 'a' and 'b': 1458 (LE f a) (LE f b) --> (LE f a), a<=b 1459 (LE f b), otherwise 1460 (LE f a) (GE f b) --> FALSE, a FALSE, a<=b 1462 (LE f a) (NG f b) --> (LE f a), a (GE f a), a>=b 1466 (GE f b), otherwise 1467 (GE f a) (NL f b) --> (GE f a) a>b 1468 (NL f b), otherwise 1469 (GE f a) (NG f b) --> FALSE, a>=b 1471 (NL f a) (NL f b) --> (NL f a), a>=b 1472 (NL f b), otherwise 1473 (NL f a) (NG f b) --> FALSE, a>=b 1475 (NG f a) (NG f b) --> (NG f a), a<=b 1476 (NG f b), otherwise 1478 7.1.7.2 Rules for simplifying unordered values 1480 These rules are applicable where there is no ordering relationship 1481 applicable to the given values 'a' and 'b': 1483 (LE f a) (LE f b) --> (LE f a), a=b 1484 FALSE, otherwise 1485 (LE f a) (GE f b) --> FALSE, a!=b 1486 (LE f a) (NL f b) --> (LE f a) a!=b 1487 FALSE, otherwise 1488 (LE f a) (NG f b) --> (LE f a), a!=b 1489 FALSE, otherwise 1491 (GE f a) (GE f b) --> (GE f a), a=b 1492 FALSE, otherwise 1493 (GE f a) (NL f b) --> (GE f a) a!=b 1494 FALSE, otherwise 1495 (GE f a) (NG f b) --> (GE f a) a!=b 1496 FALSE, otherwise 1498 (NL f a) (NL f b) --> (NL f a), a=b 1499 (NL f a) (NG f b) --> (NL f a), a=b 1501 (NG f a) (NG f b) --> (NG f a), a=b 1503 Internet draft 5 August 1998 1504 An algebra for describing media feature sets 1506 [[[TODO: model the above system to confirm that it is complete and 1507 does indeed work properly in all cases.]]] 1509 7.2 Effect of named predicates 1511 The preceding procedures can be extended to deal with named 1512 predicates simply by instantiating (i.e. substituting) the 1513 predicates wherever they are invoked, before performing the 1514 conversion to disjunctive normal form. In the absence of recursive 1515 predicates, this procedure is guaranteed to terminate. 1517 7.3 Unit designations 1519 In some exceptional cases, there may be differing conventions for 1520 the units of measurement of a given feature. For example, 1521 resolution is commonly expressed as dots per inch (dpi) or dots per 1522 centimetre (dpcm) in different applications (e.g. printing vs 1523 faxing). 1525 In such cases, a unit designator may be appended to a feature value 1526 according to the conventions indicated below (see also [3]). These 1527 considerations apply only to features with numeric values. 1529 Every feature tag has a standard unit of measurement. Any 1530 expression of a feature value that uses this unit is given without 1531 a unit designation -- this is the normal case. When the feature 1532 value is expressed in some other unit, a unit designator is 1533 appended to the numeric feature value. 1535 The registration of a feature tag indicates the standard unit of 1536 measurement for a feature, and also any alternate units and 1537 corresponding unit designators that may be used, according to [3]. 1539 Thus, if the standard unit of measure for resolution is 'dpcm', 1540 then the feature predicate '(res=200)' would be used to indicate a 1541 resolution of 200 dots-per-centimetre, and '(res=72dpi)' might be 1542 used to indicate 72 dots-per-inch. 1544 Unit designators are accommodated by the following extension to the 1545 feature predicate syntax: 1547 fvalue /= number *WSP token 1549 When performing feature set matching, feature comparisons with and 1550 without unit designators, or feature comparisons with different 1551 unit designators, are treated as if they were different features. 1552 Thus, the feature predicate '(res=200)' would not, in general, fail 1553 to match with the predicate '(res=200dpi)'. 1555 Internet draft 5 August 1998 1556 An algebra for describing media feature sets 1558 NOTE: 1560 A protocol processor with specific knowledge of the 1561 feature and units concerned might recognize the 1562 relationship between the feature predicates in the above 1563 example, and fail to match these predicates. 1565 This appears to be a natural behaviour in this simple 1566 example, but can cause additional complexity in more 1567 general cases. Accordingly, this is not considered to be 1568 required or normal behaviour. It is presumed that in 1569 general, the application concerned will ensure consistent 1570 feature processing by adopting a consistent unit for any 1571 given feature. 1573 7.4 Unknown feature value data types 1575 [[Discuss issues of specific features which may have feature- 1576 specific comparison rules, as opposed to generic Booleans, 1577 enumerations, strings and numbers which use comparison rules 1578 independent of the feature concerned.]] 1580 [[[TODO]]] 1582 7.5 Worked example 1584 [[[TODO]]] 1586 7.6 Algorithm source code 1588 [[[TODO]]] 1590 8. Security considerations 1592 Some security considerations for content negotiation are raised in 1593 [1,2,3]. 1595 Internet draft 5 August 1998 1596 An algebra for describing media feature sets 1598 The following are primary security concerns for capability 1599 identification mechanisms: 1601 . Unintentional disclosure of private information through the 1602 announcement of capabilities or user preferences. 1604 . Disruption to system operation caused by accidental or malicious 1605 provision of incorrect capability information. 1607 . Use of a capability identification mechanism might be used to 1608 probe a network (e.g. by identifying specific hosts used, and 1609 exploiting their known weaknesses). 1611 The most contentious security concerns are raised by mechanisms 1612 which automatically send capability identification data in response 1613 to a query from some unknown system. Use of directory services 1614 (based on LDAP [7], etc.) seem to be less problematic because 1615 proper authentication mechanisms are available. 1617 Mechanisms which provide capability information when sending a 1618 message are less contentious, presumably because some intention can 1619 be inferred that person whose details are disclosed wishes to 1620 communicate with the recipient of those details. This does not, 1621 however, solve problems of spoofed supply of incorrect capability 1622 information. 1624 The use of format converting gateways may prove problematic because 1625 such systems would tend to defeat any message integrity and 1626 authenticity checking mechanisms that are employed. 1628 9. Copyright 1630 Copyright (C) The Internet Society 1998. All Rights Reserved. 1632 This document and translations of it may be copied and furnished to 1633 others, and derivative works that comment on or otherwise explain 1634 it or assist in its implementation may be prepared, copied, 1635 published and distributed, in whole or in part, without restriction 1636 of any kind, provided that the above copyright notice and this 1637 paragraph are included on all such copies and derivative works. 1638 However, this document itself may not be modified in any way, such 1639 as by removing the copyright notice or references to the Internet 1640 Society or other Internet organizations, except as needed for the 1641 purpose of developing Internet standards in which case the 1642 procedures for copyrights defined in the Internet Standards process 1643 must be followed, or as required to translate it into languages 1644 other than English. 1646 Internet draft 5 August 1998 1647 An algebra for describing media feature sets 1649 The limited permissions granted above are perpetual and will not be 1650 revoked by the Internet Society or its successors or assigns. 1652 This document and the information contained herein is provided on 1653 an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET 1654 ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR 1655 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1656 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1657 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1659 10. Acknowledgements 1661 My thanks to Larry Masinter for demonstrating to me the breadth of 1662 the media feature issue, and encouraging me to air my early ideas. 1664 Early discussions of ideas on the IETF-HTTP and IETF-FAX discussion 1665 lists led to useful inputs also from Koen Holtman, Ted Hardie and 1666 Dan Wing. 1668 The debate later moved to the IETF conneg WG mailing list, where Al 1669 Gilman was particularly helpful in helping me to refine the feature 1670 set algebra. Ideas for dealing with preferences and specific units 1671 were suggested by Larry Masinter. 1673 I would also like to thank Content Technologies Ltd and 5th 1674 Generation Messaging Ltd for supporting this work. 1676 11. References 1678 [1] "Scenarios for the Delivery of Negotiated Content" 1679 T. Hardie, NASA Network Information Center 1680 Internet draft: 1681 Work in progress, November 1997. 1683 [2] "Requirements for protocol-independent content negotiation" 1684 G. Klyne, Integralis Ltd. 1685 Internet draft: 1686 Work in progress, March 1998. 1688 [3] "Content feature tag registration procedures" 1689 Koen Holtman, TUE 1690 Andrew Mutz, Hewlett-Packard 1691 Ted Hardie, NASA 1692 Internet draft: 1693 Work in progress, November 1997. 1695 Internet draft 5 August 1998 1696 An algebra for describing media feature sets 1698 [4] "Notes on data structuring" 1699 C. A. R. Hoare, 1700 in "Structured Programming" 1701 Academic Press, APIC Studies in Data Processing No. 8 1702 ISBN 0-12-200550-3 / 0-12-200556-2 1703 1972. 1705 [5] "Programming in Prolog" (2nd edition) 1706 W. F. Clocksin and C. S. Mellish, 1707 Springer Verlag 1708 ISBN 3-540-15011-0 / 0-387-15011-0 1709 1984. 1711 [6] "Media Features for Display, Print, and Fax" 1712 Larry Masinter, Xerox PARC 1713 Koen Holtman, TUE 1714 Andrew Mutz, Hewlett-Packard 1715 Dan Wing, Cisco Systems 1716 Internet draft: 1717 Work in progress, January 1998. 1719 [7] RFC 2251, "Lightweight Directory Access Protocol (v3)" 1720 M. Wahl, Critical Angle Inc. 1721 T. Howes, Netscape Communications Corp. 1722 S. Kille, Isode Limited 1723 December 1997. 1725 [8] RFC 2254, "The String Representation of LDAP Search Filters" 1726 T. Howes, Netscape Communications Corp. 1727 December 1997. 1729 [9] RFC 2068, "Hyptertext Transfer Protocol -- HTTP/1.1" 1730 R. Fielding, UC Irvine 1731 J. Gettys, 1732 J. Mogul, DEC 1733 H. Frytyk, 1734 T. Berners-Lee, MIT/LCS 1735 January 1997. 1737 [10] RFC 2234, "Augmented BNF for Syntax Specifications: ABNF" 1738 D. Crocker (editor), Internet Mail Consortium 1739 P. Overell, Demon Internet Ltd. 1740 November 1997. 1742 [11] "Logic, Algebra and Databases" 1743 Peter Gray 1744 Ellis Horwood Series: Computers and their Applications 1745 ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd) 1746 ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press) 1747 1984. 1749 Internet draft 5 August 1998 1750 An algebra for describing media feature sets 1752 [12] "Introduction to Expert Systems" 1753 Peter Jackson 1754 Addison Wesley, International computer science series 1755 ISBN 0-201-14223-6 1756 1986. 1758 [13] "Elementary Logics: A procedural Perspective 1759 Dov Gabbay 1760 Prentice Hall, Series in computer science 1761 ISBN 0-13-726365-1 1762 1998. 1764 [14] "Logic and its Applications" 1765 Edmund Burk and Eric Foxley 1766 Prentice Hall, Series in computer science 1767 ISBN 0-13-030263-5 1768 1996. 1770 [15] "Metalogic: 1771 An Introduction to the Metatheory of Standard First Order Logic" 1772 Geoffrey Hunter 1773 University of California Press 1774 ISBN 0-520-02356-0 1775 1971. 1777 [16] "Elementary Linear Algebra" 1778 Paul C Shields 1779 Worth Publishers Inc. 1780 ISBN 0-87901-121-1 1781 1968, 1973, 1980. 1783 [17] "Linear Programming" 1784 Saul I Gass, 1785 McGraw-Hill Inc. 1786 Library of Congress Catalog Card no 68-55267 (no ISBN) 1787 1958, 1964, 1969. 1789 Internet draft 5 August 1998 1790 An algebra for describing media feature sets 1792 12. Author's address 1794 Graham Klyne 1795 Content Technologies Ltd. 5th Generation Messaging Ltd. 1796 Forum 1 5 Watlington Street 1797 Station Road Nettlebed 1798 Theale Henley-on-Thames 1799 Reading, RG7 4RA RG9 5AB 1800 United Kingdom United Kingdom. 1802 Telephone: +44 118 930 1300 +44 1491 641 641 1804 Facsimile: +44 118 930 1301 +44 1491 641 611 1806 E-mail: GK@ACM.ORG