Query Processing

Region algebras

Region inventories: collections of named region sets

• region: a contiguous span of text
• named region sets (disjoint regions, overlapping regions, nested regions)

Operators

• containment and containing queries
• tree pattern matching
• regular expression matching

The Pat algebra

• example: Searching the OED

Steps in query processing

1. Convert queries to internal representation
2. Apply rewriting transformations
1. convert into a canonical form
2. eliminate redundancy
3. improve expected cost (often using information obtained from constraints)
3. Generate access plans

1. map into sequences of lower-level operations
2. augment plans with information about the physical characteristics of the database.
3. Choose the best access plan, based on the projected cost
4. Generate code for detailed query execution plan
5. Execute the detailed plan

• When two access plans are semantically equal, which is faster to execute?
• estimate sizes of sets
• choose which indexes to use
• determine caching influences
• consider input data order
• One expensive operation is evaluating path expressions:

  doc(“eb-bib.xml”)//cite and doc(“eb-bib.xml”)//cite/author

  (consider how to evaluate / and // in node-based and region-based representations)

  Observation: can rewrite path expressions to eliminate reverse axes:

  doc(“eb-bib.xml”)//cite/../author -> doc(“eb-bib.xml”)/descendant-or-self::*[cite]/author

Node-based representation

• Forward vs. reverse traversal of edges

Interval-based representation

• Join ordering
• Nested loops vs. merge join

References and related reading

Fernandez04
Olteanu02
McHugh99
Bruno02	DeHaan03	Zhang03	Young-Lai00b