Cours DEA-III 2002(03) - Controle des  changements dans XML
22 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Cours DEA-III 2002(03) - Controle des changements dans XML

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
22 Pages
English

Description

zzzzzzzContrôle des Changements dans XMLObjectifsCours: Données semi structurées Comprendre la gestion de données DEA I3 : Information, Interaction, dynamiquesIntelligence À large échelle, cas d’un entrepôt de données Grégory Cobena du Web (Xyleme)http://www-rocq.inria.fr/verso/ À l’échelle du document XML, cas de la Gregory.Cobena@inria.fr gestion de versions20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 2Motivations: Motivations:à l’échelle du Web à l’échelle du documentDans quel cas trouve-t-on la notion de Le contrôle des changements, c’est changements?d’abord: Lorsque l’on gère différents documents, on étudie les Savoir découvrir des sources de données et changements inter-documentsdes documents XML, sur le Web ou sur un Exemple: Fichier XML décrivant deux modèles de Intranetvoitures, une Peugeot-307 et une 206 Mettre en place un suivi dans le temps de ces documents Lorsqu’on s’intéresse à l’évolution dans le temps d’un Extraire des connaissances sur ce qui document donnéchange: les documents, leurs propriétés, leur Exemple: Fichier XML décrivant un carnet d’adressescontenu20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 3 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 4Enjeux Plan du coursLes données semi structurées doivent Xylemeapporter une description plus précise Un entrepôt de données XML à large échelleque du simple texte, avec une Intégration de données du ...

Subjects

Informations

Published by
Reads 29
Language English

Exrait

z
z
z
z
z
z
z
Contrôle des Changements dans XML
Objectifs
Cours: Données semi structurées
Comprendre la gestion de données
DEA I3 : Information, Interaction, dynamiques
Intelligence
À large échelle, cas d’un entrepôt de données
Grégory Cobena du Web (Xyleme)
http://www-rocq.inria.fr/verso/ À l’échelle du document XML, cas de la
Gregory.Cobena@inria.fr gestion de versions
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 2
Motivations: Motivations:
à l’échelle du Web à l’échelle du document
Dans quel cas trouve-t-on la notion de Le contrôle des changements, c’est
changements?d’abord:
Lorsque l’on gère différents documents, on étudie les Savoir découvrir des sources de données et
changements inter-documentsdes documents XML, sur le Web ou sur un
Exemple: Fichier XML décrivant deux modèles de Intranet
voitures, une Peugeot-307 et une 206 Mettre en place un suivi dans le temps de ces
documents
Lorsqu’on s’intéresse à l’évolution dans le temps d’un Extraire des connaissances sur ce qui
document donné
change: les documents, leurs propriétés, leur
Exemple: Fichier XML décrivant un carnet d’adressescontenu
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 3 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 4
Enjeux Plan du cours
Les données semi structurées doivent Xyleme
apporter une description plus précise Un entrepôt de données XML à large
échelleque du simple texte, avec une
Intégration de données du Websémantique bien définie
Surveillance active des données du WebLa gestion des changements dans les
XML Diffdonnées semi structurées est encore
Représentation des changementsplus complexe que dans les BD
Détection des changementsrelationnelles.
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 5 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 6z
z
z
z
z
z
z
z
z
z
Organization
Première Partie: Xyleme 1. The Web and XML
2. Xyleme
3. Data Acquisition and Maintenance
4. XML Repository, Semantic Data
A Dynamic Warehouse for Integration and Query Processing
the XML data of the Web 5. Query Subscription
Conclusion
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 8
The Web today(Part I: Xyleme)
Terabytes of data1. The Web and XML
A lot of public pages
1 billion in [06/2000]
several millions of servers
Private web: not publicly available pages
Deep web: data hidden behind forms
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 10
HTML = Hypertext Language XML = Semistructured Data
<product-table>Ref Name Price
< product reference=”X23">The <b> X23 </b> new camera X23 Camera 359.99
<designation> camera </designation>Ref Name Price replaces the <b> X22 </b>. It R2D2 Robot 19350.00
<price unit=Dollars> 359.99 </price>X23 Camera 359.99 comes equipped with a flash Z25 PC 1299.99 <description> … </description>easyR2D2 Robot 19350.00 (worth by itself <i>53.99 $</i>) ... </product>
Z25 PC 1299.99 < product reference=”R2D2">hard and provides great quality for Information System
<designation> Robot </designation>only <i>359.99 $</i>.
<price unit=Dollars> 19350 </price>
Data + StructureInformation System <description> … </description>
...Semistructured: Text + presentation HTML </product-table>
more flexible
Where is the data ?
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 11 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 12z
z
z
z
z
z
z
z
z
z
z
z
XML : Tree Types (Part I: Xyleme)
2. A Dynamic Warehouse for product-table
the XML Data of the Web
product reference
pricedesignation description
Semantics and structure are in paths
product-table/product/reference
product-table/product/price
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 13
Xyleme Research Xyleme Company
Started September 2000Project Xyleme at INRIA (1999-2000) :
(25 employees end of 2001)Explore XML + Web + SGBD to make the Web a Knowledge Database
INRIA Market Challenges: Sophie Cluet: Databases (OQL…)
Few XML documents available on the Web (because Serge Abiteboul: semi-structured data + web
of weak software support) Guy Ferran: ex O Technology2
Company is focusing on private XML:Mannheim University
Guido Moerkotte Press, Editors, Financial Data, Biology…
Université d’Orsay Technology:
Marie Christine Rousset Scalability for large amount of data
CNAM Internet (+focus) / Intranet support
Dan Vodislav Monitoring and Version Management
Heterogeneous Data Integration
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 15 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 16
Architecture Functional Architecture
User Interface
Cluster of PCs
-------------------- I N T E R N E T -----------------------
Developed with Linux and C++
Web Interface Xyleme Interface
Communications
Change Control Semantic Module
local: Corba Acquisition Loader
& Crawler external: HTTP Query Processor
Distribution between autonomous
machines
Repository and Index Manager
Now Web Services
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 17 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 18z
z
z
z
z
z
z
z
z
z
z
z
(Part I: Xyleme)Architecture
3. Data Acquisition and
-------------------- I N T E R N E T ----------------------- Maintenance,
Change Control and Change Control and
Acquisition and Acquisition andSemantic Semantic
Maintenance Maintenance Page ImportanceIntegration Integration
E
T
Index Index IndexH
E
R
N
Loader |Query Loader |QueryE
T
Repository Repository Repositorry Repository
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 19
Goals Life Cycle of a page in Xyleme
Discover XML pages on the web that are The URL of D is discovered as a link in
of interest for customers another page (or published by a customer)
For this crawl the web (HTML+XML) The page scheduler decides to read D
Maintain them up to date The meta data of D is read
type, last_date_update...Do this under bounded resources:
The document D is loaded Memory for known URLs
Bandwidth The document D is re(read) regularly
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 21 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 22
Main Issues Page Importance
Loading of pages Definition: Important pages are linked to
we can load up to 5 millions of pages/day on by important pages
a standard PC Offline algorithm (used by Google)
main cost is Internet connection
Our Online algorithm
Metadata management (access to disk)
(M. Preda, S. Abiteboul, G. Cobena)
Page scheduling does not require to maintain graph information
decide which page to read or refresh next faster convergence with focused crawling
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 23 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 24z
z
z
z
z
z
z
z
z
z
(Part I: Xyleme) Querying Language
4. XML Repository:
Today: A mix of OQL and XQLSemantic Data Integration
We are currently moving to X-Query and Query Processing
(which is also a mix of OQL and XQL…)
Select boss/Name, boss/Phone
From comp in BusinessDomain,
boss in comp//Manager
Where comp/Product contains “Xyleme”
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 26
Web Heterogeneity Indexing
Semantic domains, e.g., cinema Standard inverted index
Many possible types for data in this domain, word → documents that contain this word
many DTDs Xyleme index
Semantic Integration word → elements that contain this word
document + element identifier one abstract DTD for the domain
gives the illusion that the system maintains an Goal: more work can be performed without
homogeneous database for this domain accessing data
1 domain = 1 abstract DTD
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 27 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 28
I.4.1 Xyleme:
Semantic Data Integration Data Integration
One application domain -- Several schemas
heterogeneous vocabulary and structure
Xyleme Semantic Integration
gives the illusion that the system maintains an
homogeneous database for each domain
abstracts a set of DTDs into an abstract DTD = a
hierarchy of pertinent terms for a particular domain
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 29 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 30z
z
z
I.4.2 Xyleme:
Technology in short Query Processing
Cluster DTDs into application domains
Business, culture, tourism, biology, …
For an application domain – semi-automatically
Organize tags into a hierarchy of concepts using
thesauri such as Wordnet and other linguistic tool
This provides the abstract DTD for the particular
domain
Generate mappings between concrete DTDs and the
abstract one
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 31 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 32
Xyleme Query Language Principle of Querying
query on abstract DTD Union of concrete queriesA mix of OQL and XQL, will use the W3C
(possibly with joins)standard when there will be one
Select product/name, product/price
catalogue/product/price ⇒ d1//camera/price
From doc in catalogue,
⇒ d2/product/cost
product in doc/product
catalogue/product/description
Where product//components contains “flash” ⇒ d1//camera/description
and product/description contains “camera” ⇒ d2/product/info, ref
⇒ d2/description
MAPPINGS between concrete
and abstract DTD’s
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 33 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 34
Query Processing Query processing
1. Partial translation, from abstract to concrete, to
Essential use of a smart index combining identify “machines” with relevant data
full-text and structure
2. Algebraic rewriting, linear search strategy based
on simple heuristics: in priority, use in memory
indexes and minimize communication
3. Decomposition into local physical subplans and
installation
4. Execution of plans
5. If needed, Relaxation
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 35 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 36z
z
z
z
z
I.4.2 Xyleme:
Repository Storage System: Xyleme Store
Efficient storage of trees in variable
length records within fixed length pages
Balancing of tree branches in case of
overflow
minimize the number of I/O for direct access
and scanning
good compromise : compaction / access time
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 37 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 38
Tree Balancing in Xyleme Store Questions ?
Record 1
Overflow: Overflow:
Sub-tree in other page more children in other page
Record 2 Record 3 Record 4
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 39 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 40
The Web changes all the time(Part I: Xyleme)
5. Change Control
Data acquisition + maintenance
keep the warehouse up-to-date
Version management
representation and storage of change
(see part II)
Change monitoring
query subscription
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 42z
z
z
z
z
z
z
z
z
z
z
z
Subscription Language Example
subscription myPaintings
SQL-like language based on ‘atomic events’.
% what are the new painting entries in Musee d’Orsay site
Combines the use of monitoring queries and monitoring newPainting
continuous queries. select URL
Atomic The language can be extended by adding new where URL extends www.musee-orsay.fr/*
events
types of atomic events. and <painter> contains “Monet”
% manage the changes in the expositions Uses the XML Query Language for continuous
continuous delta Expositionqueries. “Querying the XML Documents of the
select ... from ... where Web”, V. Aguilera, S. Cluet, F. Boiscuvier,
when monthlyTech. Report
notify daily % send me a daily report
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 43 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 44
Step 1: Atomic Event Detection Alerters
5 millions of pages/day
Each Alerter can be viewed as a plug-in that acts on
d a document flow.atomic event 46: URL matches
All sorts of Atomic events can be detected: URL pattern www.musee-orsay.fr/*
metadata pattern detection, Keywords, XPath expressions, atomic event 67: XML document
manager Page rank…contains the tag <painter> with
Can be distributed.the value “Monet”
document & alerts Some advanced alerts are:
d/46 Long string look-ups
Finding XML Patterns (e.g. XPath)
Comparing digital signature of text documents (copy
XML complex tracker)
loader event detectiond/46,67
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 45 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 46
URL Patterns Detection (1) URL Patterns Detection (2)
Using a tree: navigate on the tree until a leave is Supported patterns
encountered URL | prefix* | *suffix
Example: Tree is,
Using Hash Table: try all possible patterns
Test in O(1), total test time is O(n), where n is the <root str=“www.inria.fr/”>
length of URLs <node str=“/verso” alert=“1”>
<node str=“/index.html” alert=“2”/>
<n=“/main.html” alert=“3”/>
Example: http://www.inria.fr/verso/index.html </node>
Test: </root>
http://www.inria.fr/verso/*
Patricia Trees ?http://www.inria.fr/*
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 47 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 48z
z
z
z
z
z
z
z
z
z
z
z
z
z
Keywords Sequence Algorithm Simple XPath filtering Algorithm
Detect: « Air France » Problem:
detect <a> CONTAINS « word »Solution:
a Tree of backward keyword sequences Solution:
a context memory with O(1) update cost Reverse path expression
Use postfix orderTree is implemented over a hash table
Use a stack for ‘//’ and another stack for ‘/’
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 49 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 50
Simple XPath filter example:
Understanding the tree structure in
postfix order Simple XPath: Example
Consider tree: <a> CONTAINS toto is detected by:
<A><B><C>toto</C><C/></B></A> « toto »::ancestor <a>
Nodes come as:
When « toto » is detected, it is stored
toto (id=1, level=4)
For each ancestor of « toto », the name
C (id=2, level=3)
is compared to <a>.
C (id=3, level=3)
All tests are executed using an hash
B (id=4, level=2)
table
A (id=5, level=1)
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 51 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 52
Step 2: Complex Event Detection
Stemming
On the Alerter Millions of alerts of pages/day
Exemple: Éléphant –> ELEPHANT Millions of subscriptions
HTML Do it for 500 documents / second
parser complex Noise may be introduced
event detection
(Example: tâche = tache)
On the Subscription Manager
To avoid duplicate registration of similar events complex event 12: 67 & 46
XML (XML document contains the tag To show the user how his query is stemmed
loader <painter> with value “Monet”
Real stemmers: chevaux -> cheval and URL matches pattern
www.musee-orsay.fr/*)
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 53 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 54z
z
z
z
z
z
z
z
z
Complex Events Algorithm Step 3: Notification Processor
The formal problem is NP-hard
We proposed several possible
alerts notification/monitoringalgorithms complex
Experimental (simulation) Reporter
event detectionvalues proved the effectiveness
of our solutions
The Hash-Tree based algorithm Millions of triggers
is well suited for our application:
Notifications/day 10 million Complex Events
clock continuous 1 million Atomic Events
100 Atomic events queries notification/resultsdetected per document
0.8 ms to process a document.
~2 million documents per
day (on each PC).
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 55 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 56
Architecture Monitoring Applications
Xyleme
documents Query
Processor
Trigger
Engine
Complex
Xyleme Xyleme
Event Reporter
Alerter Reporter
Detection
Subscription
Manager
SQL
Xyleme
Subscription Web Browser
Manager
SQL
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 57 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 58
Copy tracking Web portal management
Example: a press agency wants to check that people are not Standard portal management
publishing illegally copies of their wires
Unreachable pages
Need to react fast on changes: illegal copy of the wire may last
Dangling pointersonly a couple of days
Incorrect pages (e.g., do not parse)
Detection of interesting pages on the web
Query to search engine
Etc.1 Or specific crawl + pre-filter23
detection Portal archiving
Filter
Subscription and notification
Flow of candidate
Slice the documents
document
20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 59 20/12/2002 DEA I3 - Données semi-structurées - Grégory Cobéna 60