Rationale as a Query Language: from Frege to XML

Slide1 l.jpg
1 / 31
0
0
1095 days ago, 331 views
PowerPoint PPT Presentation

Presentation Transcript

Slide 1

Rationale as a Query Language: from Frege to XML Victor Vianu U.C. San Diego

Slide 2

Logic and Databases: an example of overcoming adversity • FO lies at the center of present day database frameworks • Relational question dialects depend on FO: SQL, QBE • More capable inquiry dialects (the distance to XML) depend on expansions of FO • Foundations lie in established rationale FO : Frege social variable based math : Tarski

Slide 3

Why is FO so fruitful as a question dialect? • simple to utilize syntactic variations SQL, QBE • productive usage through social polynomial math managable to examination and improvement • potential for impeccable scaling to extensive databases quick reaction can be accomplished utilizing parallel handling

Slide 4

A social database: consumer bar brew frequents serves Joe's King's Bass Joe Molly's King's Bud Sue's Molly's Bass … ... … • legitimately a limited first-arrange structure

Slide 5

Find the consumers who visit some bar serving Bass FO:  d :consumer |  b :bar (frequents( d,b )  serves( b, Bass ))  QBE: bar lager consumer bar frequents serves d b Bass consumer answer d

Slide 6

not Find the consumers who visit some bar serving Bass FO:  d :consumer |  b :bar (frequents( d,b )  serves( b, Bass ))  ¬ QBE: bar brew consumer bar frequents serves d b Bass ¬ consumer answer d

Slide 7

• Naïve execution : settled circles  d :consumer |  b :bar (frequents( d,b )  serves( b, Bass ))  for every consumer for every bar check the example Number of checks: |drinkers|  |bars| Roughly n : unsuitable for extensive databases! 2 • Better approach : social polynomial math

Slide 8

Relational variable based math operations • union, contrast bar lager King's Bass Molly's Bass • choice  (serves) = … brew = Bass bar King's • projection  (serves) = bar Molly's …

Slide 9

• join |  | frequents |  | serves consumer bar brew frequents serves Joe's King's Bass Joe Molly's King's Bud Sue's Molly's Bass … ... … consumer bar brew frequents |  | serves King's Bass Joe King's Bass Molly's Bass Joe King's Bud … Joe Molly's Bass Sue Molly's Bass …

Slide 10

Relational polynomial math questions Find the consumers who visit some bar serving Bass  (  ( frequents |  | serves )) consumer lager = Bass consumer bar lager consumer bar brew consumer Joe King's Bass King's Bass King's Bass Joe Sue … .. Joe King's Bass Molly's Bass Molly's Bass Joe King's Bud … Joe Molly's Bass Joe Molly's Bass Sue Molly's Bass Sue Molly's Bass … Theorem: Relational variable based math and FO are proportionate

Slide 11

Journey of a Query FO (SQL) z(P(xz)  Q(zy))  … Relational Algebra  13 (P Q)  … Query Rewriting  14 (P S)  Q  R Query Execution Plan Execution Physical Level   14 Q R  P S

Slide 12

• modifying rules for polynomial math inquiries  (  ( frequents |  | serves )) consumer brew = Bass • productive calculations for individual operations Indexes: unique "catalogs" to information cost: generally n ( log n) much superior to n for huge databases! 2

Slide 13

• revising rules for variable based math inquiries  (  ( frequents |  | serves )) consumer brew = Bass  [ frequents |  |  (  ( serves ))] consumer bar lager = Bass • proficient calculations for individual operations Indexes: exceptional "catalogs" to information cost: generally n ( log n) much superior to n for expansive databases! 2

Slide 14

Most dynamite: hypothetical potential for immaculate scaling! • consummate scaling: given adequate assets, execution does not corrupt as the database gets to be bigger • key: parallel handling • cost: number of processors polynomial in the span of the database • part of variable based math: operations highlight parallelism

Slide 15

Each polynomial math operation can on a fundamental level be actualized effectively in parallel Example: projection  (serves) bar brew bar serves King's Bass' King's Bud's Molly's Bass … Constant parallel time!

Slide 16

Another illustration: join frequents |  | serves consumer bar frequents Joe King's Joe Molly's consumer bar brew Sue Molly's … ... Ruler's Bass Joe King's Bass Joe King's Bass Molly's Bass Joe King's Bud … Joe Molly's Bass bar brew Sue Molly's Bass serves King's Bass King's Bud … Molly's Bass …

Slide 17

Every social variable based math inquiry takes consistent parallel time !  (  ( frequents |  | serves )) consumer lager = Bass  consumer  brew = Bass steady parallel time |  | frequents serves

Slide 18

Summary in this way: • Keys to the accomplishment of FO as a question dialect : - convenience - effective execution by means of social variable based math • Constant parallel unpredictability: the maximum capacity of FO as an inquiry dialect remains yet to be figured it out!

Slide 19

Beyond social databases: the Web and XML • relations supplanted by trees (XML information) • structure portrayed by outlines (e.g., DTDs) Again, rationale gives the establishments: • DTDs are proportional to tree automata (MSO on trees) • XML inquiries are basically tree transducers • Can utilize automata and rationale to comprehend semantics and expressiveness, perform static investigation

Slide 20

Most XML question dialects are expansions of SQL • usage in light of same worldview • utilizes augmentations of social polynomial math • inquiry improvement expands upon social procedures

Slide 21

XML and DTDs <dealer> <UsedCars> <ad> <model> Honda </model> <year> 96 </year> </ad> </UsedCars> <NewCars> <ad> <model> Acura </model> </ad> </NewCars> </dealer> merchant UsedCars NewCars advertisement promotion show year display Honda 96 Acura

Slide 22

Data Type Definition (DTD)  : letter set of component names, root   set of standards: e r consistent expression over  component name

Slide 23

Documents fulfilling a DTD root … . e r e 1 … . e k  r Set of trees fulfilling DTD d: T(d)

Slide 24

Example A DTD and a tree fulfilling it: root section*; area introduction, section*,conclusions; root segment introduction segment conc introduction conc introduction segment conc introduction conc introduction conc

Slide 25

Specialization merchant UsedCars NewCars advertisement promotion show year display promotion has distinctive structure in various settings

Slide 26

Specialization merchant UsedCars NewCars promotion utilized promotion new model year demonstrate promotion has diverse structure in various settings

Slide 27

• What sets of trees can be characterized? Precisely the consistent tree dialects! - trees acknowledged by tree automata - trees characterized by Monadic Second-Order Logic (MSO) • XML inquiry dialects are basically tree transducers • Consequences: can utilize automata/rationale procedures to investigate and control DTDs and XML questions

Slide 28

Example: static examination for powerful information reconciliation Integrated View Common DTD XML Source XML Source DTDs

Slide 29

Example: static investigation for strong information joining Integrated View Tree machine B Common DTD Tree transducer T XML Source XML Source Tree robot A Source DTDs

Slide 30

Example: static examination for vigorous information incorporation Integrated View Tree robot B Common DTD Tree transducer T XML Source XML Source Tree machine A Source DTDs Need to check: T(A)  B Key: T - 1 (B) quantifiable in MSO

Slide 31

Conclusion Logic has given the establishments of databases, from social databases the distance to XML FO lies at the center of social database frameworks • XML and its question dialects are established upon tree automata, tree transducers, and rationales on trees • Implementation utilizes augmentations of social variable based math and expands upon social database systems

SPONSORS