XML Und Formale Sprachen - TU Dortmund
�··amakerpriceeaeceaaecVor 2500lauter Bäumen.“”XML und formale Spracheneceecea”Gibson”MarburgaMärz 2005 bca Thomas Schwentickba c0 11 00 111
Bevor es losgeht.Meine Forschungsgebiete Grundlagen von Datenbanken Logik in der Informatik Komplexitätstheorie Automaten und Formale SprachenAktueller ForschungsschwerpunktGrundlagen von Anfragesprachen für semistrukturierte DatenZiel des Vortrags XML und Datenbanken Formalsprachliche Konzepte im Zusammenhang mit XML Verwendbarkeit für die Schule? Keine (!) Einführung in XMLSchwentickLogik für XMLEinleitung1
XML: Ein erster Blick. als BaumClaude poserMarriedDiedPTitleLa MerPYear1905InstrumentsLarge orchestraMovements3PieceBeobachtungen XML ist einfach XML ist selbstbeschreibend XML ist flexibel XML ist nichts Besonderes XML ist baumartigSchwentickLogik für XMLXML und Datenbanken2
InhaltXML und DatenbankenXML und Formale SprachenFazit
XML: Wozu?Bemerkungen Ursprünglich: Datenaustausch im Internet Zusätzlich: Lingua Franca der Datenintegration Zwei Welten repräsentierbar: Relationale Daten undDokumente In der Forschung: Neues Datenmodell für Datenbanken Allgemeinerer Ansatz: Semistrukturierte Daten (Graph stattBaum)SchwentickLogik für XMLXML und Datenbanken4
XML vs. Relationale DatenbankenRelationale Datenbanken Deklarative Anfragen Mengenorientierte Auswertungsalgebra Effiziente Auswertung Starres Schema Ordnungsprinzip: TabellenXML Anfragesprachen: fortgeschrittene Standards Navigation Auswertungsstrategien: Baustelle Ordnungsprinzip: Bäume XML-Datenbanken?SchwentickLogik für XMLXML und Datenbanken5
XML-VerarbeitungVier Arten der Verarbeitung von XML-Daten und ihre SprachenValidierungDTD, XML SchemaTest, ob ein Dokument einem gegebenen Typ entsprichtNavigationAuswahl von Positionen in einem DokumentXPathAnfragenExtraktion relevanter Daten aus DokumentenXQueryTransformationXSLTKonstruktion eines neuen Dokumentes aus einem gegebenen DokumentSchwentickLogik für XMLXML und Datenbanken6
Schematisch betrachtet.DTD/ XML Schema ja/neinXQuery SchwentickXPath XSLT Logik für XML XML und Datenbanken7
Forschungsziele für TheoretikerXML-SprachenBekannte formale ModelleGeeignete FragmenteSchwentickLogik für XMLAngepasste formale ModelleXML und Datenbanken8
InhaltXML und DatenbankenXML und Formale SprachenDTDs und reguläre AusdrückeDTDs und erweiterte kontextfreie GrammatikenSchemasprachen und reguläre BaumsprachenSonstigesFazit
DTDs und reguläre AusdrückeBeispiel: DTD !DOCTYPE Composers [ !ELEMENT Composers (Composer*) !ELEMENT Composer (Name, Vita, Piece*) !ELEMENT Vita (Born, Married*, Died?) !ELEMENT Born (When, Where) !ELEMENT Married (When, Whom) !ELEMENT Died (When, Where) !ELEMENT Piece (PTitle, PYear,Instruments, Movements) ] DTDs verwenden reguläre Ausdrücke zur Beschreibung der Folgeder Kinder eines Knoten Einschränkung zur effizienten Auswertung:It is an error if an element in the document can match”more than one occurrence of an element type in thecontent model [without looking ahead]“[XML 1.0, W3C recommendation Oktober 2000]SchwentickLogik für XMLXML und Formale Sprachen - DTDs und reguläre Ausdrücke10
Deterministische reguläre Ausdrücke It is an error if an element in the document can match”more than one occurrence of an element type in thecontent model [without looking ahead]“ bc bd erfüllt die Bedingung nicht b(c d) erfüllt sie Wie lässt sie sich definieren und effizient testen?Definition: 1-unambiguous [Brüggemann-Klein, Wood 97] Nummeriere Symbole von links nach rechts r 0 r ist 1-unambiguous , falls gilt:uxi v L(r 0 ) und uyj w L(r 0 ), xi 6 yj x 6 yBeispielr 0 b 1 c2 b 3 d 4 r bc bd b1 c2 L(r 0 ), b3 d4 L(r 0 ), b1 6 b3SchwentickLogik für XMLaber: b bXML und Formale Sprachen - DTDs und reguläre Ausdrücke11
1-unambiguous: CharakterisierungDefinition: Glushkov-Automat Sei r 0 nummerierter“ regulärer Ausdruck” Zustände von Ar0 : {0} {alle Zeichen von r 0 }b aibjfalls uai bj v L(r 0 )Beispiel r bc bd bb1bb3r 0 b 1 c2 b 3 d 4cc20d4dSatz [Brüggemann-Klein, Wood 97]Ein regulär Ausdruck r ist genau dann 1-unambiguous, wennAr0 deterministisch istSchwentickLogik für XMLXML und Formale Sprachen - DTDs und reguläre Ausdrücke12
InhaltXML und DatenbankenXML und Formale SprachenDTDs und reguläre AusdrückeDTDs und erweiterte kontextfreie GrammatikenSchemasprachen und reguläre BaumsprachenSonstigesFazit
XML-Dokumente als AbleitungsbäumeBeispiel !DOCTYPE Composers [ !ELEMENT Composers (Composer*) !ELEMENT Composer (Name, Vita, Piece*) !ELEMENT Vita (Born, Married*, Died?) !ELEMENT Born (When, Where) !ELEMENT Married (When, Whom) !ELEMENT Died (When, Where) !ELEMENT Piece (PTitle, PYear,Instruments, Movements) ] Beobachtung DTDs sind im Grunde erweiterte kontextfreie Grammatiken :– Produktionen haben reguläre Ausdrücke auf der rechten Seite– Rest wie kontextfreie Grammatiken Gültige XML-Dokumente sind dann Ableitungsbäume zu dieserGrammatikSchwentickLogik für XMLXML und Formale Sprachen - DTDs und Ableitungsbäume14
DTDs und Ableitungsbäume spiel-DTD.Logik für XMLPYearInstrumentsMovementsLa Mer1905Orch.3.als Grammatik !DOCTYPE Composers [ !ELEMENT Composers (Composer*) !ELEMENT Composer (Name, Vita, Piece*) !ELEMENT Vita (Born, Married*, Died?) !ELEMENT Born (When, Where) !ELEMENT Married (When, Whom) !ELEMENT Died (When, Where) !ELEMENT Piece (PTitle, PYear,Instruments, Movements) ] SchwentickPTitleComposers Composer Composer Name Vita Piece Vita Born Married Died?Born When WhereMarried When WhomDied When WherePiece PTitle PYear Instr Move···XML und Formale Sprachen - DTDs und Ableitungsbäume15
Validierung bezüglich osers Composer Composer Name Vita Piece Vita Born Married Died?Born When WhereMarried When WhomDied When WherePiece PTitle PYear Instr Move···SchwentickDiedLogik für XMLPTitlePYearInstrumentsMovementsLa Mer1905Orch.3BemerkungValidierung bzgl. DTD ist einfach:Für jeden Knoten teste, ob die Folgeder Kinder dem zugehörigenregulären Ausdruck entsprichtXML und Formale Sprachen - DTDs und Ableitungsbäume16
InhaltXML und DatenbankenXML und Formale SprachenDTDs und reguläre AusdrückeDTDs und erweiterte kontextfreie GrammatikenSchemasprachen und reguläre BaumsprachenSonstigesFazit
Ausdrucksschwäche von DTDsBemerkung DTDs haben nur eine sehr eingeschränkte Ausdrucksfähigkeit: Elemente mit dem selben Namen können nicht in verschiedenenZusammenhängen auftreten Zuordnung von Elementen zu Typen wäre wünschenswert DTDs mit Typen(Abstraktion von XML-Schema)Ein klassisches Beispiel !DOCTYPE Dealer [ !ELEMENT Dealer (UsedCars NewCars) !ELEMENT UsedCars (ad*) !ELEMENT NewCars (ad*) !ELEMENT ad ((model, year) model) ] ogik für XMLyearXML und Formale Sprachen - Reguläre Baumsprachenmodel18
DTDs mit TypenDefinition: DTD mit Typen Σ: Elementnamen Σ0 : Typen für Elemente µ : Σ0 Σ: Zuordnung von Typen zu Elementnamen d: (einfache) DTD über TypenBeispielDealer UsedCars NewCarsUsedCars adUsed NewCars adNew adUsed model yearadNew modelµ(Dealer) Dealerµ(UsedCars) UsedCarsµ(NewCars) NewCarsµ(adUsed) adµ(adNew) adDefinitionEin Baum erfüllt eine DTD mit Typen, wenn es einekonsistente Zuordnung seiner Knoten zu Typen gibtSchwentickLogik für XMLXML und Formale Sprachen - Reguläre Baumsprachen19
rAudi TTMazda 3231988BemerkungDTDs mit Typen lassen sich als Baumautomaten auffassenSchwentickLogik für XMLXML und Formale Sprachen - Reguläre Baumsprachen20
Von Strings zu BäumenEin StringabcabString als BaumaBinärer Baumabcaaceeaba···acca a ee cbXML und Bäume XML-Bäume haben unbeschränkten Knotengrad Baumautomaten wurden zuerst für binäre Bäume betrachtet Die meisten wichtigen Ideen wurden dabei schon entwickelteLogik für XMLcaebeecbSchwentickebcUnbeschränkter BaumaeceaXML und Formale Sprachen - Reguläre Baumsprachena21
Von String-Automaten zu Baum-AutomatenFrage: Wie lassen sich Automaten auf Bäumen eLogik für XMLccceaeaaeccXML und Formale Sprachen - Reguläre Baumsprachen22
Bottom-Up AutomatenBeispiel: Auswertung baumartiger Schaltkreise q1 q1 q1 q00q01 q1q11q10 q1q00q01 q1q11q11q1TransitionenIdee Zwei Zustände: q0 , q1 Akzeptierend an derWurzel: q1SchwentickLogik für XMLδ( , q1 ) {(q1 , q1 )}δ( , q0 ) {(q0 , q1 ), (q1 , q0 ), (q0 , q0 )}δ( , q1 ) {(q0 , q1 ), (q1 , q0 ), (q1 , q1 )}δ( , q0 ) {(q0 , q0 )}δ(0, q0 ) {²}; δ(0, q 1 ) δ(1, q1 ) {²}; δ(1, q 0 ) XML und Formale Sprachen - Reguläre Baumsprachen23
Top-Down AutomatenBeispiel q1 q1 q0 q1 q1 q1 q10 q0 1 q1 1 q1 0 q0 0 q0 1 q1 1 q1 1 q1accaccaccaccaccaccaccacc SchwentickIdeeRate richtige Werte vonWurzel ausTeste an den BlätternZustände: q0 , q1 , accStartzustand q1 an derWurzelAkzeptieren, wenn alleBlätter acc annehmenLogik für XMLTransitionenδ( , q1 ) {(q1 , q1 )}δ( , q0 ) {(q0 , q1 ), (q1 , q0 ), (q0 , q0 )}δ( , q1 ) {(q0 , q1 ), (q1 , q0 ), (q1 , q1 )}δ( , q0 ) {(q0 , q0 )}δ(0, q0 ) {acc}; δ(0, q1 ) δ(1, q1 ) {acc}; δ(1, q0 ) XML und Formale Sprachen - Reguläre Baumsprachen24
Reguläre BaumsprachenSatzFür eine Baumsprache L sind äquivalent:(a) L wird von einem nichtdeterministischen Bottom-upAutomaten akzeptiert(b) L wird von einem deterministischen Bottom-up Automatenakzeptiert(c) L wird von einem nichtdeterministischen Top-downAutomaten akzeptiert Reguläre BaumsprachenBeweisidee(a) (b): Potenzmengen-Konstruktion(a) (c): Die gleiche Sache - aus zwei Richtungen betrachtetBemerkungEs gibt viele weitere äquivalente BeschreibungenSchwentickLogik für XMLXML und Formale Sprachen - Reguläre Baumsprachen25
Von binären zu unbeschränkten BaumautomatenBinäre Baumautomatenq σTransitionen durch endlichen Menge gegeben:δ(σ, q) {(q1 , q2 ), (q3 , q4 ), . . .}σ1σ2q1q2Unbeschränkte Baumautomatenq σσ1σ2σnq1q2qn δ(σ, q)?δ(σ, q) Bei unbeschränkten Baumautomaten ist δ(σ, q) eine reguläre Sprache δ(σ, q) kann z.B. durch einen regulären Ausdruck spezifiziert werden[Brüggemann-Klein, Murata, Wood 2001]SchwentickLogik für XMLXML und Formale Sprachen - Reguläre Baumsprachen26
XML-Schema und Reguläre Baumsprachen XML-Schemasprachen lassen sich als eingeschränktereguläre Baumsprachen auffassen [Murata, Lee, Mani 2000] Effiziente Validierung ebenfalls für eingeschränkte Klassenmöglich(umfasst Kern von XML-Schema) Erweiterung: Reguläre Anfragen Reguläre Baumsprachen bilden einen soliden Hintergrundfür das Studium von XML-SchemasprachenSchwentickLogik für XMLXML und Formale Sprachen - Reguläre Baumsprachen27
InhaltXML und DatenbankenXML und Formale SprachenDTDs und reguläre AusdrückeDTDs und erweiterte kontextfreie GrammatikenSchemasprachen und reguläre BaumsprachenSonstigesFazit
Weitere ZusammenhängeÜbersichtXPath Vertikale Navigation://Vita/Died/* Σ · Vita · Died · Σ Auch Navigation längs anderer Achsen : parent,descendant, following-sibling,. Verallgemeinung regulärer Ausdrücke für Bäume:Caterpillars– Navigation & Tests– down · first · right · right · a · up:Gehe zu Knoten, dessen drittes Kind Label a hat XPath-Auswertung: Polynomielle Zeit mit dynamischerProgrammierung [Gottlob, Koch, Pichler 03]XSLT Enge Korrespondenz zu Treewalk-Automaten mit PebblesXQuery .noch viel zu tunSchwentickLogik für XMLXML und Formale Sprachen - Sonstiges29
InhaltXML und DatenbankenXML und Formale SprachenFazit
Fazit Formale Sprachen spielen für die Grundlagen vonXML-Srachen eine wichtige Rolle Viele formalsprachliche Konzepte lassen sich also imRahmen eines aktuellen Anwendungsbereiches motivieren Geeignet für die Schule?SchwentickLogik für XMLXML und Formale Sprachen - Sonstiges31
Literatur Anne Brüggemann-Klein, Derick Wood. One-Unambiguous Regular Languages.Inf. Comput. 142(2): 182-206 (1998) Murata, Lee, Main. Taxonomy of XML Schema Languages using FormalLanguage Theory. Technischer Bericht, 2000 Geert Jan Bex, Wim Martens, Frank Neven, Thomas Schwentick.Expressiveness of XSDs: from Practice to Theory, There and Back Again.International World Wide Web Conference, WWW 2005 Anne Brüggemann-Klein, Derick Wood. Caterpillars: A Context SpecificationTechnique. Markup Languages 2(1): 81-106 (2000) Frank Neven. Automata, Logic, and XML. CSL 2002: 2-26 Georg Gottlob, Christoph Koch, Reinhard Pichler. XPath Processing in aNutshell. SIGMOD Record 32(1 2) (2003) Nils Klarlund, Thomas Schwentick and Dan Suciu. XML: Model, Schemas,Types, Logics, and Queries. In Logics for Emerging Applications of Databases2003, Springer, 1-41, 2003 www.w3.org Harald Schöning. XML und Datenbanken : Konzepte und Systeme. Hanser,2003SchwentickLogik für XMLXML und Formale Sprachen - Sonstiges32
Ankündigung: Tag der Informatik“” Mittwoch, 27.4.05, nachmittags Informationen für Schüler und Studenten desGrundstudiums über– Studium und Lehre der Informatik in Marburg– Forschungsschwerpunkte (Doktoranden berichten)– Berufsfelder (Ehemalige berichten) Vorläufige hwentickLogik für XMLXML und Formale Sprachen - Sonstiges33
Waggonhalle: RotkehlchenRudolfBultmannStraßeSchwentickLogik für XMLXML und Formale Sprachen - Sonstiges34
String als Baum a b c a b Bin arer Baum a b c a b a b a b c c Unbeschr ankter Baum a e c e a e c a a e e c a e a e c e c e e a e XML und B aume † XML-B aume haben unbeschr ankten Knotengrad † Baumautomaten wurden zuerst f ur bin are B aume betrachtet † Die meisten wichtigen Ideen wurden dabei schon entwickelt
w'fmd'i' W'fm & úNd.h 2019 iy bka miqj meje;afjk úNd. i yd m%Yak m;% jHQyh yd uQ,dlD;s m%Yak-ii-, % ! % 4 2019!. # %!'" % " "# 4 !/. % # % " . . * - ii - LVK X .
- 1 - iiiiiiiiiiiiiiiii2018ishiÆ uysñliyïlïwuel iú 'QQwi,H Qiskh iyq.u iywqil%Nhdih iúNf acwriyq.u imis ú %iew wK ïiw auvWi,H Qdi I fldgi idudkH f;dr; re ;dlaIK (GIT) úNd.h 1. úNd.h yd iïnkaO fmd f;dr; re 1.1 ye skaùu YS% ,dxlsh mdi,a orejkaf.a m .Kl idCIr;dj jeä †hqKq ls fï mshjrla jYfhka
Uses of XML XML data comes from many sources on the web: web servers store data as XML files databasessometimes return query results as XML webservices use XML to communicate XML is the de facto universal format for exchange of data XML languages are used for music, math, vector graphics popular use: RSS for news feeds & podcasts CSC443: Web Programming
The design goals for XML are: 1. XML shall be straightforwardly usable over the Internet. 2. XML shall support a wide variety of applications. 3. XML shall be compatible with SGML. 4. It shall be easy to write programs which process XML documents. 5. The number of optional features in XML is to be kept to the absolute minimum, ideally zero. 6.
The number of optional features in XML is to be kept to the absolute minimum, ideally zero XML documents should be human-legible and reasonably clear The XML design should be prepared quickly The design of XML shall be formal and concise XML documents should be easy to create Terseness in XML markup is of minimal importance
C Provide the XML services more and more customers want, or C Watch your customer base shrink You can: C Learn to work with XML smoothly and easily, or C Fight XML tooth and nail You can: C Use XML content to make some of your processes easier C Let XML be an added step, added expense, and continual nuisance You can't make XML go away! Page 2
Overview XML More about XML We will talk about algorithms and programming techniques to efficiently manipulate XML data: I Regular expressions can be used to validate XML data, I finite state machines lie at the heart of highly efficient XPath implementations, I tree traversals may be used to preprocess XML trees in order to support XPath evaluation, to store XML trees in databases, etc.
Tom Sawyer’s observations of his environment and the people he encounters. In addition, students will make their own observations about key aspects of the novel, and use the novel and the journal writing activity to make observations about their own world and the people they are surrounded by. This unit plan will allow students to examine areas of Missouri, both in Hannibal, and in their own .
