Lit / HKT10

HKT10: Sven Hartmann, Henning Köhler, Thu Trinh. On the Existence of Armstong Data Trees for XML Functional Dependencies

{lit+ textvar Lit.Lit$:FoIKS10 is undefined or empty} pp 94-113

XML Tree:

  • tree T mit root rT ∈ VT Nodes and Arcs AT
  • names: VT → Names gibt die KnotenNamen
  • kind: VT → {E,A,S} unterscheided Entities, Attribute und Strings (cdata),
  • LT = alle A und S Knoten, sind immer Leaves
  • walk: Weg von der root zu einem leaf
  • rT-subgraph von T = graph union einer Menge W von walks

XML Data Tree T' = XML Tree +

  • val: LT → STRING die Evaluationsfunktion mit StringWerten

Homomorphismus Φ:T → T' ist Funktion auf den Knoten, die root-, arcs-, names- und kind-treu

  • value-equal Iso auf XMLDataTrees, evaluation-treu

XML Schema Tree: ein XML Tree plus

  • kein Knoten hat mehrer Successors desselben Namens
  • freq: AT → {?, 1, +,*} die erlauben Multiplizitäten (?=0 oder 1 usw. wie in regular Expressions)
  • für XML: Arc auf A-Knoten hat Muliplizität ? und 1 auf S-Knoten, diese Einschränkung kann aber auch weggelassen werden
  • T' ⟩ T: XML DataTree T' ist kompatibel mit Schema T, d.h. es ∃ Φ: T' → T, das die Multiplizitäten freq respektiert. Falls Φ existiert ist es eindeutig.

Für T' ⟩ T ist

  • ein subgraph H' von T' ist eine copy von H von T wenn die Einschränkung von Φ auf H' iso
  • ein subgraph H' von T' ist eine subcopy von T, falls ∃ H' für copy
  • subcopy ist maximal falls nicht echt enthalt in eine subcopy von T (für dieses Φ: T' → T)
  • almost-copy von T = nicht leeres maximales subcopy

XFD = XML Function dependency ist X → Y mit

  • X und Y rT-subgraphs von T
  • ∀ T', T", almost-copies von T': falls T' und T" auf X value-equal sind , dann auch auf Y

Reasoning about XFDs: AxiomenSystem: Achtung Transitivität gilt nur mit Zusatzbedingungen! Haben in einem anderen Papier ein sound und complete RuleSystem gebracht.

Charactzerising Armstron DataTrees: Ein XMLDataTree T' ⟩ T heisst 'Armstrong' für eine Menge Σ von XFDs, falls T' jedes XFD ∈ Σ erfüllt und jedes XFD ∉ Σ verletzt. Charakterisiert Armstrong Datatrees mithilfe von Agree und Difference Sets (in Anlehnung zum relationalen Fall). Aber zu einem XML Schema und einer Menge von XFDs, braucht kein Armstrong Tree zu exsistieren.

Existenzbedingung von Armstrong Data Trees

Diskussion:

  • XFDs immer an der Wurzel aufgehängt sind, scheint mir unnatürlich. XML ist doch beliebig geschachtelt!
  • das XFDs mit almostCopies definiert sind, werden die gleichnamigen Siblings immer auf ein reduziert, so einfache Redundanzen wie Anzahl childrenn fallen so durch