A Syntax for Describing Media Feature Sets
updated by
Extracted elements (29)
Disjunctive normal form (OR of ANDs) was chosen over the more common clausal/conjunctive normal form because the goal of feature set matching is to find at least one satisfiable disjunction, which maps more naturally to DNF. The feature tag interdependence requires Predicate Calculus rather than simpler Propositional Calculus.
No rules are defined for combining quality values across AND-combined sub-predicates; preference information is only meaningful at the top-level OR clause level. Combining sub-predicate preferences is considered an unresolved research problem and is left to specific protocol extensions.
Quality value parameters are permitted on any sub-expression in the syntax (not just top-level) for two reasons: (a) to ease composition of separately constructed predicates, and (b) to provide an extensible tagging mechanism for future uses such as explicit matching-rule specification.
The feature set framework starts from the assumption that any feature collection is possible, then progressively excludes instances via Boolean predicates. This predicate-as-relation approach allows the same expression form to describe sender, receiver, and file format capabilities uniformly.
The LDAP search filter syntax (RFC 2254) was adopted for feature predicate notation because a feature collection is analogous to a directory entry (named values), and LDAP filters provide a well-understood structure that is easy to parse. Differences include absence of substring/approximate matching and the addition of quality values.
When a characteristic has different constraints for different parts of a resource (e.g., MRC stripe-size vs. JBIG stripe-size), separate feature tags must be used. A single feature tag within a conjunction can only hold one value; attempting to assign it two values produces an unsatisfiable predicate.
Feature values with comparison semantics not covered by this framework (e.g., multi-part version strings like 'x.y.z') are outside the scope of this specification. Specific applications may define handling, and future work may define extensible data types.
This document's use of 'feature set' differs from Transparent Content Negotiation in HTTP (RFC 2295), which uses the term with a slightly different meaning. Quality value semantics here are also more restricted than those in RFC 2068 HTTP Accept headers.
Unit designators with different tokens (e.g., default dpcm vs. 'dpi') are treated as distinct features during matching, so '(res=200)' and '(res=200dpi)' will not fail to match each other unless a processor with explicit unit knowledge intervenes. Applications should ensure consistent unit usage to avoid spurious mismatches.
Feature comparisons with and without unit designators, or with different unit designators, are treated as if they involve different features during matching. A predicate '(res=200)' does not automatically match '(res=200dpi)', even if the numeric values are equivalent.
Feature tags used to describe capabilities SHOULD be registered using the procedures in RFC 2506. Unregistered feature tags SHOULD be allocated in the 'URI tree' as described in that memo.
If an unrecognized feature tag is encountered during feature set predicate processing, it should still be processed as a legitimate feature tag. The matching rules are designed to allow new tags without affecting existing capability assertions.
Less-than and greater-than comparisons on non-numeric feature values amount to equality tests because no ordering relation on non-numeric values is defined by this specification. Specific applications may define such ordering for specific feature tags.
Only top-level quality values are recognized for ranking purposes. Quality values attached to sub-expressions inside an AND or OR are syntactically permitted but have no defined effect on preference ordering.
Within a given feature collection, each feature tag may have only one value. A feature predicate that requires the same tag to equal two different values within a single conjunction is always unsatisfiable (evaluates to FALSE) and the conjunction is discarded.
During matching, all comparisons and negations are reduced to four relational operators: LE ('<='), GE ('>='), NL (strict less-than, i.e., NOT GE), and NG (strict greater-than, i.e., NOT LE). The original '=', '<=', '>=' and their negations are translated into combinations of these four primitives.
Feature values are typed as Boolean (TRUE/FALSE, case-insensitive), numeric (decimal integer or rational 'n/m' with optional sign), token (letters/digits/hyphens), or quoted string. Numeric values may appear as rationals where multiple forms (e.g., 3/2, +15/10, 600/400) can represent the same value.
Named predicates can be defined with the form '(fname *pname) :- filter' and invoked via 'ext-pred'. Auxiliary predicates are scoped to a 'filter...where...end' block; they are not mutually visible and recursive predicates are not permitted.
Quality values are numeric parameters in the range 0 to 1 (up to 3 fractional digits) attached to any filter sub-expression with ';q=qvalue' syntax. Higher values are preferred; absent quality values default to 1.0. Only top-level quality values are recognized for ranking.
The canonical (disjunctive normal) form of a feature predicate has at most three levels: an outermost '(|...)' disjunction of '(&...)' conjunctions of possibly negated simple feature comparisons. This form is required for the matching algorithm to work reliably.
The 'set' shorthand syntax allows expressing enumerated values and ranges in a single item: 'T=[E1,E2,...En]' expands to a disjunction of equalities, and 'T=[R1..R2]' expands to '(& (T>=R1) (T<=R2))'. This is a notational convenience with no additional semantic content.
Unit designations may be appended to numeric feature values (e.g., '72dpi') to indicate a non-standard unit of measurement. The feature tag registration (RFC 2506) specifies the standard unit and any permitted alternates with their designator tokens.
Within each conjunction of the disjunctive normal form, simple predicates are grouped by their left-hand feature tag. Simplification rules are then applied per group to merge overlapping constraints and detect contradictions (resolved to FALSE), eliminating unsatisfiable conjunctions.
A capability identification mechanism could be used to probe a network by identifying specific hosts and exploiting their known weaknesses. Directory-service-based approaches (LDAP) are considered less problematic because proper authentication mechanisms are available.
Accidental or malicious provision of incorrect capability information can disrupt system operation. Mechanisms that provide capability data when sending a message are less contentious than those that auto-respond to queries, but neither addresses spoofed capability assertions.
Capability identification mechanisms risk unintentional disclosure of private information through the announcement of capabilities or user preferences, particularly when automatically responding to queries from unknown systems.
Format-converting gateways are problematic because they tend to defeat message integrity and authenticity checking mechanisms, potentially allowing undetected modification of capability information in transit.
Feature set matching uses a 7-step algorithm: (1) formulate AND of both predicates; (2) expand 'set' notation; (3) push negations inward via De Morgan's laws; (4) eliminate negations by substituting LE/GE/NL/NG operators; (5) reduce to disjunctive normal form; (6) for each conjunction, group by feature tag and merge constraints; (7) if any conjunction survives unsatisfied, the feature sets overlap.
The feature predicate is defined by an ABNF grammar (based on RFC 2254 LDAP search filters) where a 'filter' is a parenthesized 'filtercomp' followed by optional parameters. Composite forms are '(&...)' for AND, '(|...)' for OR, and '(!...)' for NOT; simple comparisons use 'attr filtertype value' with filtertype being '=', '>=', or '<='.