Structured Text
Text models
Stream: of characters, words, paragraphs, page images.
Document: monolithic stream, fielded record, nested fields
(tree or forest), graph.
Document collection: sequence, set, graph.
Text extents
Mechanism: fixed width, superimposed (external) structures,
markup (inline tags).
Terminators: explicit vs. implicit.
Tag semantics: presentation, procedural, descriptive.
Constraints
Purpose: consistency (creation or update), efficiency
(storage, access)
Forms:
None
(self-defining structure)
Grammars:
regular expression, context-free language, regular right-part grammar
Algebraic: data
types, relational
Semi-structured data
Lore data model
Based on OEM directed graph model developed as part of
Tsimmis project at Stanford
- sinks
(leaves) represent atomic values
- internal
nodes represent compound objects, labelled by unique object identifiers
(OIDs)
- some
nodes are "entry points" labelled by names
- directed
edges are labelled by role names
- edges
can be represented as triples <source OID, label, target OID or atomic
value>
No schema no
constraints whatsoever placed on possible instances.
Example: encyclopedia bibliography
DataGuide
Abstraction of relationships that are found in the data
- Helps guide
query formulation
- Serves
as basis for an index
Construction similar to converting NFA to DFA, and as a result
- For
every path, the set of all OIDs (or values) reachable from a root in the
database instance by that path will be represented by a unique node in the
DataGuide.
- For
every edge in the DataGuide with label L connecting N1 to N2, there will
be some edge <S,L,T> in the instance such that the OID for S is in
the set corresponding to N1 and the OID for T is in the set corresponding
to N2.
Properties of the DataGuide:
- Every
path starting from a root in the database has one and only one
corresponding path in the DataGuide with the same sequence of labels.
- Cycles
in the database correspond to cycles in the DataGuide.
XML data models
- InfoSet
Tree-structured, with nodes (information items) for Document, Element, Attribute, Processing Instruction, Unexpanded Entity Reference, Character, Comment, DTD, Unparsed Entity (declaration), Notation (declaration), Namespace. Each node type has properties defined (e.g., children, parent, value)
- XQuery 1.0 and XPath 2.0
Tree-structured, with nodes for Document, Element, Attribute, Processing Instruction, Text, Comment, Namespace. The properties are similar to, but not identical to, those defined for the corresponding nodes in the InfoSet.
XML interfaces
SAX : stream, event-based
DOM : tree-structure, object-oriented (types and methods);
“live” document
XPath expressions
- single step: "axis::node-test[predicate]"
axes: child, desendent, parent, ancestor, self, descendent-or-self, ancestor-or-self, following-sibling, preceding-sibling, following, preceding, attribute, namespace
- path: "/" step | step | path "/" step
- abbreviated notation (/, //, ., .., @)
References and related reading
Querying XML, Chapters 2, 3, 6, 9
|
|
||||