这门课主要是讲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
