• Assignment 2

❖ Assignment 2

Aim: implement variants of signature-based indexing   (SIMC, CATC)

Implement individual relations and commands to work on them.

Each relation R consists of multiple files:

• R.info ... relation meta-data (e.g. # tuples)
• R.data ... data file containing pages of tuples
• R.tsig ... file containing tuple signatures
• R.psig ... file containing page-level signatures
• R.bsig ... file containing bit-sliced signatures

Each relation implements one signature style  (SIMC or CATC)

❖ Assignment 2 (cont)

File structures for signature info + data files

Tuples are all tupSize bytes long (based on # attributes)

Signatures are m  bits long, rounded to ceil(m/8)  bytes

❖ Assignment 2 (cont)

Superimposed codewords (SIMC):

• signature has m  bits, ~m/2  bits set to 1
• codewords have m  bits, each has k  bits set to 1
• codewords combined via OR
• false matches caused by hash collisions and superimposition

Concatenated codewords (CATC):

• signature has m bits, ~m/2 bits set to 1
• codewords have u_i ≅ m/n  bits, each has u/2  bits set to 1
• codewords combined via shift + OR
• false matches caused by hash collisions  (worse than SIMC)

❖ Assignment 2 (cont)

More detailed file structures for data + signature files

❖ Assignment 2 (cont)

❖ Assignment 2 (cont)

We supply:

• complete command programs to build and query relations
• partially-complete ADTs for operations needed by commands

You complete the ADTs so that the commands work properly

• create, insert, select ... build/query commands
• gendata, stats, dump ... utility commands
• x1, x2, x3 ... commands for debugging ADTs

❖ Assignment 2 (cont)

./create RelName SigType #tuples #attrs 1/pF

• creates a new relation with prefix  RelName
• uses n = #attrs to determine tuple size
• uses r = #tuples to determine bs ⇒ length of bit-slices
  (#tuples suggests maximum number of tuples to be stored)
• uses pF and n  to determine m  and k  for SIMC signatures
• uses pF and n  to determine m  and u_i  for CATC signatures
• creates files RelName.info, RelName.data, etc. etc.
• as supplied, data and signature files are empty after create
• when complete, RelName.bsig should contain all-zero bit-slices

❖ Assignment 2 (cont)

./gendata #tuples #attributes [startID] [seed]

• generates #tuples tuples in a standard format, e.g.

  1234567,iuwhfkajewhkfjkwefbx,a3-101,a4-256,a5-013,...
  

• first attribute is unique id
• second attribute is 20-char random string (most likely unique)
• rest are aN-DDD up to #attributes
• attributes a3-DDD to aN-DDD are not unique
• if no startID given, use 1000000;   if no seed given, use 0

❖ Assignment 2 (cont)

./insert [-v] RelName

• insert tuples read from stdin into Relname
• updates all files: info, data, signature files
• tuples look like those generated from gendata
• typical usage

  ./gendata #tuples #attrs | ./insert RelName
  

• -v displays each tuple and PID of page where inserted

❖ Assignment 2 (cont)

./select RelName 'Query'

• finds all matches for pmr query in relation RelName
• queries are expressed using ? for unknown attributes, e.g.

  ?,?,?,?,?         # matches all tuples
  1234567,?,?,?,?   # matches single tuple with this ID
  ?,?,a3-101,?,?    # matches tuples with a3-101 as 3rd attr
  ?,?,a3-101,a4-200,a5-013
  

• should enclose Query in single quotes   (to avoid problems with zsh)
• prints one tuple per line   (note: order of tuples is not important)
• prints page read statistics at end of output

❖ Assignment 2 (cont)

ADTs that you need to complete

• Bits ... operations on bit-strings  (set,unset,and,or,shift)
• Reln ... operations on relations  (new,open,close)
• Query ... operations on queries  (start,scan,stats,close)
• Tsig ... operations on tuple signatures  (makeSig,find)
• Psig ... operations on page signatures  (makeSig,find)
• Bsig ... operations on bit-slices  (find)

You should not change any of the commands  (e.g. select.c)

❖ Assignment 2 (cont)

What to do now?

• review the notes on signature-based indexing
• read the spec carefully
• read the code for the commands   (to see how they use the ADTs)
• read the ADT *.h files;   read the ADT *.c files
• write and test your code   (suggest: tsig, then psig, then bsig)

Testing script available next week.

Don't wait. It's easy to devise your own tests.