这门课主要是讲web上的data模型，侧重在xml上

1.Semi-Structured Data (SSD)

由于自然语言和二进制所写的数据总会造成对于人类或者机器阅读的不友好，所以需要一种对于human-machine 都readable 的语言。这样就不用专门写解释器了。

我们可以利用tree来表示SSD这种结构

属于该结构下的有：XML，JSON，Lore，Object Exchange Model

2.XML

xml （eXtensible Markup Language），是ssd的一种用来存储数据的data model，并不是文档的布局工具。

3.XML：Basics

可利用tree来表示，data中的一小块都可以称为是element，不存在二义性的层次结构，有一个root节点来包含所有的element，不需要解释器。

<?xml version="1.0" encoding="utf-8" ?>

<!DOCTYPE book SYSTEM "book.dtd"> ／／指明该文档为book类型，且可由book.dtd对其进行校验

element用tags来修饰<book>,</book> or <book/>, 对于element的名字是区分大小写的

element内部可以存在attribute <boook title="jshkaf"/> ／／attribute不能定义两次 

XML：well-formed

exactly one root element

tags inside <> are correct

tags are nested

attribute are unique and quoted

no comments inside the tags

或者简单一点，可以用tree来表示这个xml文档

XML：Valid

可以利用DTD，XML Schema，Relax NG来对XML中的数据进行校验

DTD：利用正则表达式来表达允许出现的文档格式

<!ELEMENT elem_name elem_regexp>

element regular expression: *,+,?, [,], EMPTY, ANY, #PCDATA(text)

mixed element could be (#PCDATA|sub_element)

<!ATTLIST elem_name 

                  att_name att_type att_values>

attribute type: ID, IDREF(FK), CDATA, v1|v2|..., vn

attribute values: #REQUIRED,  #IMPLIED, #FIXED v

4. VALID in xml:

利用dtd来进行validation的过程，讲正则表达式转化为一个自动机让它进行识别的过程。

自动机有两种DFA和NFA，DFA指的就是每个状态根据action只能到达下一个状态，而NFA在于每个状态根据相应的action可能可以到达多个状态。每一个NFA都可以转化为DFA，但是需要指数级的空间，evalution时可能并不是很有效。W3C要求使用乔姆斯基automaton，需要1-unambigous的形式

所以dtd利用FA来进行validation时采用top-down的形式：

1.对于每个<!ELEMENT...>开始的建立它自己相对应的automaton A

2. 对于Document D中的每个元素对它进行匹配相应的自动机

3. 若出现不匹配项则return no valid

4. 若全部match 则document valid

缺点：

dtd不是xml形式的。。。。

利用XML SChema进行匹配

<xsd: element name="name"/>

<xsd: element name = "x", minOccurs="1",maxOccurs="unbounded",type="xsd:date">

type: string, boolean, number, float, time, duration, base64binary, AnyURI...

利用tree automata 进行xml校验

Tree 分为两种：

rank: every node has bounded number of children

unranked: doesn't have that rule

unranked => rank tree using first-child next-sibling

bottom-up non-deterministic tree automata:

A=(alphabet, states, accept_states, transition)

从叶子节点向上推导，直至root节点，若root节点的状态属于终态集中，则将之称为accepting

能被这样一个树形自动机识别的语言被称为：regular tree language

Top-down tree automata

A=(alphabet, states, initial_states, accept_states, transition)

从root节点向下推导直至所有叶子节点都属于终态集则accept

regular tree language= accept by non-deterministic bottom-up = deterministic bottom-up= non-deterministic top-down

f{epsilon}-> Qf

d{Qf}->Qd

a{Qb*,QC+}->QA

5. Regular Tree grammars

G=(N,T,S,P)

N: non-terminal symbols

T: terminal symbols

S: start symbols 

P: production rules

Dir-> directory[Person*]

Perosn->person{epsilon}

RelaxNG

Competing NON-terminals:

AB are non-terminals, A->x[shdjfk], B->x[sdfdsg]

then call AB competing non-terminals

Local tree gramma:

there is no competing non-terminals

(dtd)

Sing-type tree gramma:

the competing non-terminals should not show in the same content.

(XML Schema)

Restrained Competition Gramma:

the competing non terminals could show in the same content but without the same pre..

there should not have UAV and UBW show in the same time

simple example:

Person→student[DirA])

Person→professor[DirB]

DirA→direction[Name.Number?.Add?]

DirB→direction[Name.Add?.Phone∗]

the gramma is STG but not RCG not LTG