idnits 2.17.1 draft-ietf-conneg-feature-syntax-02.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 document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page ** 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. == The page length should not exceed 58 lines per page, but there was 32 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. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? RFC 2119 keyword, line 179: '... "SHOULD", SHOULD NOT", "RECOMMENDED"...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Unrecognized Status in 'Category: Work-in-progress', assuming Proposed Standard (Expected one of 'Standards Track', 'Full Standard', 'Draft Standard', 'Proposed Standard', 'Best Current Practice', 'Informational', 'Experimental', 'Informational', 'Historic'.) -- 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 (29 October 1998) is 9311 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: '8' is mentioned on line 1567, but not defined == Missing Reference: '9' is mentioned on line 1571, but not defined == Missing Reference: '10' is mentioned on line 1579, but not defined == Missing Reference: '11' is mentioned on line 1584, but not defined == Missing Reference: '12' is mentioned on line 1591, but not defined == Missing Reference: '13' is mentioned on line 1597, but not defined == Unused Reference: '6' is defined on line 1550, 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' ** Downref: Normative reference to an Experimental RFC: RFC 2295 (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) Summary: 13 errors (**), 0 flaws (~~), 10 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IETF media feature registration WG Graham Klyne 3 Request for comments: nnnn Content Technologies/5GM 4 Category: Work-in-progress 29 October 1998 5 Expires: April 1999 7 A syntax 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 [[INTENDED STATUS: This document specifies an Internet standards 31 track protocol for the Internet community, and requests discussion 32 and suggestions for improvements. Please refer to the current 33 edition of the "Internet Official Protocol Standards" (STD 1) for 34 the standardization state and status of this protocol. 35 Distribution of this memo is unlimited.]] 37 Copyright Notice 39 Copyright (C) The Internet Society 1998. All Rights Reserved. 41 Abstract 43 A number of Internet application protocols have a need to provide 44 content negotiation for the resources with which they interact [1]. 45 A framework for such negotiation is described in [2], part of which 46 is a way to describe the range of media features which can be 47 handled by the sender, recipient or document transmission format of 48 a message. A format for a vocabulary of individual media features 49 and procedures for feature registration are presented in [3]. 51 RFC nnnn A syntax for describing media feature sets 52 29 October 1998 54 This document introduces and describes a syntax that can be used to 55 define feature sets which are formed from combinations and 56 relations involving individual media features. Such feature sets 57 are used to describe the media feature handling capabilities of 58 message senders, recipients and file formats. 60 An algorithm for feature set matching is also described here. 62 Table of contents 64 1. Introduction.............................................3 65 1.1 Structure of this document ...........................4 66 1.2 Document terminology and conventions .................4 67 1.3 Discussion of this document ..........................4 68 1.4 Amendment history ....................................5 69 1.5 Unfinished business ..................................6 70 2. Content feature terminology and definitions..............6 71 3. Media feature combinations and capabilities..............7 72 3.1 Media features .......................................7 73 3.2 Media feature collections and sets ...................7 74 3.3 Media feature set descriptions .......................7 75 3.4 Media feature combination scenario ...................8 76 3.4.1 Data resource options............................8 77 3.4.2 Recipient capabilities...........................9 78 3.4.3 Combined options.................................9 79 3.5 Feature set predicates ...............................9 80 3.5.1 Comparison with directory search filters.........10 81 3.6 Describing preferences ...............................11 82 3.7 Combining preferences ................................12 83 4. Feature set representation...............................12 84 4.1 Textual representation of predicates .................12 85 4.2 Notational conveniences ..............................14 86 4.3 Feature set definition example .......................14 87 5. Matching feature sets....................................15 88 5.1 Feature set matching strategy ........................17 89 5.2 Formulating the goal predicate .......................18 90 5.3 Replace set expressions ..............................18 91 5.4 Move logical negations inwards .......................18 92 5.5 Replace comparisons and logical negations ............19 93 5.6 Conversion to canonical form .........................20 94 5.7 Grouping of feature predicates .......................21 95 5.8 Merge single-feature constraints .....................21 96 5.8.1 Rules for simplifying ordered values.............22 97 5.8.2 Rules for simplifying unordered values...........22 98 6. Other features and issues................................23 99 6.1 Named and auxiliary predicates .......................23 100 6.1.1 Defining a named predicate.......................23 101 6.1.2 Invoking named predicates........................24 102 6.1.3 Auxiliary predicates in a filter.................24 104 RFC nnnn A syntax for describing media feature sets 105 29 October 1998 107 6.1.4 Feature matching with named predicates...........24 108 6.1.4 Example..........................................25 109 6.2 Unit designations ....................................25 110 6.3 Unknown feature value data types .....................26 111 7. Examples and additional comments.........................26 112 7.1 Worked example .......................................26 113 7.2 A note on feature tag scoping ........................27 114 8. Algorithm source code....................................29 115 9. Security considerations..................................29 116 10. Full copyright statement................................30 117 11. Acknowledgements........................................30 118 12. References..............................................31 119 13. Author's address........................................33 121 1. Introduction 123 A number of Internet application protocols have a need to provide 124 content negotiation for the resources with which they interact [1]. 125 A framework for such negotiation is described in [2]. A part of 126 this framework is a way to describe the range of media features 127 which can be handled by the sender, recipient or document 128 transmission format of a message. 130 Descriptions of media feature capabilities need to be based upon 131 some underlying vocabulary of individual media features. A format 132 for such a vocabulary and procedures for registering media features 133 within this vocabulary are presented in [3]. 135 This document defines a syntax that can be used to describe feature 136 sets which are formed from combinations and relations involving 137 individual media features. Such feature sets are used to describe 138 the media handling capabilities of message senders, recipients and 139 file formats. 141 An algorithm for feature set matching is also described here. 143 The feature set syntax is built upon the principle of using feature 144 set predicates as "mathematical relations" which define constraints 145 on feature handling capabilities. This allows that the same form 146 of feature set expression can be used to describe sender, receiver 147 and file format capabilities. This has been loosely modelled on 148 the way that relational databases use Boolean expresions to 149 describe a set of result values, and a syntax that is based upon 150 LDAP search filters. 152 RFC nnnn A syntax for describing media feature sets 153 29 October 1998 155 1.1 Structure of this document 157 The main part of this memo addresses the following main areas: 159 Section 2 introduces and references some terms which are used with 160 special meaning. 162 Section 3 introduces the concept of describing media handling 163 capabilities as combinations of possible media features, and the 164 idea of using Boolean expressions to express such combinations. 166 Section 4 contains a description of a syntax for describing feature 167 sets based on the previously-introduced idea of Boolean expressions 168 used to describe media feature combinations. 170 Section 5 describes an algorithm for feature set matching. 172 Section 6 discusses some additional media feature description and 173 processing issues that may be viewed as extensions to the core 174 framework. 176 1.2 Document terminology and conventions 178 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 179 "SHOULD", SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 180 document are to be interpreted as described in RFC 2119. 182 NOTE: Comments like this provide additional nonessential 183 information about the rationale behind this document. 184 Such information is not needed for building a conformant 185 implementation, but may help those who wish to understand 186 the design in greater depth. 188 1.3 Discussion of this document 190 Discussion of this document should take place on the content 191 negotiation and media feature registration mailing list hosted by 192 the Internet Mail Consortium (IMC): 194 Please send comments regarding this document to: 196 ietf-medfree@imc.org 198 To subscribe to this list, send a message with the body 'subscribe' 199 to "ietf-medfree-request@imc.org". 201 To see what has gone on before you subscribed, please see the 202 mailing list archive at: 204 http://www.imc.org/ietf-medfree/ 206 RFC nnnn A syntax for describing media feature sets 207 29 October 1998 209 1.4 Amendment history 211 00a 28-Sep-1998 This memo created to contain a description of the 212 syntax-related features from a previous.draft "An 213 algebra for describing media feature sets". 214 Theoretical background material is replaced by a 215 more practically oriented introduction to the 216 concepts, and references to ASN.1 representation 217 have been removed. 219 00b 16-Oct-1998 Reinstated discussion of preferences and q-values 220 that was lost in the previous edit. Corrected 221 error in placement of "parameter" in formal 222 syntax. Added description of set construct in 223 syntax section. 225 01a 22-Oct-1998 Added references to previous TCN work. Move 226 discussion of named predicates and value units to 227 separate section, and other restructuring. Added 228 text dealing with handling of unknown data types. 230 02a 29-Oct-1998 Added feature set processing step to move logical 231 negations to apply directly to feature 232 comparisons. Added discussion of (non-)scoping of 233 features, based on RFC2301 MRC image data example. 234 Fix syntax for numbers and added explicit syntax 235 for Boolean values. 237 Revision history of "An algebra for describing media feature sets": 239 00a 11-Mar-1998 Document initially created. 241 01a 05-May-1998 Mainly-editorial revision of sections describing 242 the feature types and algebra. Added section on 243 indicating preferences. Added section describing 244 feature predicate syntax. Added to security 245 considerations (based on fax negotiation scenarios 246 draft). 248 01b 25-Jun-1998 New Internet draft boilerplate in 'status' 249 preface. Review and rationalization of sections 250 on feature combinations. Added numeric 251 expressions, named predicates and auxiliary 252 predicates as options in the syntax. Added 253 examples of text string predicate representation. 255 RFC nnnn A syntax for describing media feature sets 256 29 October 1998 258 02a 08-Jul-1998 Added chapter on protocol processing 259 considerations, and in particular outlined an 260 algorithm for feature set matching. Added 261 restrictions to the form of arithmetic expression 262 to allow deterministic feature set matching. 264 03a 27-Jul-1998 Simplified feature set handling by removing 265 options for expressions on the RHS of feature 266 comparison expressions. Syntax elements have been 267 added as placeholders for possible future 268 extensions in this area; examples have been 269 adjusted accordingly, and the feature set matching 270 algorithm greatly simplified. Add simple unit 271 designations. 273 1.5 Unfinished business 275 o Add worked example and source code for feature matching 276 implementation. 278 2. Content feature terminology and definitions 280 Feature Collection 281 is a collection of different media features and 282 associated values. This might be viewed as describing a 283 specific rendering of a specific instance of a document 284 or resource by a specific recipient. 286 Feature Set 287 is a set of zero, one or more feature collections. 289 NOTE: this term is used slightly differently by earlier 290 work on Transparent Content Negotiation in HTTP [4]. 292 Feature set predicate 293 A function of an arbitrary feature collection value which 294 returns a Boolean result. A TRUE result is taken to mean 295 that the corresponding feature collection belongs to some 296 set of media feature handling capabilities defined by 297 this predicate. 299 Other terms used in this draft are defined in [2]. 301 RFC nnnn A syntax for describing media feature sets 302 29 October 1998 304 3. Media feature combinations and capabilities 306 3.1 Media features 308 This memo assumes that individual media feature values are simple 309 atomic values: 311 o Boolean values. 313 o Enumerated values. 315 o Text string values (treated as atomic entities, like enumerated 316 value tokens). 318 o Numeric values (Integer or rational). 320 These values all have the property that they can be compared for 321 equality ('='), and that numeric and ordered enumeration values can 322 be compared for less-than and greater-than relationship ('<=', 323 '>='). These basic comparison operations are used as the primitive 324 building blocks for more comprehensive capability expressions. 326 3.2 Media feature collections and sets 328 Any single media feature value can be thought of as just one 329 component of a feature collection that describes some instance of a 330 resource (e.g. a printed document, a displayed image, etc.). Such 331 a feature collection consists of a number of media feature tags 332 (each per [3]) and associated feature values. 334 A feature set is a set containing a number of feature collections. 335 Thus, a feature set can describe a number of different data 336 resource instances. These can correspond to different treatments 337 of a single data resource (e.g. different resolutions used for 338 printing a given document), a number of different data resources 339 subjected to a common treatment (e.g. the range of different images 340 that can be rendered on a given display), or some combination of 341 these (see examples below). 343 Thus, a description of a feature set can describe the capabilities 344 of a data resource or some entity that processes or renders a data 345 resource. 347 3.3 Media feature set descriptions 349 A feature set may be unbounded. For example, in principle, there 350 is no limit on the number of different documents that may be output 351 using a given printer. But to be practically useful, a feature set 352 description must be finite. 354 RFC nnnn A syntax for describing media feature sets 355 29 October 1998 357 The general approach to describing feature sets is to start from 358 the assumption that anything is possible; i.e. the feature set 359 contains all possible document instances (feature collections). 360 Then constraints are applied that progressively remove document 361 instances from this set; e.g. for a monochrome printer, all 362 document instances that use colour are removed, or for a document 363 that must be rendered at some minimum resolution, all document 364 instances with lesser resolutions are removed from the set. The 365 mechanism used to remove document instances from the set is the 366 mathematical idea of a "relation"; i.e. a Boolean function (a 367 "predicate") that takes a feature collection parameter and returns 368 a Boolean value that is TRUE if the feature collection describes an 369 acceptable document instance, or FALSE if it describes one that is 370 excluded. 372 P(C) 373 P(C) = TRUE <- : -> P(C) = FALSE 374 : 375 +----------:----------+ This box represents some 376 | : | set of feature collections (C) 377 | Included : Excluded | that is constrained by the 378 | : | predicate P. 379 +----------:----------+ 380 : 382 The result of applying a series of such constraints is a smaller 383 set of feature collections that represent some media handling 384 capability. Where the individual constraints are represented by 385 predicates that each describe some media handling capability, the 386 combined effect of these constraints is some subset of the 387 individual constraint capabilities that can be represented by a 388 predicate that is the logical-AND of the individual constraint 389 predicates. 391 3.4 Media feature combination scenario 393 This section develops some exaple scenarios, introducing the 394 notation that is defined formally in the next section. 396 3.4.1 Data resource options 398 The following expression describes a data resource that can be 399 displayed either: 400 (a) as a 750x500 pixel image using 15 colours, or 401 (b) at 150dpi on an A4 page. 403 (| (& (pix-x=750) (pix-y=500) (color=15) ) 404 (& (dpi>=150) (papersize=iso-A4) ) ) 406 RFC nnnn A syntax for describing media feature sets 407 29 October 1998 409 3.4.2 Recipient capabilities 411 The following expression describes a receiving system that has: 412 (a) a screen capable of displaying 640*480 pixels and 16 million 413 colours (24 bits per pixel), 800*600 pixels and 64 thousand 414 colours (16 bits per pixel) or 1024*768 pixels and 256 colours 415 (8 bits per pixel), or 416 (b) a printer capable of rendering 300dpi on A4 paper. 418 (| (& (| (& (pix-x<=640) (pix-y<=480) (color<=16777216) ) 419 (& (pix-x<=800) (pix-y<=600) (color<=65535) ) 420 (& (pix-x<=1024) (pix-y<=768) (color<=256) ) ) 421 (media=screen) ) 422 (& (dpi=300) 423 (media=stationery) (papersize=iso-A4) ) ) 425 Note that this expression says nothing about the colour or grey- 426 scale capabilities of the printer. In the scheme presented here, 427 it is presumed to be unconstrained in this respect (or, more 428 realistically, any such constraints are handled out-of-band by 429 anyone sending to this recipient). 431 3.4.3 Combined options 433 The following example describes the range of document 434 representations available when the resource described in the first 435 example above is sent to the recipient described in the second 436 example. This is the result of combining their capability feature 437 sets: 439 (| (& (pix-x=750) (pix-y=500) (color=15) ) 440 (& (dpi=300) (media=stationery) (papersize=iso-A4) ) ) 442 The feature set described by this expression is the intersection of 443 the sets described by the previous two capability expressions. 445 3.5 Feature set predicates 447 There are many ways of representing a predicate. The ideas in this 448 memo were inspired by the programming language Prolog [5], and its 449 use of predicates to describe sets of objects. 451 For the purpose of media feature description in networked 452 application protocols, the format used for LDAP search filters 453 [7,8] has been adopted, because it is a good match for the 454 requirements of capability identification, and has a very simple 455 structure that is easy to parse and process. 457 RFC nnnn A syntax for describing media feature sets 458 29 October 1998 460 3.5.1 Comparison with directory search filters 462 Observe that a feature collection is similar to a directory entry, 463 in that it consists of a collection of named values. Further, the 464 semantics of the mechanism for selecting feature collections from a 465 feature set is in many respects similar to selection of directory 466 entries from a directory. 468 A feature set predicate used to describe media handling 469 capabilities is implicitly applied to some feature collection. 470 Within the predicate, members of the feature collection are 471 identified by their feature tags, and are compared with known 472 feature values. (Compare with the way an LDAP search filter is 473 applied to a directory entry, whose members are identified by 474 attribute type names, and compared with known attribute values.) 476 For example, in: 478 (& (dpi>=150) (papersize=iso-A4) ) 480 the tokens 'dpi' and 'papersize' are feature tags, and '150' and 481 'iso-A4' are feature values. (In a corresponding LDAP search 482 filter, they would directory entry attribute types and attribute 483 values.) 485 Differences between directory selection (per [7]) and feature set 486 selection are: 488 o Directory selection provides substring-, approximate- and 489 extensible- matching for attribute values. Directory selection 490 may also be based on the presence of an attribute without regard 491 to its value. 493 o Directory selection provides for matching rules that test for the 494 presence or absence of a named attribute type. 496 o Directory selection provides for matching rules which are 497 dependent upon the declared data type of an attribute value. 499 o Feature selection provides for the association of a quality value 500 with a feature predicate as a way of ranking the selected value 501 collections. 503 The idea of substring matching does not seem to be relevant to 504 feature set selection, and is excluded from these proposals. 506 Testing for the presence of a feature may be useful in some 507 circumstances, but does not sit comfortably within the semantic 508 framework. Feature sets are described by implied universal 509 quantification over predicates, and the absence of reference to a 511 RFC nnnn A syntax for describing media feature sets 512 29 October 1998 514 given feature means the set is not constrained by that feature. 515 Against this, it is difficult to define what might be meant by 516 "presence" of a feature, so the "test for presence" option is not 517 included in these proposals. An effect similar to testing for the 518 presence of a feature can be achieved by a Boolean-valued feature. 520 The idea of extensible matching and matching rules dependent upon 521 data types are facets of a problem not addressed by this memo, but 522 which do not necessarily affect the feature selection syntax. An 523 aspect that might bear on the syntax would be specification of an 524 explicit matching rule as part of a selection expression. 526 3.6 Describing preferences 528 A convenient way to describe preferences is by numeric "quality 529 values", as used in HTTP "Accept" headers, etc. (see RFC 2068 [9], 530 section 3.9). 532 It has been suggested that numeric quality values are potentially 533 misleading if used as more than just a way of ranking options. 534 Attempts to perform arithmetic on quality values do seem to 535 degenerate into meaningless juggling of numbers. 537 Numeric quality values in the range 0 to 1 (as defined by RFC 2068 538 [9], section 3.9) are used to rank feature sets according to 539 preference. Higher values are preferred over lower values, and 540 equal values are presumed to be equally preferred. Beyond this, 541 the actual number used has no significance defined by this memo, 542 and arithmetic operations using them are likely to produce 543 unpredictable results unless suitably defined for the context where 544 they are used. 546 In the absence of any explicitly applied quality value, a value of 547 "1" is assumed, suggesting an "ideal" option that is equally or 548 more preferred than any other. 550 Using the notation defined later, a quality value may be attached 551 to any feature set predicate sub-expression: 553 (| (& (pix-x=750) (pix-y=500) (color=15) );q=0.8 554 (& (dpi>=150) (papersize=iso-A4) ) ;q=0.7 ) 556 The next section explains that quality values attached to sub- 557 expressions are not always useful. 559 RFC nnnn A syntax for describing media feature sets 560 29 October 1998 562 3.7 Combining preferences 564 The general problem of describing and combining preferences among 565 feature sets is very much more complex than simply describing 566 allowable feature sets. For example, given two feature sets: 567 (& (a1);q=0.8 (b1);q=0.7 ) 568 (& (a2);q=0.5 (b2);q=0.9 ) 570 where: 571 feature a1 is preferred over a2 572 feature b2 is preferred over b1 574 Which of these feature sets is preferred? In the absence of 575 additional information or assumptions, there is no generally 576 satisfactory answer to this. 578 The proposed resolution of this issue is simply to say that no 579 rules are provided for combining preference information. Applied 580 to the above example, any preference information about (a1) in 581 relation to (a2), or (b1) in relation to (b2) is not presumed to 582 convey information about preference of (& (a1) (b1) ) in relation 583 to (& (a2) (b2) ). 585 In practical terms, this restricts the application of preference 586 information to top-level predicate clauses. A top-level clause 587 completely defines an allowable feature set; clauses combined by 588 logical-AND operators cannot be top-level clauses (see canonical 589 format for feature set predicates, described later). 591 NOTE: This memo does not apply specific meaning to 592 quality values or rules for combining them. Application 593 of such meanings and rules is not prohibited, but is seen 594 as an area for future research and experimentation. 596 4. Feature set representation 598 The foregoing sections have described a framework for defining 599 feature sets with predicates applied to feature collections. This 600 section presents a concrete representation for feature set 601 predicates. 603 4.1 Textual representation of predicates 605 The text representation of a feature set is based on RFC 2254 "The 606 String Representation of LDAP Search Filters" [8], excluding those 607 elements not relevant to feature set selection (discussed above), 608 and adding elements specific to feature set selection (e.g. options 609 to associate quality values with predicates). 611 RFC nnnn A syntax for describing media feature sets 612 29 October 1998 614 The format of a feature predicate is defined by the production for 615 "filter" in the following, using the syntax notation and core rules 616 of [10]: 618 filter = "(" filtercomp ")" *( ";" parameter ) 619 parameter = "q" "=" qvalue 620 / ext-param "=" ext-value 621 qvalue = ( "0" [ "." 0*3DIGIT ] ) 622 / ( "1" [ "." 0*3("0") ] ) 623 ext-param = ALPHA *( ALPHA / DIGIT / "-" ) 624 ext-value = 625 filtercomp = and / or / not / item 626 and = "&" filterlist 627 or = "|" filterlist 628 not = "!" filter 629 filterlist = 1*filter 630 item = simple / set / ext-pred 631 set = attr "=" "[" setentry *( "," setentry ) "]" 632 setentry = value "/" range 633 range = value ".." value 634 simple = attr filtertype value 635 filtertype = equal / greater / less 636 equal = "=" 637 greater = ">=" 638 less = "<=" 639 attr = ftag 640 value = fvalue 641 ftag = 642 fvalue = Boolean / number / token / string 643 Boolean = "TRUE" / "FALSE" 644 number = integer / rational 645 integer = [ "+" / "-" ] 1*DIGIT 646 rational = [ "+" / "-" ] 1*DIGIT "/" 1*DIGIT 647 token = ALPHA *( ALPHA / DIGIT / "-" ) 648 string = DQUOTE *(%x20-21 / %x23-7E) DQUOTE 649 ; quoted string of SP and VCHAR without DQUOTE 650 ext-pred = 652 (Subject to constraints imposed by the protocol that carries a 653 feature predicate, whitespace characters may appear between any 654 pair of syntax elements or literals that appear on the right hand 655 side of these productions.) 657 As described, the syntax permits parameters (including quality 658 values) to be attached to any "filter" value in the predicate (not 659 just top-level values). Only top-level quality values are 660 recognized. If no explicit quality value is given, a value of 661 '1.0' is applied. 663 RFC nnnn A syntax for describing media feature sets 664 29 October 1998 666 NOTE: The flexible approach to quality values and other 667 parameter values in this syntax has been adopted for two 668 reasons: (a) to make it easy to combine separately 669 constructed feature predicates, and (b) to provide an 670 extensible tagging mechanism for possible future use (for 671 example, to incorporate a conceivable requirement to 672 explicitly specify a matching rule). 674 4.2 Notational conveniences 676 A "set" item is simply a shorthand notation for some common 677 situations that can be expressed using "simple" item constructs. 678 Occurrences of "set" items can eliminated by applying the following 679 identities: 681 T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) ) 682 (T=[R1..R2]) --> (& (T>=R1) (T<=R2) ) 683 (T=[E]) --> (T=E) 685 Examples: 687 The expression: 688 ( paper-size=[A4,B4] ) 689 can be used to express a capability to print documents on either A4 690 or B4 sized paper. 692 The expression: 693 ( width=[4..8.5] ) 694 might be used to express a capability to print documents that are 695 anywhere between 4 and 8.5 inches wide. 697 The set construct is designed so that enumerated values and ranges 698 can be combined in a single expression, e.g.: 699 ( width=[3,4,6..8.5] ) 701 4.3 Feature set definition example 703 The following is an example of a feature predicate that describes a 704 number of image size and resolution combinations. 706 (| (& (Pix-x=1024) 707 (Pix-y=768) 708 (| (& (Res-x=150) (Res-y=150) ) 709 (& (Res-x=150) (Res-y=300) ) 710 (& (Res-x=300) (Res-y=300) ) 711 (& (Res-x=300) (Res-y=600) ) 712 (& (Res-x=600) (Res-y=600) ) ) 714 RFC nnnn A syntax for describing media feature sets 715 29 October 1998 717 (& (Pix-x=800) 718 (Pix-y=600) 719 (| (& (Res-x=150) (Res-y=150) ) 720 (& (Res-x=150) (Res-y=300) ) 721 (& (Res-x=300) (Res-y=300) ) 722 (& (Res-x=300) (Res-y=600) ) 723 (& (Res-x=600) (Res-y=600) ) ) ;q=0.9 724 (& (Pix-x=640) 725 (Pix-y=480) 726 (| (& (Res-x=150) (Res-y=150) ) 727 (& (Res-x=150) (Res-y=300) ) 728 (& (Res-x=300) (Res-y=300) ) 729 (& (Res-x=300) (Res-y=600) ) 730 (& (Res-x=600) (Res-y=600) ) ) ;q=0.8 732 5. Matching feature sets 734 This section presents a procedure for combining feature sets to 735 determine the common feature collections to which they refer, if 736 there are any. Making a selection from the possible feature 737 collections (based on q-values or otherwise) is not covered here. 739 Matching a feature set to some given feature collection is 740 esentially very straightforward: the feature set predicate is 741 simply evaluated for the given feature collection, and the result 742 (TRUE or FALSE) indicates whether the feature collection matches 743 the capabilities, and the associated quality value can be used for 744 selecting among alternative feature collections. 746 Matching a feature set to some other feature set is less 747 straightforward. Here, the problem is to determine whether or not 748 there is at least one feature collection that matches both feature 749 sets (e.g. is there an overlap between the feature capabilities of 750 a given file format and the feature capabilities of a given 751 recipient?) 753 This feature set matching is accomplished by logical manipulation 754 of the predicate expressions as described in the following 755 sections. 757 For this procedure to work reliably, the predicates must be reduced 758 to a canonical form. The canonical form used here is "disjunctive 759 normal form". A syntax for disjunctive normal form is: 761 filter = orlist 762 orlist = "(" "|" andlist ")" / term 763 andlist = "(" "&" termlist ")" / term 764 termlist = 1*term 765 term = "(" "!" simple ")" / simple 767 RFC nnnn A syntax for describing media feature sets 768 29 October 1998 770 where "simple" is as described previously in section 4.1. Thus, 771 the canonicalized form has at most three levels: an outermost 772 "(|...)" disjunction of "(&...)" conjunctions of possibly negated 773 feature value tests. 775 NOTE 777 The usual canonical form for predicate expressions is 778 "clausal form". Procedures for converting general 779 predicate expressions are given in [5] (section 10.2), 780 [11] (section 2.13) and [12] (section 5.3.2). 782 "Clausal form" for a predicate is similar to "conjunctive 783 normal form" for a proposition, being a conjunction 784 (logical AND) of disjunctions (logical ORs). The related 785 form used here, better suited to feature set matching, is 786 "disjunctive normal form", which is a logical disjunction 787 (OR) of conjunctions (ANDs). In this form, the aim of 788 feature set matching is to show that at least one of the 789 disjunctions can be satisfied by some feature collection. 791 Is this consideration of canonical forms really required? 792 After all, the feature predicates are just Boolean 793 expressions, aren't they? Well, no: a feature predicate 794 is a Boolean expression containing primitive feature 795 value tests (comparisons), represented by 'item' in the 796 feature predicate syntax. If these tests could all be 797 assumed to be independently TRUE or FALSE, then each 798 could be regarded as an atomic proposition, and the whole 799 predicate could be dealt with according to the 800 (relatively simple) rules of Propositional Calculus. 802 But, in general, the same feature tag may appear in more 803 than one predicate 'item', so the tests cannot be 804 regarded as independent. Indeed, interdependence is 805 needed in any meaningful application of feature set 806 matching, and it is important to capture these 807 dependencies (e.g. does the set of resolutions that a 808 sender can supply overlap the set of resolutions that a 809 recipient can handle?). Thus, we have to deal with 810 elements of the Predicate Calculus, with some additional 811 rules for algebraic manipulation. 813 A description of both the Propositional and Predicate 814 calculi can be found in [12]. 816 We aim to show that these additional rules are more 817 unfamiliar than complicated. The construction and use of 818 feature predicates actually avoids some of the complexity 819 of dealing with fully-generalized Predicate Calculus. 821 RFC nnnn A syntax for describing media feature sets 822 29 October 1998 824 5.1 Feature set matching strategy 826 The overall strategy for matching feature sets, expanded in the 827 following sections, is: 829 1. Formulate the feature set match hypothesis. 831 2. Replace "set" expressions with equivalent comparisons. 833 3. Move logical negations "inwards", so that they are all applied 834 directly to feature comparisons. 836 4. Eliminate logical negations, and express all feature comparisons 837 in terms of just four comparison operators 839 5. Reduce the hypothesis to canonical disjunctive normal form (a 840 disjunction of conjunctions). 842 6. For each of the conjunctions, attempt to show that it can be 843 satisfied by some feature collection. 845 6.1 Separate the feature value tests into independent feature 846 groups, such that each group contains tests involving just 847 one feature tag. Thus, no predicate in a feature group 848 contains a feature tag that also appears in some other 849 group. 851 6.2 For each feature group, merge the various constraints to a 852 minimum form. This process either yields a reduced 853 expression for the allowable range of feature values, or an 854 expression containing the value FALSE, which is an 855 indication that no combination of feature values can satisfy 856 the constraints (in which case the corresponding conjunction 857 can never be satisfied). 859 7. If the remaining disjunction contains at least one satisfiable 860 conjunction, then the constraints are shown to be satisfiable. 861 Further, it can be used as a statement of the resulting feature 862 set for possible further matching operations. 864 RFC nnnn A syntax for describing media feature sets 865 29 October 1998 867 5.2 Formulating the goal predicate 869 A formal statement of the problem we need to solve can be given as: 870 given two feature set predicates, '(P x)' and '(Q x)', where 'x' is 871 some feature collection, we wish to establish the truth or 872 otherwise of the proposition: 874 EXISTS(x) : (P x) AND (Q x) 876 i.e. does there exist a feature collection 'x' that satisfies both 877 predicates, 'P' and 'Q'? 879 Then, if feature sets to be matched are described by predicates 'P' 880 and 'Q', the problem is to determine if there is any feature set 881 satisfying the goal predicate: 883 (& P Q) 885 i.e. to determine whether the set thus described is non-empty. 887 5.3 Replace set expressions 889 Replace all "set" instances in the goal predicate with equivalent 890 "simple" forms: 892 T = [ E1, E2, ... En ] --> (| (T=[E1]) (T=[E2]) ... (T=[En]) ) 893 (T=[R1..R2]) --> (& (T>=R1) (T<=R2) ) 894 (T=[E]) --> (T=E) 896 5.4 Move logical negations inwards 898 The goal of this step is to move all logical negations so that they 899 are applied directly to feature comparisons. During the following 900 step, these logical negations are replaced by alternative 901 comparison operators. 903 This is achieved by repeated application of the following 904 transformation rules: 906 (! (& A1 A2 ... Am ) ) --> (| (! A1 ) (! A2 ) ... (! Am ) ) 907 (! (| A1 A2 ... Am ) ) --> (& (! A1 ) (! A2 ) ... (! Am ) ) 908 (! (! A ) ) --> A 910 The first two rules are extended forms of De Morgan's law, and the 911 third is elimination of double negatives. 913 RFC nnnn A syntax for describing media feature sets 914 29 October 1998 916 5.5 Replace comparisons and logical negations 918 The predicates are derived from the syntax described previously, 919 and contain primitive value testing functions '=', '<=', '>='. The 920 primitive tests have a number of well known properties that are 921 exploited to reach a useful conclusion; e.g. 923 (A = B) & (B = C) => (A = C) 924 (A <= B) & (B <= C) => (A <= C) 926 These rules form a core body of logic statements against which the 927 goal predicate can be evaluated. The form in which these 928 statements are expressed is important to realizing an effective 929 predicate matching algorithm (i.e. one that doesn't loop or fail to 930 find a valid result). The first step in formulating these rules is 931 to simplify the framework of primitive predicates. 933 The primitive predicates from which feature set definitions are 934 constructed are '=', '<=' and '>='. Observe that, given any pair 935 of feature values, the relationship between them must be exactly 936 one of the following: 938 (LT a b): 'a' is less than 'b'. 939 (EQ a b): 'a' is equal to 'b'. 940 (GT a b): 'a' is greater than 'b'. 941 (NE a b): 'a' is not equal and not related to 'b'. 943 (The final case arises when two values are compared for which no 944 ordering relationship is defined, and the values are not equal; 945 e.g. two unequal string values.) 947 These four cases can be captured by a pair of primitive predicates: 949 (LE a b): 'a' is less than or equal to 'b'. 950 (GE a b): 'a' is greater than or equal to 'b'. 952 The four cases described above are prepresented by the following 953 combinations of primitive predicate values: 955 (LE a b) (GE a b) | relationship 956 ---------------------------------- 957 TRUE FALSE | (LT a b) 958 TRUE TRUE | (EQ a b) 959 FALSE TRUE | (GT a b) 960 FALSE FALSE | (NE a b) 962 RFC nnnn A syntax for describing media feature sets 963 29 October 1998 965 Thus, the original 3 primitive tests can be translated to 966 combinations of just LE and GE, reducing the number of additional 967 relationships that must be subsequently captured: 969 (a <= b) --> (LE a b) 970 (a >= b) --> (GE a b) 971 (a = b) --> (& (LE a b) (GE a b) ) 973 Further, logical negations of the original 3 primitive tests can be 974 eliminated by the introduction of 'not-greater' and 'not-less' 975 primitives 977 (NG a b) == (! (GE a b) ) 978 (NL a b) == (! (LE a b) ) 980 using the following transformation rules: 982 (! (a = b) ) --> (| (NL a b) (NG a b) ) 983 (! (a <= b) ) --> (NL a b) 984 (! (a >= b) ) --> (NG a b) 986 Thus, we have rules to transform all comparisons and logical 987 negations into combinations of just 4 relational operators. 989 5.6 Conversion to canonical form 991 NOTE: Logical negations have been eliminated in the 992 previous step. 994 Expand bracketed disjunctions, and flatten bracketed conjunctions 995 and disjunctions: 997 (& (| A1 A2 ... Am ) B1 B2 ... Bn ) 998 --> (| (& A1 B1 B2 ... Bn ) 999 (& A2 B1 B2 ... Bn ) 1000 : 1001 (& Am B1 B2 ... Bn ) ) 1002 (& (& A1 A2 ... Am ) B1 B2 ... Bn ) 1003 --> (& A1 A2 ... Am B1 B2 ... Bn ) 1004 (| (| A1 A2 ... Am ) B1 B2 ... Bn ) 1005 --> (| A1 A2 ... Am B1 B2 ... Bn ) 1007 RFC nnnn A syntax for describing media feature sets 1008 29 October 1998 1010 The result is in "disjunctive normal form", a disjunction of 1011 conjunctions: 1013 (| (& S11 S12 ... ) 1014 (& S21 S22 ... ) 1015 : 1016 (& Sm1 Sm2 ... Smn ) ) 1018 where the "Sij" elements are simple feature comparison forms 1019 constructed during the step at section 7.1.4. Each term within the 1020 top-level "(|...)" construct represents a single possible feature 1021 set that satisfies the goal. Note that the order of entries within 1022 the top-level '(|...)', and within each '(&...)', is immaterial. 1024 From here on, each conjunction '(&...)' is processed separately. 1025 Only one of these needs to be satisfiable for the original goal to 1026 be satisfiable. 1028 (A textbook conversion to clausal form [5,11] uses slightly 1029 different rules to yield a "conjunctive normal form".) 1031 5.7 Grouping of feature predicates 1033 NOTE: remember that from here on, each conjunction is 1034 treated separately. 1036 Each simple feature predicate contains a "left-hand" feature tag 1037 and a "right-hand" feature value with which it is compared. 1039 To arrange these into independent groups, simple predicates are 1040 grouped according to their left hand feature tag ('f'). 1042 5.8 Merge single-feature constraints 1044 Within each group, apply the predicate simplification rules given 1045 below to eliminate redundant single-feature constraints. All 1046 single-feature predicates are reduced to an equality or range 1047 constraint on that feature, possibly combined with a number of non- 1048 equality statements. 1050 If the constraints on any feature are found to be contradictory 1051 (i.e. resolved to FALSE according to the applied rules), the 1052 containing conjunction is not satisfiable and may be discarded. 1053 Otherwise, the resulting description is a minimal form of that 1054 particular conjunction of the feature set definition. 1056 RFC nnnn A syntax for describing media feature sets 1057 29 October 1998 1059 5.8.1 Rules for simplifying ordered values 1061 These rules are applicable where there is an ordering relationship 1062 between the given values 'a' and 'b': 1064 (LE f a) (LE f b) --> (LE f a), a<=b 1065 (LE f b), otherwise 1066 (LE f a) (GE f b) --> FALSE, a FALSE, a<=b 1068 (LE f a) (NG f b) --> (LE f a), a (GE f a), a>=b 1072 (GE f b), otherwise 1073 (GE f a) (NL f b) --> (GE f a) a>b 1074 (NL f b), otherwise 1075 (GE f a) (NG f b) --> FALSE, a>=b 1077 (NL f a) (NL f b) --> (NL f a), a>=b 1078 (NL f b), otherwise 1079 (NL f a) (NG f b) --> FALSE, a>=b 1081 (NG f a) (NG f b) --> (NG f a), a<=b 1082 (NG f b), otherwise 1084 5.8.2 Rules for simplifying unordered values 1086 These rules are applicable where there is no ordering relationship 1087 applicable to the given values 'a' and 'b': 1089 (LE f a) (LE f b) --> (LE f a), a=b 1090 FALSE, otherwise 1091 (LE f a) (GE f b) --> FALSE, a!=b 1092 (LE f a) (NL f b) --> (LE f a) a!=b 1093 FALSE, otherwise 1094 (LE f a) (NG f b) --> (LE f a), a!=b 1095 FALSE, otherwise 1097 (GE f a) (GE f b) --> (GE f a), a=b 1098 FALSE, otherwise 1099 (GE f a) (NL f b) --> (GE f a) a!=b 1100 FALSE, otherwise 1101 (GE f a) (NG f b) --> (GE f a) a!=b 1102 FALSE, otherwise 1104 (NL f a) (NL f b) --> (NL f a), a=b 1105 (NL f a) (NG f b) --> (NL f a), a=b 1107 (NG f a) (NG f b) --> (NG f a), a=b 1109 RFC nnnn A syntax for describing media feature sets 1110 29 October 1998 1112 6. Other features and issues 1114 6.1 Named and auxiliary predicates 1116 Named and auxiliary predicates can serve two purposes: 1118 (a) making complex predicates easier to write and understand, and 1120 (b) providing a possible basis for naming and registering feature 1121 sets. 1123 6.1.1 Defining a named predicate 1125 A named predicate definition has the following form: 1127 named-pred = "(" fname *pname ")" ":-" filter 1128 fname = ftag ; Feature predicate name 1129 pname = token ; Formal parameter name 1131 'fname' is the name of the predicate. 1133 'pname' is the name of a formal parameter which may appear in the 1134 predicate body, and which is replaced by some supplied value when 1135 the predicate is invoked. 1137 'filter' is the predicate body. It may contain references to the 1138 formal parameters, and may also contain references to feature tags 1139 and other values defined in the environment in which the predicate 1140 is invoked. References to formal parameters may appear anywhere 1141 where a reference to a feature tag ('ftag') is permitted by the 1142 syntax for 'filter'. 1144 The only specific mechanism defined by this memo for introducing a 1145 named predicate into a feature set definition is the "auxiliary 1146 predicate" described later. Specific negotiating protocols or 1147 other specifications may define other mechanisms. 1149 NOTE: There has been some suggestion of creating a 1150 registry for feature sets as well as individual feature 1151 values. Such a registry might be used to introduce named 1152 predicates corresponding to these feature sets into the 1153 environment of a capability assertion. Further 1154 discussion of this idea is beyond the scope of this memo. 1156 RFC nnnn A syntax for describing media feature sets 1157 29 October 1998 1159 6.1.2 Invoking named predicates 1161 Assuming a named predicate has been introduced into the environment 1162 of some other predicate, it can be invoked by a filter 'ext-pred' 1163 of the form: 1165 ext-pred = fname *param 1166 param = expr 1168 The number of parameters must match the definition of the named 1169 predicate that is invoked. 1171 6.1.3 Auxiliary predicates in a filter 1173 A auxiliary predicate is attached to a filter definition by the 1174 following extension to the "filter" syntax: 1176 filter =/ "(" filtercomp *( ";" parameter ) ")" 1177 "where" 1*( named-pred ) "end" 1179 The named predicates introduced by "named-pred" are visible from 1180 the body of the "filtercomp" of the filter to which they are 1181 attached, but are not visible from each other. They all have 1182 access to the same environment as "filter", plus their own formal 1183 parameters. (Normal scoping rules apply: a formal parameter with 1184 the same name as a value in the environment of "filter" effectively 1185 hides the environment value from the body of the predicate to which 1186 it applies.) 1188 NOTE: Recursive predicates are not permitted. The 1189 scoping rules should ensure this. 1191 6.1.4 Feature matching with named predicates 1193 The preceding procedures can be extended to deal with named 1194 predicates simply by instantiating (i.e. substituting) the 1195 predicates wherever they are invoked, before performing the 1196 conversion to disjunctive normal form. In the absence of recursive 1197 predicates, this procedure is guaranteed to terminate. 1199 When substituting the body of a precdicate at its point of 1200 invocation, instances of formal parameters within the predicate 1201 body must be replaced by the corresponding actual parameter from 1202 the point of invocation. 1204 RFC nnnn A syntax for describing media feature sets 1205 29 October 1998 1207 6.1.4 Example 1209 This example restates that given in section 4.3 using an auxiliary 1210 predicate named 'Res': 1212 (| (& (Pix-x=1024) (Pix-y=768) (Res Res-x Res-y) ) 1213 (& (Pix-x=800) (Pix-y=600) (Res Res-x Res-y) );q=0.9 1214 (& (Pix-x=640) (Pix-y=480) (Res Res-x Res-y) );q=0.8 ) 1215 where 1216 (Res Res-x Res-y) :- 1217 (| (& (Res-x=150) (Res-y=150) ) 1218 (& (Res-x=150) (Res-y=300) ) 1219 (& (Res-x=300) (Res-y=300) ) 1220 (& (Res-x=300) (Res-y=600) ) 1221 (& (Res-x=600) (Res-y=600) ) ) 1222 end 1224 Note that the formal parameters of "Res", "Res-x" and "Res-y", 1225 prevent the body of the named predicate from referencing similarly- 1226 named feature values. 1228 6.2 Unit designations 1230 In some exceptional cases, there may be differing conventions for 1231 the units of measurement of a given feature. For example, 1232 resolution is commonly expressed as dots per inch (dpi) or dots per 1233 centimetre (dpcm) in different applications (e.g. printing vs 1234 faxing). 1236 In such cases, a unit designator may be appended to a feature value 1237 according to the conventions indicated below (see also [3]). These 1238 considerations apply only to features with numeric values. 1240 Every feature tag has a standard unit of measurement. Any 1241 expression of a feature value that uses this unit is given without 1242 a unit designation -- this is the normal case. When the feature 1243 value is expressed in some other unit, a unit designator is 1244 appended to the numeric feature value. 1246 The registration of a feature tag indicates the standard unit of 1247 measurement for a feature, and also any alternate units and 1248 corresponding unit designators that may be used, according to [3]. 1250 Thus, if the standard unit of measure for resolution is 'dpcm', 1251 then the feature predicate '(res=200)' would be used to indicate a 1252 resolution of 200 dots-per-centimetre, and '(res=72dpi)' might be 1253 used to indicate 72 dots-per-inch. 1255 RFC nnnn A syntax for describing media feature sets 1256 29 October 1998 1258 Unit designators are accommodated by the following extension to the 1259 feature predicate syntax: 1261 fvalue =/ number *WSP token 1263 When performing feature set matching, feature comparisons with and 1264 without unit designators, or feature comparisons with different 1265 unit designators, are treated as if they were different features. 1266 Thus, the feature predicate '(res=200)' would not, in general, fail 1267 to match with the predicate '(res=200dpi)'. 1269 NOTE: 1271 A protocol processor with specific knowledge of the 1272 feature and units concerned might recognize the 1273 relationship between the feature predicates in the above 1274 example, and fail to match these predicates. 1276 This appears to be a natural behaviour in this simple 1277 example, but can cause additional complexity in more 1278 general cases. Accordingly, this is not considered to be 1279 required or normal behaviour. It is presumed that an 1280 application concerned will ensure consistent feature 1281 processing by adopting a consistent unit for any given 1282 feature. 1284 6.3 Unknown feature value data types 1286 This memo has dealt with feature values that have well-understood 1287 comparison properties: numbers, with equality, less-than, greater- 1288 than relationships, and other values with equality relationships 1289 only. 1291 Some feature values may have comparison operations that are not 1292 covered by this framework. For example, strings containing multi- 1293 part version numbers: "x.y.z". Such feature comparisons are not 1294 covered by this memo. 1296 Specific applications may recognize and process feature tags that 1297 are associated with such values. Future work may define ways to 1298 introduce new feature value data types in a way that allows them to 1299 be used by applications that do not contain built-in knowledge of 1300 their properties. 1302 7. Examples and additional comments 1304 7.1 Worked example 1306 [[[TODO]]] 1308 RFC nnnn A syntax for describing media feature sets 1309 29 October 1998 1311 7.2 A note on feature tag scoping 1313 This section contains some additional commentary on the 1314 interpretation of feture set predicates. It does not extend or 1315 modify what has been described previously. Rather, it attempts to 1316 clarify an area of possible misunderstanding. 1318 The essential fact that needs to be established here is: 1320 Within a given feature collection, each feature tag may 1321 have only one value. 1323 This idea is explained below in the context of using the media 1324 feature framework to describe the characteristics of transmitted 1325 image data. 1327 In this context, we have the requirement that any feature tag value 1328 must apply to the entire image, and cannot have different values 1329 for different parts of an image. This is a consequence of the way 1330 that the framework of feature predicates is used to describe 1331 different possible images, such as the different images that can be 1332 rendered by a given recipient. 1334 This idea is illustrated here using an example of a flawed feature 1335 set description based on the TIFF image format defined for use by 1336 Internet fax [13]: 1338 (& (& (MRC-mode=1) (stripe-size=256) ) 1339 (| (& (image-coding=JBIG-2-LEVEL) (stripe-size=128) ) 1340 (image-coding=[MH,MR,MMR]) ) ) 1342 This example is revealing because the 'stripe-size' attribute is 1343 applied differently to different attributes on an MRC-formatted 1344 data: it can be applied to the MRC format as a whole, and it can 1345 be applied separately to a JBIG image that may appear as part of 1346 the MRC data. 1348 One might imagine that this example describes a stripe size of 256 1349 when applied to the MRC image format, and a separate stripe size of 1350 128 when applied to a JBIG-2-LEVEL coded image within the MRC- 1351 formatted data. But it doesn't work that way: the predicates used 1352 obey the normal laws of Boolean logic, and would be transformed as 1353 follows: 1355 --> [flatten nested (&...)]: 1356 (& (MRC-mode=1) (stripe-size=256) 1357 (| (& (image-coding=JBIG-2-LEVEL) (stripe-size=128) ) 1358 (image-coding=[MH,MR,MMR]) ) ) 1360 RFC nnnn A syntax for describing media feature sets 1361 29 October 1998 1363 --> [Distribute (&...) over (|...)]: 1364 (| (& (MRC-mode=1) (stripe-size=256) 1365 (& (image-coding=JBIG-2-LEVEL) (stripe-size=128) ) ) 1366 (& (MRC-mode=1) (stripe-size=[0..256]) 1367 (image-coding=[MH,MR,MMR]) ) ) 1369 --> [Flatten nested (&...) and group feature tags]: 1370 (| (& (MRC-mode=1) 1371 (stripe-size=256) 1372 (stripe-size=128) 1373 (image-coding=JBIG-2-LEVEL) ) 1374 (& (MRC-mode=1) 1375 (stripe-size=256) 1376 (image-coding=[MH,MR,MMR]) ) ) 1378 Examination of this final expression shows that it requires both 1379 'stripe-size=128' and 'stripe-size=256' within the same 1380 conjunction. This is manifestly false, so the entire conjunction 1381 must be false, reducing the entire predicate expression to: 1383 (& (MRC-mode=1) 1384 (stripe-size=256) 1385 (image-coding=[MH,MR,MMR]) ) ) 1387 This indicates that no MRC formatted data containing a JBIG-2-LEVEL 1388 coded image is permitted within the feature set, which is not what 1389 was intended in this case. 1391 The only way to avoid this in situations when a given 1392 characteristic has different constraints in different elements of 1393 an image is to use separate feature tags. In this example, 1394 'MRC-stripe-size' and 'JBIG-stripe-size' could be used to capture 1395 the intent: 1397 (& (& (MRC-mode=1) (MRC-stripe-size=256) ) 1398 (| (& (image-coding=JBIG-2-LEVEL) (JBIG-stripe-size=128) ) 1399 (image-coding=[MH,MR,MMR]) ) ) 1401 which would reduce to: 1403 (| (& (MRC-mode=1) 1404 (MRC-stripe-size=256) 1405 (JBIG-stripe-size=128) 1406 (image-coding=JBIG-2-LEVEL) ) 1407 (& (MRC-mode=1) 1408 (MRC-stripe-size=256) 1409 (image-coding=[MH,MR,MMR]) ) ) 1411 RFC nnnn A syntax for describing media feature sets 1412 29 October 1998 1414 The property of the capability description framework explicated 1415 above is captured by the idea of a "feature collection" which (in 1416 this context) describes the feature values that apply to a single 1417 image. Within a feature collection, each feature tag may have no 1418 more than one value. 1420 The characteristics of an image recipient are described by a 1421 "Feature set", which is formally a set of feature collections. 1422 Here, the feature set predicate is applied to some image feature 1423 collection to determine whether or not it belongs to the set that 1424 can be handled by an image recipient. 1426 8. Algorithm source code 1428 [[[TODO]]] 1430 9. Security considerations 1432 Some security considerations for content negotiation are raised in 1433 [1,2,3]. 1435 The following are primary security concerns for capability 1436 identification mechanisms: 1438 o Unintentional disclosure of private information through the 1439 announcement of capabilities or user preferences. 1441 o Disruption to system operation caused by accidental or malicious 1442 provision of incorrect capability information. 1444 o Use of a capability identification mechanism might be used to 1445 probe a network (e.g. by identifying specific hosts used, and 1446 exploiting their known weaknesses). 1448 The most contentious security concerns are raised by mechanisms 1449 which automatically send capability identification data in response 1450 to a query from some unknown system. Use of directory services 1451 (based on LDAP [7], etc.) seem to be less problematic because 1452 proper authentication mechanisms are available. 1454 Mechanisms which provide capability information when sending a 1455 message are less contentious, presumably because some intention can 1456 be inferred that person whose details are disclosed wishes to 1457 communicate with the recipient of those details. This does not, 1459 RFC nnnn A syntax for describing media feature sets 1460 29 October 1998 1462 however, solve problems of spoofed supply of incorrect capability 1463 information. 1465 The use of format converting gateways may prove problematic because 1466 such systems would tend to defeat any message integrity and 1467 authenticity checking mechanisms that are employed. 1469 10. Full copyright statement 1471 Copyright (C) The Internet Society 1998. All Rights Reserved. 1473 This document and translations of it may be copied and furnished to 1474 others, and derivative works that comment on or otherwise explain 1475 it or assist in its implementation may be prepared, copied, 1476 published and distributed, in whole or in part, without restriction 1477 of any kind, provided that the above copyright notice and this 1478 paragraph are included on all such copies and derivative works. 1479 However, this document itself may not be modified in any way, such 1480 as by removing the copyright notice or references to the Internet 1481 Society or other Internet organizations, except as needed for the 1482 purpose of developing Internet standards in which case the 1483 procedures for copyrights defined in the Internet Standards process 1484 must be followed, or as required to translate it into languages 1485 other than English. 1487 The limited permissions granted above are perpetual and will not be 1488 revoked by the Internet Society or its successors or assigns. 1490 This document and the information contained herein is provided on 1491 an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET 1492 ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR 1493 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1494 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1495 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1497 11. Acknowledgements 1499 Thanks are due to Larry Masinter for demonstrating the breadth of 1500 the media feature issue, and encouraging the development of some 1501 early thoughts. 1503 Many of the ideas presented derive from the "Transparent Content 1504 Negotiation in HTTP" work of Koen Holtman and Andy Mutz [4]. 1506 Early discussions of ideas with the IETF HTTP and FAX working 1507 groups led to further useful inputs from Koen Holtman, Ted Hardie 1508 and Dan Wing. The debate later moved to the IETF conneg working 1509 group, where Al Gilman and Koen Holtman were particularly helpful 1511 RFC nnnn A syntax for describing media feature sets 1512 29 October 1998 1514 in refining the feature set algebra. Ideas for dealing with 1515 preferences and specific units were suggested by Larry Masinter. 1517 This work was supported by Content Technologies Ltd and 5th 1518 Generation Messaging Ltd. 1520 12. References 1522 [1] "Scenarios for the Delivery of Negotiated Content" 1523 T. Hardie, NASA Network Information Center 1524 Internet draft: 1525 Work in progress, November 1997. 1527 [2] "Requirements for protocol-independent content negotiation" 1528 G. Klyne, Integralis Ltd. 1529 Internet draft: 1530 Work in progress, March 1998. 1532 [3] "Media Feature Tag Registration Procedure" 1533 Koen Holtman, TUE 1534 Andrew Mutz, Hewlett-Packard 1535 Ted Hardie, NASA 1536 Internet draft: 1537 Work in progress, July 1998. 1539 [4] RFC 2295, "Transparent Content Negotiation in HTTP" 1540 Koen Holtman, TUE 1541 Andrew Mutz, Hewlett Packard 1542 March 1998. 1544 [5] "Programming in Prolog" (2nd edition) 1545 W. F. Clocksin and C. S. Mellish, 1546 Springer Verlag 1547 ISBN 3-540-15011-0 / 0-387-15011-0 1548 1984. 1550 [6] "Media Features for Display, Print, and Fax" 1551 Larry Masinter, Xerox PARC 1552 Koen Holtman, TUE 1553 Andrew Mutz, Hewlett-Packard 1554 Dan Wing, Cisco Systems 1555 Internet draft: 1556 Work in progress, January 1998. 1558 [7] RFC 2251, "Lightweight Directory Access Protocol (v3)" 1559 M. Wahl, Critical Angle Inc. 1560 T. Howes, Netscape Communications Corp. 1561 S. Kille, Isode Limited 1562 December 1997. 1564 RFC nnnn A syntax for describing media feature sets 1565 29 October 1998 1567 [8] RFC 2254, "The String Representation of LDAP Search Filters" 1568 T. Howes, Netscape Communications Corp. 1569 December 1997. 1571 [9] RFC 2068, "Hyptertext Transfer Protocol -- HTTP/1.1" 1572 R. Fielding, UC Irvine 1573 J. Gettys, 1574 J. Mogul, DEC 1575 H. Frytyk, 1576 T. Berners-Lee, MIT/LCS 1577 January 1997. 1579 [10] RFC 2234, "Augmented BNF for Syntax Specifications: ABNF" 1580 D. Crocker (editor), Internet Mail Consortium 1581 P. Overell, Demon Internet Ltd. 1582 November 1997. 1584 [11] "Logic, Algebra and Databases" 1585 Peter Gray 1586 Ellis Horwood Series: Computers and their Applications 1587 ISBN 0-85312-709-3/0-85312-803-3 (Ellis Horwood Ltd) 1588 ISBN 0-470-20103-7/0-470-20259-9 (Halstead Press) 1589 1984. 1591 [12] "Logic and its Applications" 1592 Edmund Burk and Eric Foxley 1593 Prentice Hall, Series in computer science 1594 ISBN 0-13-030263-5 1595 1996. 1597 [13] RFC 2301, "File format for Internet fax" 1598 L. McIntyre, 1599 R. Buckley, 1600 D. Venable, Xerox Corporation 1601 S. Zilles, Adobe Systems, Inc. 1602 G. Parsons, Northern Telecom 1603 J. Rafferty, Human Communications 1604 March 1998. 1606 RFC nnnn A syntax for describing media feature sets 1607 29 October 1998 1609 13. Author's address 1611 Graham Klyne 1612 Content Technologies Ltd. 5th Generation Messaging Ltd. 1613 Forum 1 5 Watlington Street 1614 Station Road Nettlebed 1615 Theale Henley-on-Thames 1616 Reading, RG7 4RA RG9 5AB 1617 United Kingdom United Kingdom. 1619 Telephone: +44 118 930 1300 +44 1491 641 641 1621 Facsimile: +44 118 930 1301 +44 1491 641 611 1623 E-mail: GK@ACM.ORG