- data guide is a concise and accurate summary of a data graph
-
accurate: every path in the data occurs in the data guide,
and vice versa
-
concise: every path in the data guide occurs exactly
once
- data guide is the most specific schema graph for a
given data graph
i.e., there is a simulation from the data guide to every other schema
graph the data graph satisfies
- data graph is analogous to a nondeterministic finite state
automaton (NFA)
- given NFA N, data guide is analogous to a
deterministic finite state automaton (DFA) equivalent to
NFA N
- conversion from NFA to DFA can result in exponential increase in
size
