Type and Coding

November 24, 2004

Basic idea Is it necessary that coding keeps same for different type? I dn't think so. Why the xml is verbose? I think it is because xml text represenation use a unified represenation for any type in the xml infoset. Or we say xml text represeatntion is suitable for xml inforset withoug xml-schema, but not suitable for a xml infoset with xml-schema;

So in a whole message, different part can have different encoding rule based on the type of that part for the coding performance. Basically this idea is not exactly the one of binary xml which also uses a unified encoding rules but in binary format, it is the basic idea behind of the BOXSA and BXSA;

I am thinking using tree grammar to give a taxonomy of the realationship between type and coding. If you are not familiar with tree grammer , then ``Taxonomy of XML Schema Languages using Formal Language Theory'' is recommended;

Information in a message

• DATA
• NAME
• SIZE (Optional), which can represented as a number or a delimiter;
• Encoding Meta Data

Taxonomy of Message Encoding

• Self-descriptive Representation:
  The message will inlcude the NAME, DATA,SIZE (option) and ENCODING META DATA; For example XML text representation is the one, and XBIS and other current binary XML is also in this category, but just with binary representation;

• No-self-descriptive representation:
  Given a message, if we can tell what the parts of the message is by the position in the message , then we call the message is position determinable. In other word, by the position determainable schema we can stataically decide the position of any part in the message. The position determainable scheme will save lots of time for serializatioin and deserailization since the native data representation can be used and eliminates the need for any coding conversion; The message will only inlcude the DATA and ENCODING META DATA;

  OpenMetaData(PBIO) is an example of this policy.

• Semi-self-decriptive representation:
  Position determinable schema gives too much constraints to be a flexible; Most time, we have dynamic lenght part in the message, like string and array; So just with the schema, we can't decide the which part is in the mesesage; Sometime we need put some extra information in the message, like lenght followed by the part; or delimiter at the end of part. This time the a little bit formate converstion will be done when serializing and deserailizing, it will be slower than the one with position determainble schema; The message will only inlcude the DATA and SIZE and ENCODING META DATA;;

  XBS and lots of other binary data representation will use

• DFDL?

Taxonomy of Message Type for the high performance encoding

• Location Determinable Type
  

  The tree grammar, the production rule only use , in its regular expression such as Doc -> doc(Para1, Para2)

  In this case, the NAME information for every child element is redundent if the size of the representation of the element is known and SIZE information is associated with every child element;

  If the size of every child element is fixed/static, then SIZE information also is redundant, only DATA is needed (i.e. NO-self-descriptive)

  The XML-Schema is <sequence> <a> <b> </sequence>

• Location-Size Determinable Type
  

  The tree grammar, the production rule only use , * or ? in its regular expression ,such as Doc -> doc(Para1, Para2*)

  In this case, the NAME information of Para2 isnot totally redundant since we need to check the last element or whether it is null; However if the SIZE of Para2* can be provied in the message, then the NAME information of Para2 can be omitted (i.e. Semi-self-descriptive); For example, a dynamical array of double;

  The XML-Schema is <element name = 'a' maxOccurance = 100>

• Name Determinable Type
  

  The tree grammar, the production rule will have | in its regular expression ,such as Doc -> doc(Para1 | Para2)

  In this case, the NAME information is necessary since we need to tell which elemement does appear in the message; For this message type, we need the NAME and DATA, (note SIZE is optional due to the NAME) (i.e.Self discriptive representation)

  The XML-Schema is <choice> <a> <b> </choice>