# ML Wiki

## Typical Queries

### Point Query

Find all values for the (multi-dimensional) search key

• for product "TV" sold in Ireland with ALL for date
• does there exist a star on coordinate (10, 3, 5)

### Partial Match Queries

Not all values of a search key are specified

• return the coordinates pf all stars with $x=5$ and $z=3$

### Range Queries (Dicing)

• return all cube cells with date $\geqslant Q_1$ and date $\leqslant Q_2$ and sales $\leqslant 100$
• return coordinates of all stars with $x \geqslant 10$ and $20 \leqslant y \leqslant 35$

### Nearest-Neighbor Queries

• return closest 3 stars to a star at (10, 15, 20)

## Can Use One-Dimensional Indexes?

One-Dimensional Indexes (such as B-Tree)

• take one single key
• can use one key made of multiple attributes

### B-Tree

Need to impose lexicographical order on keys in B-Tree to do that

### Hash Tables

For Hash-Based Indexes we need to compute Hash Function for tuples

• extend hash function: $h(x, y, z) = h_1(x) + h_2(y) + h_3(z)$

Problem

• cannot answer range queries at all
• age < 20
• sal < 30
• age < 20 and sal < 20
• all lead to linear scan