Note: SQL

###Schema

• Snowflake
• Star

###Relation algebra

• Selection
• Projection

• Cartesian Product

  Join: they are all just syntactic sugar

  • natural join
  • left outer join
  • right outer join
  • full outer join
  • left semi join
  • right semi join
• Rename
• Union
• Minus

###Some gotcha - The use of GROUP BY

followed by```having``` - duplicate vs. redundant

###Refs

• Xquery
• Codd’s theorom

###Feb 4 Class

• SQL does a hell lot of join optimization: simply because join is the most common operation in SQL query

• sub-query:

  • correlated
  • uncorrelated

  normally uncorrelated has a better performance because correlated means do a sub-query for each different value.

• Don’t think SQL execution in terms of algorithm sense: because the execution time really depends on the optimization the database does. There may be different indexes for optimization.
• SQL tries to get around NULL because normally nobody expects it to throw out some errors. But it brings the consequence that operations involving NULL can have unexpected result.
• However, for programming languages, they care more about correctness, so basically it will throw exceptions or errors.
• Eg: in WHERE, only output rows whose outcome is TRUE, but reject UNKNOWN/FALSE

Note: Multithreaded Programming

####Creating POSIX Threads

pthread_create

• returns a positive value indicating failure

####Structure pointer approach

P46

####Passing arguments to threads

1. copy all arguments to the thread’s stack: isn’t supported in either POSIX or Win-32
2. pass a pointer to local storage: should make sure this storage doesn’t go out of scope until the thread is finished with it
3. pass a pointer to static or global storage: works only if one thread at a time is using the storage
4. pass a pointer to dynamically allocated storage: works only if we can free the storage exactly when the thread is finished with it

####Threads terminate

• 2 ways:
  1. return from its first procedure(a value of type void*)
  2. call pthread_exit, supplying a void* argument
• difference:
  1. pthread_exit: terminates just the calling thread
  2. exit: terminates the entire process, including other threads in the process

####Deadlock conditions

1. a thread can hold an item while waiting for another
2. a thread cannot be forced toyield the items it is holding
3. each container has a finite capacity
4. a circular wait

####Semaphore

• binary semaphores
• counting semaphres

####Conditional variables

• P67: why not if --writers == 0
• P70: Now when the waiting threads wake up, they will find the guard false….

####async-signal

• fork
• _exit
• open
• close
• read
• write
• sem_post

####Question

• POSIX cancellation

####Bear in mind

1. it’s unsafe to make more than 1 call to pthread_join on any particular thread
2. for each call to pthread_create there should be exactly one call to either pthread_join or pthread_detach.
3. pthread_cleanup_push must match exactly with pthread_cleanup_pop

####Notes during db assignment

• It’s a common(if standard) approach to mask the signal you want to handle in the main thread, then create a handler thread, specifically unblocking the signal and waiting for the signal, to handle that signal.
• If you did not pthread_detach the thread, then you’ll have to pthread_join the thread, or the resources allocated by the thread will not be collected.
• Signal is not that hard at all, just need to figure out the current state.
• If you cherish your life, stay away from pthread_detach!!!

Note: A Whirlwind Tour

###lone

• multiplicity

• Name -> lone Addr
  

• each name is mapped to at most one address

###Signature facts

• facts that apply to every member of a signature

###?lookup? {n.^(b.addr) & Addr}

###?Why I have different result with the book?

pay attention to the address mapping change in the Book definition

###Some lessons

• start from a simple model, add more constraints as needed

Note: Introduction

####Traps

• Invoking the kernel from user code
• Done by system calls
• Handled as part of the program that caused it

####Interrupts

• A request from an external device for a response from the processor.
• Handled independently of any user program

####Address space

• Stack
• going down
• going up
• Dynamic
• BSS(block started by symbol)
• Data
• Text

####Process Management

• fork()
• wait(&ReturnCode)
• exit(n)
• 1. process calls exit- zombie state(PID and return value preserved)
  2. parent process calls wait- released(all traces disappear)
• parent terminates before the child PID 1 inherits the children of terminated processes

####Exec(s)

• creates a new process to replace the program with a new one
• execl(name of file, name of program, command-line arguments terminating with 0)
• What if the size doesn’t match up? The new process image will have different address spaces for text, data, BSS, Dynamic and Stack according to the new process.

####File Descriptors

• How many file descriptor table? Each process have different file descriptor table residing in the shell

• Both file descriptors refer to the same context info

    close(1);
    close(2);
    dup(1);
  

####Pipe

int p[2];
pipe(p);
// p[0] for read
// p[1] for write

####Links

• Hard link: link system call or ln
• Symbol link: symlink system call or ln -s

####execve

execve(const char *path, char *const argv[], char*const envp[]);

• path is the path to the program
• argv
  • The first element in argv is the name of the executed program(eg: last component of path, or whatever)
  • The rest elements in args are argumentlist, terminated by NULL
• envp
  • Environment pointer, null-terminated
  • see environ(7)

####Bear in mind: some realations

• Every time you malloc, you have to free
• Every time you open, think about close

Cryptography 1

##Week 1

###One Time Pad

Never use stream cipher key more than once!

• Network traffic: negotiate new key for every session
• Disk encryption: typically do not use a stream cipher