We have seen how to access records from a file, but the issue is what we have seen so far, let us sequentially read records from a file, we can go to the first block of the file and then read all the blocks of the file, read all the records, which is ok if you want to read the whole relation, but for most online transaction processing workloads, transactions do not do that, they will pick up particular students record and retrieve it. So, how do you fetch a particular student's record? You could always do it by scanning the entire student relation, but that is going to be very slow. So, what we want is an index which lets us find out given key value like the roll number, where is the record or where are the records relating to this particular search key value in this particular file, the student relation for example. So, question is how do you build such indices? So, we are going to start with some concepts before we move on to the actual index structure which is most widely used which is the B plus tree. B plus tree again the lot of details given that we have very little time, I am not actually going to try to explain B plus tree algorithms, but just give an overview of the structure and give some intuition about how B plus trees work. Again people here have taught this course know all this stuff. So, what I want to do is again go over it quickly and then if there are questions you have you know anything which you found weird, let us discuss those. So, the basics there is a notion of a search key which is what you use to store data in the index and to retrieve records in the index and then index in general consists of index entries of the form search key and pointer. There are certain special indices which instead of storing the pointer will actually store the record itself the contents of the record, but the typical index only has a pointer to the record stored somewhere else. And there are two broad kinds of indices ordered and hash we are going to skip hash indices and focus on ordered. In fact, in the real world hash indices are not used that widely for disk data storage. They are used for indexing data in memory, but on disk B plus trees are pretty much universal. Some databases like Oracle do support hash indices, but Postgres supports it, but they do not encourage you to use it. They say that we have seen the performance and it does not give any benefit. Stick with B plus trees that is the general the wisdom of people who are actually implemented these things. So, now what do you do with an index? There are several metrics including the time to access a record given a search key, time to access multiple records given a search key range, time to insert a record, time to delete a record, how much space the index takes and so on. So, we are going to focus on ordered indices where the index entries are stored sorted on the search key value. Some other notation this what is called a primary index which some people confuse to mean a primary index is index on the primary key. It is not an index on the primary key. The primary index is for a sequentially ordered file. If the file is ordered the primary index is an index whose search key specifies the sequential order for the file. So, the file is sorted on student ID. An index on student ID is a primary index. An index on student name would be called a second reindex. Now, a primary index is also called a clustering index. Why clustering? Because if you have multiple records with the same search key value. Now, you do not have multiple students with the same ID, but let us say we have the takes relation which says which courses a student has taken. If that relation is sorted on the student ID, all the records for that student are going to be cluster. They are going to be consecutive on that index because all of them have the same ID value. And this is very important. If you have a registration system which needs to find out what all the courses the student has taken. If this set of records is scattered across a relation when a particular student courses have to be displayed, you have to retrieve data from many places. Now, how many courses would a student have taken? If you want to display all the courses the student has taken since they joined your institute. Typically, students take what? 6, 7 courses a semester including labs times 8 semesters say of the order of 50 different courses. If these 50 things are at 50 locations on disk, you have to do one IO. Now, how much time will this take? If we say 10 milliseconds per IO, it is half a second to retrieve the records for one student. Now, if you have online registration and 1000 students are coming in in one hour or not even an hour, 1000 students are coming in in say a few minutes and retrieving data just displaying their data. They are not even registering. They are just seeing what they have registered for half a second times 1500 seconds. That is a lot of time and this is just one thing they are doing. They are actually doing many other things all of which take time. So, it is very critical for performance when you are retrieving multiple records to have the records clustered together. This can make a huge difference in performance and how do you choose how to cluster a relation? Well, that depends on what are the queries on that relation. So, for example, the takes relation would probably be ideally should be clustered on ID. The secondary index is one where the search key is not clustered. So, if you do not cluster the takes relation on ID, then the records for the student will be scattered. So, then that is index on ID will be a secondary index. There is a notion of index sequential file and ordered sequential file which also has an index. Now, an index has these entries. A dense index has one entry for every search key value which appears in the file. So, an index on ID has one entry per ID. In this case, the student instructor relation has one record per ID. So, the index has one entry per record. However, if a file has multiple records for the same search key, you may have a dense index which, for example, has one entry for compsci, but then there are three instructors for compsci. This would be provided this file is actually sorted on department name in which case the you only need to store the pointer to the first record. The remaining ones are consecutive. If this file was sorted on instructor ID, you cannot do this. Then you have to have one entry per record here. In contrast, the sparse index file has only a few entries. And this is applicable only if the file is sorted on this search key. And the key idea is that you know, if I store a few representative values. Now, if I search for record, let's say 1, 2, 1, 2, 1, it's greater than this record, it's less than this one. So, I will follow the pointer to this record and then search sequentially till I find that record. How far away can that record be? It may be anywhere from here to this point. So, as long as I have enough entries here, I don't have to search through too much of this file to access that record. That's the key idea of a sparse index. Now, single level index, you know, okay, so this is still a single level index. But the question is, how many in a sparse index I can choose to have one entry per five records? I can have one entry per 100 records. How do I choose this? And the typical optimal solution, a good trade off, is to use whatever is the size of the blocks which the database system uses. So, what is the meaning of a block? When the database fetches data from this, it's going to fetch a whole block of data. Whether you want the rest of the data or not, it's going to fetch that whole block into the buffer. So, once the block is fetched, it's available, it's cheap enough to read what is in the block. So, it's usually a good idea to have just one entry for the block. Anyway, you're going to read the block and then it's cheap enough to scan through the block. So, this index will have one entry per data block. So, this is a sparse index. Now, what if this index itself becomes very big? You can build an index on top of this index, which is a multi-level index. So, here is a pictorial representation. These are the actual disk blocks. The file is sorted on the search key. And then you have the level zero or inner index, which has one entry per block. This itself is divided into multiple blocks. And the next index has one entry per block in this level. So, this is a multi-level index. And this is how indices were designed initially in early days of databases. I'll repeat the question. Go ahead. Okay. So, the question is what if I delete a record here, like 3234, which was actually used in this index at this level. So, what you could do is replace that by the next record here. So, that the index is consistent with this. It is also possible to not do this. So, you can actually have an index which has values which don't exist in here. And we'll actually do that in the B plus pre case. We allow that. It's simpler to not bother. But if you wish to bother, you can update. Yeah. Question is regarding this multi-level indexing. Actually, if you increase these levels, it is going to affect the efficiency. Yeah, it will be slower, right? Yes, if you increase the levels, you have to traverse through all the levels. So, how do you justify that considering that indexing? It's a question. No, it's a trade-off. If you can use larger blocks here. Right. So, you can actually, you can either use the disk block size for the database block size. Or you can use a different notion of block which is bigger and have fewer levels. So, database implementations actually play around with these things. And the block size for the index is often larger than the minimum block size. But there are some tricks in there. I don't have time to get into it. But yes, they... But there is an interesting problem actually. But you do have to live with multi-level indexes because this index can become too big. You can't store it in memory. Whereas, this outer index may be smaller. Okay. In the interest of time, let's move on. We've seen, you know, on a primary index, you can have sparse things and then you can have a multi-level index. A secondary index doesn't give you this benefit. You have to have entry per key value. If you have multiple records with the same key value, you have a couple of options. One is to have a bucket of pointers, which has a pointer to each record with that search key value. There's also another option of having multiple entries here, one per record. Now, the key thing is that this itself is a very large file and you will have a multi-level index on this file. And this file happens to be sorted. Even if it's a secondary index, this file is sorted on the search key, which allows you to build a sparse index on it and create a multi-level index. That's the conceptually how indices are built. Now, if you come back to this picture, you see here, turn it around mentally, turn, rotate it 90 degrees and it looks like a tree structure. In fact, this is a tree structure. Now, there are some limitations with this kind of an index. What if you delete a record here? What if you delete multiple records here? The block may become almost empty. But still, what if you insert a record here? This thing has to be sorted. If you insert a record, this block becomes full. Now, what do you do? You have to have an overflow block. But then that block doesn't have a pointer from here. You have to deal with that. So, one way is to just keep one pointer and have a link list of blocks, which you have to search. But what if a lot of insertions happen here, this link list can become very big. So, that's a bad idea. So, a better idea is if this block fills up, you split it, move some other records into one block, move the other records into another block. But now, if you split this, you need an entry from this next level, you need an entry to the newly inserted block. But then this may become full too. And now you have to split this. But if you split, there is a tradeoff. If you split, if it's full and you split, each of these may be only half full, because there aren't enough records. You have 100 records in the block, you split the blocks. The two blocks together have space for 200 records, but you only have 101 records. So, each of the blocks is going to be only part full. That's a tradeoff which B plus trees take. You say, yes, we will live with this tradeoff. Let blocks be only partially full. But the benefit it gives is that when I insert records here, I can split it and add more entries here. And this is actually recursive. This is full. I will split it and add entries here.  This is the key idea of a B plus tree. So, from a basic multi-level index, we now move to a B plus tree structure. B plus trees are going to be shown rotated. And here is a B plus tree structure. What does it look like? This is the underlying file containing the records. And this file in this case is sorted on the instructor ID. But this B plus tree is sorted on. It's key is the instructor name. So, now, if you look at this index, the bottom layer of this is actually sorted. If you see, you have B, C, E, G, K, M, S and finally W. So, if you look at the names, they are sorted. And the next level up has pointers to these things. So, the next level up is actually a sparse index on this thing. Now, each of the key values here has a pointer to the corresponding record in this file. There are no duplicate names. We don't have time for it, but there are ways to deal with duplicate names. We will skip that for the moment. The next level up is the sparse index. So, what does the sparse index need to do? It has to, our earlier avatar of the sparse index had to basically say which is the minimum key in this, which is a minimum key here and so on. Now, if you look at this, it's actually doing something a little bit different. This level has two key values, but three pointers. Our original sparse index had three key values and it would have had three key values and three pointers. It would have had an entry which says the minimum thing here is brand and here is a pointer to this. The minimum thing here is Einstein and here is a pointer to this. The minimum thing here is golden. Here is a pointer to it. Now, B plus trees basically have a small optimization which says for the smallest one, I'm not going to keep the minimum. I don't care what the minimum is. If it, as long as it's less than Einstein, I have to go to that pointer. So, there is no point keeping track of what is the minimum one there. It's irrelevant. So, you're going to have two key values and three pointers in this case, in this particular node. In this particular B plus tree, how many pointers would you have at maximum four and three key values at maximum? What is the minimum you will have? If you allow nodes to have two few pointers, then there's a lot of wasted space and the tree can also become very tall. In this particular case, if the maximum number of pointers in an internal node is four, the minimum will be ceiling of n by two because this is four. The minimum is two and this particular node is actually at the minimum. It has two pointers and it has one key value which serves to distinguish between this. So, if the value is less than Srinivasan, you go here. If it's greater than Srinivasan, the records are on this side. The next level up on the tree is the sparse index on this level. Here, there are only two values. We need a value which helps us decide whether to go here or here. But now, there is another issue here. If I start the minimum value here, what is the minimum value in this node? Is it Srinivasan? If you look, physically here is Srinivasan. But actually, conceptually, there is one more value which we have thrown out and that is really the minimum value. Since I have thrown it out, I can't find it from this node, but I can certainly traverse down the leftmost pointer here and find the minimum value here, which is Mozart. So, that is the value which I am keeping here. So, if I am searching for Mozart, I need to go to the right. Now, I find Srinivasan. It's Mozart is less. So, I will go to the left pointer, come down here and I will find Mozart. If I am searching for a value which is less than Mozart, say Kim. It's less than Mozart. I will go to the left. Now, here is Kim greater than gold? Yes. So, I will go to the right. In this node, I will have to search through the values and yes, I do find Kim. What if I search for a value which is not there? Let's say I search for Mohan. Is Mohan less than Mozart? Yes, H is less than Z. I will go down here. Is Mohan greater than gold? Yes. I will go down here. Is Mohan here? No. So, if I want to insert a new record for Mohan, the first step is to search for Mohan and now Mohan is not here. So, what do I do? I will have to insert the entry for Mohan here at the leaf along with the pointer to the Mohan record. Of course, I have to insert the Mohan record into the file also. So, that is separate. So, I am just worried about the index here. If I have to insert the Mohan record here, what happens? The node is full. There is no space. So, what do I do? I have to split it. When I split it, I have to add an entry pointer to that node above along with a value here which decides whether I go to this node or the newly created node. In this case, there is space here. So, we are ok. But if this were full, this itself needs to be split and then we have to go up. So, the splitting like this can go all the way up to the root. If the root is split, what happens? You get two nodes and you have to add a new level to the B plus tree above with a pointer to the two things. So, that is the basic intuition of how insertions happen in a B plus tree. Now, when all these insertions happen, you will see that the tree is balanced in terms of the height. If you look at this tree, all the leaves are exactly two levels below the root. When I do an insert, if splits happen, a new root is created and all the leaves will be three levels below the root. So, the depth of the tree, every leaf is exactly the same depth. There is another property which is that every internal node has at least n by two pointers. In this case, the minimum is two pointers. So, what is the height of the tree? It could be log to the base two of the number of entries at this level. Now, log to the base two of a million is 20, log to the base two of thousand is 10 and of a million is 20. So, if I have to search through 20 levels of a tree and potentially each of these is in a different disk block, I am in trouble. It is going to take a long time. So, in fact, these nodes are going to be very big. Typically, the number of pointers at max would be 100 or 200 and admin would be 50 to 100. So, now, if let us say the minimum is 100, what is log to the base 100 of a million? It is 3, 100 power 3 is a million. So, then the tree will have at most three levels. So, at most three discios to get down to the leaf level, which would be three times 10 milliseconds or 30 milliseconds, which is a lot better than 20 times 10 milliseconds, which is 200 milliseconds.  There are there is a lot of stuff here, which gives the details of the occupancy, more details about the structure of a node, the properties of leaf nodes, properties of internal nodes. For lack of time, I am skipping all these slides. Then, there are several examples with different n. We saw an n equal to 4. This one is another tree with n equal to 6, 6 pointers from a node, internal node. And you will notice that when n increase, the height of the tree decreased. Earlier our tree had three levels, now it has only two levels. Then there is a query algorithm, which I described informally. The formal algorithm is here. And then this logarithmic time details are on this slide. So, I am skipping all of those. Insertion, again we have described the intuition. This is again presented here, the same intuition, including how to propagate splits. All those details are here, because we are really out of time, I have skipped those. But here is an example. So, I think I will take a couple of minutes at least to work through this example. So, this is a tree initially. And now I am inserting the value Adams into it. So, is Adams less than Mozart? Yes, I go here. Is Adams less than Einstein? Yes, I go here. Now, this guy is full. I have to insert Adams here. So, I split it in two. Now, basically I will take a sorted list over here. Move half the things here and move half the things here. Half the sorted list including Adams. So, I will get Adams and Brandt here and Caliphari and Crick here. So, now when I split this node into two, I need an extra pointer to be added here. I also need to know what is the value which differentiates this node from this node. In other words, the minimum value in this node. So, what I have done here is, I add an entry Caliphari in from this, in this node I am adding Caliphari, Einstein and Gold are still there. The left child of Caliphari is the left node. The right child of Caliphari is the other node. The two nodes resulting from a split are separated by Caliphari. And then the other one, Einstein and Gold remain unchanged. And the entry, the other entries in that node remain unchanged. So, in this case, the split happened here, but did not stopped here. Now, this is another one. The original tree I inserted Lamport. Where does that go? L is Lamport is less than Mozart. Lamport is greater than Gold. So, it is here. So, Lamport goes in here. Now, Gold Cat's Kim is full. I have to split it. And that results in Gold Cat's and Kim Lamport. Now, when this splits, I have to add an entry to the parent. But now the parent, this is the result of a previous insertion. The parent is full. Now, what do I do? I split the parent. So, there were four pointers. Now, there is now one extra pointer. There are total of five pointers. So, three of those pointers will go to one node. Two of the pointers will go to the other node. So, the first three go here. And the last two go here. But there are some details about the intervening values. So, if you see caliphary Einstein, they remain the same. They are the intervening values. Then you had Gold, which if you see caliphary Einstein, those three pointers remain the same. Gold had a pointer to this. But now, this is split into two. And those two, if you see, are separated by Kim. So, this node here has Kim as the separating value and pointers to these two nodes. What happened to Gold though? Gold is now the separator between these three and these two. But Gold no longer stays in this node. It actually has to go up to the parent. Because these three land up here. These two land up here. So, the parent itself, I need to know when to go to this and when to go to that. And that value separating them is exactly Gold. So, Gold has moved up to the parent when the split happened. And it separates these two pointers. So, the pointer to this node now became two pointers, one to this node and one to this node. And Gold is now the separating value there. And that has gone up to the parent. Is this clear? So, this is how splits propagate up. Okay. What are these horizontal arrows? At the leaf level in our structure, there is one extra pointer. Because the leaf level, I am going to have one pointer to the record per key value. I can use this space for something which can be useful, which is to find out the next leaf. If I want to scan the leaves, I can use this pointer. But actually speaking this pointer is many people skip this pointer because it is actually redundant. I can always look at the next level up and find which are the children. And then I can use that to scan the children. Instead of going up and going down, it can go sequentially. However, it turns out that if you do this each time you read a page, you will have to process it and only then you know which is the next page to read. So, now the problem is after reading every page, you have to wait for the next page to be fetched. So, what optimized implementations do is, they will look at this node and say, I want to do a sequential scan and they will issue prefetches on all these four pages. So, while you are processing this first page, the remaining three pages are also being prefetched. So, by the time you use them, they are hopefully already in the buffer. And then when you are done processing them, it will actually go up the tree and go down to the next side. It will not up the tree. It knows where it came from. It will go to the next child and prefetch a bunch of values from there which is the next three over here. So, even for a sequential scan, the next pointer is not useful for prefetching. You want to use the pointers from the parent to do the prefetching. What is the difference between a B free and a B plus free? Both are balanced. The difference is the following. What we have used is a B plus free and you will notice that key values here do not have any pointer to an actual record. In a B tree, a key value here may also store a pointer to the actual record. Now, the original presentation of B trees actually allowed record pointers from internal nodes. Afterwards, people realized that this just made implementation more complicated and it did not give any benefits. In fact, it had some drawbacks. What is the drawback? By storing record pointers here, you are reducing the fan out of this node. If you reduce the fan out, the height of the tree increases. Now, you might say for some records, you can directly access them from here, but unfortunately, most of the records are at this level, not at this level. So, it turned out that it was not a good idea to store record pointers from internal levels and what everybody uses today is what are called B plus trees. So, we have in the book, for example, we have de-emphasized B trees. We just mentioned it somewhere for historical interest, but you do not want to waste time actually dealing with B trees. Just know that they existed and what is the difference and that is it. Do not spend time on actually implementing or dealing with them in any further manner. This is what is used and if you look at database manuals, they will not say B plus trees. They will just say B tree, but by B tree, they mean this one, not the original B tree. They mean this implementation, this variation. Any other questions? I do not know how much it is related to this presentation. I just want to ask question regarding the red black trees. What is the necessity of representing the nodes in the red color or the black color? It is also concerned as the balanced trees. Yeah, there are many different balancing schemes. Red black trees are one example. Two three trees are another example. In terms of the two three trees are a special case of B plus trees. If you have a node with a maximum fan out of three, the minimum fan out is two and a B plus tree with maximum fan out three and minimum fan out two is a two three tree. Now, there are different ways of balancing a tree. There are height balancing, weight balancing and red black trees are one particular implementation. So, that is probably more relevant to a data structure scores, not to a database score. The key problem with all those other structures is that they tend to be binary trees. And for this storage, for magnetic disc certainly, a binary tree is not at all efficient. You want a much fatter tree. You might ask what about flash storage? In terms of even flash storage, access is a page at a time. So, even for flash, a binary tree is a bad idea. Next, you may ask what about in-memory indices for a database system? Why not use a binary tree is there? It turns out that memory today is beginning to look a little like page access, page oriented, not a page, a cache line oriented access structure. Now, what do I mean by this? The processor speeds today are of the order of a gigahertz or multiple gigahertz. It is kind of stopped at two to three gigahertz. But now, the cache which is in the processor runs at this speed, a gigahertz speed. But if you try to access memory, memory systems today still take off the order of 50 to 100 nanoseconds, meaning that it takes 50 cycles of the processor to read even one byte of memory from the memory subsystem. So, instead of wasting time reading one byte at a time, every processor today will read multiple bytes at one go. It reads the whole cache line. How big is the cache line? 16 bytes is common size. So, it reads 16 bytes or 32 bytes at a time from the memory subsystem. Now, if you look at this 16 or 32 bytes, it really looks like a tiny disk page, really small page. And it turns out that B trees with very small fan out are actually better than binary trees even for an in memory index. So, many databases play around with this and even for an in memory index, they may use hash indices. But if they use B plus trees, then they would use things with tiny fan out. And then there are some tricks which combine a page itself in a B plus tree is organized as a set of tiny pages organized as a B plus tree inside of a page. So, there are a bunch of tricks which people use to get faster access to data within a disk block, which is really a B plus tree with a tiny, with a smaller fan out. Other questions? So, there are bunch of slides on how to do insertion. Then there are some details on deletion where we had splits on deletion. We will have merging on splits for insertion match to merges for deletion. But it turns out that when you go under full, if you are less than half full, you may not be able to merge with either of your siblings because they may be full. So, deletion requires a new operation which is called redistribution or borrowing of values from a sibling. So, redistribution again, there are details on the slides and in the book. For lack of time, I am going to skip these details. Maybe just show one example. I am deleting Strenivasan from this tree. What happens here? I delete Strenivasan. This node should have at least two entries here. It has a maximum of three entries. These are the leaf node. If I delete this, it has only one. Therefore, in this case, it tries to merge with a sibling and it can merge with this. So, Mozart, Sing and Wu is what is left here. Now, if this merges, this dividing value here, Strenivasan is now useless. These two pointers merge into one pointer which is a pointer to this node. So, now, what has happened to this node? It no longer has two pointers. It has only one pointer and in fact, it has no key values. So, this is under full. Now, what do I do? Can I merge with a sibling here? Unfortunately, no. This sibling is already full. It cannot take even this one extra pointer. So, at this point, I need to redistribute pointers. So, now, this has only one pointer, the pointer to this node. This thing is gone. So, now, what do I do? I borrow a pointer from this node. When I borrow a pointer, I also need to know what value separates this pointer from this pointer. How do I know what is the value which separates these two? I can search down here and find this, but instead of doing that, that value is already there in the parent node which is Mozart. So, now, what I will do is, I will copy this pointer into this node and move Mozart, the separating value into here. So, what I have got here is Mozart and a pointer to this gold node and a pointer to this Mozart node. Now, there is another thing which has happened here. Now, this node has only these three pointers. This node has these two pointers. So, the separating value between this and this has changed. It used to be Mozart. It is now changed. Now, what is the separating value? It is actually gold, which was in this node. So, now, gold goes up to the parent. It is kind of a rotation. Gold goes up and Mozart comes down into this and that is the result of this tree now. Gold now separates this pointer and this pointer and Mozart separates this and this. Is this clear? It can actually happen that, let me take an example. Supposing I delete gold now from this tree. If I delete gold, what happens? This node now has two entries. Is it under full? No. It has a maximum of three and a minimum of two. So, I will do nothing. I just delete gold and that is it. But note something interesting. Gold is still here. Do I need to do something about it? I do not. I do not care if gold is not actually down here at the bottom. It does not affect anything. It does not affect search. It does not affect insertion. Even if gold were there or were not there, I still have to search down till this leaf and then I will find it or not find it. So, how does it matter if gold is still here? I cannot look at this and say gold is there. In a big tree, on the other hand, this could be an issue. But in a V plus tree, we do not care. So, we will leave entries around which correspond to values which are been deleted and are gone. So, there is another example of further deletion. This example shows the height of the tree actually shrinking. For lack of time, I am going to skip this example also. Now, there is some issues on how to handle duplicate search keys. So far, we kind of assume search keys are unique. What if search keys are duplicate? There are probably three different solutions. One solution is to just let search keys get repeated in the V plus tree. If you do that, the search algorithm, the insertion algorithm have to change a little bit. Actually, insertion does not change much. The search algorithm has to change a little bit. Some details are there in the book. I should note that the first printing here had a mistake in the exact way in which this was handled. So, the errata has a correction. So, look up the errata or the slides. These slides have the correct form. So, you can either look at the slides or look up the errata which is on the website for the case of how to handle duplicates. If there are no duplicates, the algorithms, as stated, do not have any problems. It is only for the case of duplicate search keys that the algorithms have an issue. But it turns out that handling duplicates this way is not a good idea in any case. Yes, you can modify the algorithms a little to handle duplicates, but you do not want to do it for reason which I am going to cover in just a minute. So, the next alternative is to have buckets. That is, the search key is stored only once, but instead of storing a pointer to the records, it stores a pointer to a bucket which stores pointers to a record. What is wrong with this? It adds one more level of indirection, one more IO. Now, that bucket may be under full or over full. You have to deal with that. It is a headache. So, people do not actually implement that in practice. Yet another way is you have a key only once, but store a list of tuple pointers with that key. This is actually implemented by a few systems. But again, this has some overhead. What if this list becomes very big? How do you deal with that? That may span multiple blocks. Then you have to deal with those situations where it is too big and then the biggest problem though still is if you have a deletion, how do you delete that record? I will find the search key. I will go through that entire list till I find the record ID and then delete it. Now, there is a problem here. Now, all the other B plus 3 operations so far without duplicates had a nice guarantee. Insertion is logarithmic. Logarithmic in what? To the base of the minimum occupancy. So, if the minimum number of children of an internal node is 50, the height of the tree is the number of entries in the tree, log of that to the base 50, which is a very small value. So, it is very nice to have these logarithmic bonds on insertion, deletion and search. But if you have duplicates, you do not have and if you follow one of these two schemes we have seen so far, the problem is we have to look at all the records with that search key to find which one to delete. Now, what if half the records in relation have a particular search key value? If I delete one of those records, I am going to search potentially through huge number of records to find the one to delete. That is very bad. So, a much better way which also simplifies implementation of B plus trees is to not use the original search key which has duplicates, but to add on to that search key something which makes the record unique. So, typically a record ID, what is a record ID? A pointer to the record or a primary key or some other sequence number stored with the record which lets us uniquely identify a record. The moment you do this, what you have is a composite key, a key with two parts. The composite key can be used in just like an ordinary key, you know the salt order is straightforward, it is a lexicographic order. So, there is no problem with having a composite key in a B plus tree. The benefit now is that when I want to delete a record, I know its record ID or its unique key value. So, I will search in this B plus tree using the search key comma record ID and I will find exactly the record I want in logarithmic time, exactly the leaf which I need in logarithmic time and then I can delete that node and I am done. So, deletion of a record can be done in logarithmic time provided I make the search key unique by adding on something and that is what most implementations use typically. Now, a B plus tree so far, assume the records are stored in a separate file. Now, it is often useful to cluster the records in that file in a meaningful fashion. I said the takes relation for example, I would like it clustered by the student ID. But what if there are a lot of insertions and deletions to the takes relation? This happens when students register or change their registration, there are insertions and deletions. How do I make sure the takes relation is sorted? That becomes an issue. There are two solutions. One is I will periodically resort the relation and then I will use overflow blocks or something like that and that is the traditional solution which pretty much all databases use till some time ago and PostgreSQL uses that even today. I can ask PostgreSQL to cluster a relation which is to sort the relation and store it in sorted order. But the moment I do insertions and deletions, the sort ordering goes for a toss. How do I maintain the sort ordering now? That becomes a problem and the solution it is actually to use a B plus tree again. The trick is instead of storing record pointers in the B plus tree, I am going to store records in the B plus tree. So, here is an example illustrating this. This is a B plus tree on what? It is on some search key. I am just using a single letter C F to represent it and the records on the other hand are there at the leaf. If you see at the leaf, it is not storing a pointer. It is storing an actual record. A4 is the actual record and now I may have three records in this leaf, two in this. So, the records are actually stored here. So, this is called a B plus tree file organization. Now, this looks simple enough. In fact, it is simple enough. So, then you may ask why did most databases not implement this initially? Why did they implement it only recently and PostgreSQL has not implemented it yet. DB2 implemented it like a couple of years ago. Oracle implemented it maybe three, four years ago. Now, why is it such a recent thing? Part of the reason is that there was not enough demand for it, but initially they thought there was not a demand. But the second issue is the moment you allow records to move around like this. The notion of a record ID is a problem. Note that records are moving. Why do the records move? If a leaf becomes full, I split. Half the records move to a new page. Now, I have been assuming there is something called a record ID which is typically a page and a offset in that page. Now, a record ID completely changes the moment a record moves. So, I cannot use a physical record ID anymore. And the problem was most databases when they were implemented had the notion of a record ID hard coded in their code. If you allowed records to move, record IDs were no longer meaningful and that cost a lot of problems. So, in order to implement relations where records can move, you should not be using a record ID elsewhere. What do you use instead? If I cannot have a record ID, what do I do? The trick is that this B plus 3 file organization is on some key. That key itself, let us say it is on the primary key. That is a common mode. But whatever key it is on, that key has to be unique and uniquely identifies the record. So, the trick is now wherever I used record IDs earlier, why do you use record IDs? I use it in other indices, other structures. The record ID now which I should use will be this search key. And the search key will include something to make the record unique. Now, earlier I said the record ID makes it unique, which is the physical location. But now that is meaningless. So, what I need to do instead is store some unique value with the record, maybe the primary key of the record or maybe something else which is added artificially. So, now everybody else has to store this search key which includes that primary key or something else which makes it unique. So, this is what everybody else should store. So, that is detailed in record relocation in secondary indices. I am going to skip the detail here. For lack of time, I am going to skip a few more details. Maybe I should just mention this, because this is something which people are not aware of, which is if you take a database, create a relation. Let me go ahead and ask you a question. There are two questions to you. One is, by creating a single index, can we link it to multiple files, multiple data files? Is it possible? Single index which refers to multiple different relations. That is actually potentially something very useful. Some databases do implement it. So, yes, it is a good idea, which is a very nice question. Now, why is it useful? For example, if you are joining records from those two relations on that key. If you just search once on this index, you will find those pointers to those records and you can fetch them and join them quickly without traversing multiple indices. Second question is, how to choose an attribute on which index can be created to improve the access efficiency? That is another very good question. The question is, what indices should I create for a particular database? So, there are two parts to the answer. One is, every database automatically creates a number of indices. What are these indices which are automatically created? If you declare a set of attributes to be a primary key or a unique key, automatically an index is created. Why? Because to enforce that constraint, when you insert a tuple, you have to see if that key already exists and unless you have an index, you cannot do this efficiently. So, every database automatically creates that index. The second automatically created index is if you have a foreign key reference from something to another relation. Now, if you delete a record from that other relation, you have to check if there is a key value here, which references that. If you do not have an index on the foreign key attribute, you cannot check this efficiently. You have to scan the relation. So, these two kinds of indices are created automatically. Now, what other indices do you create? That is a function of the queries which you have. For example, name may not be either a primary or a foreign key value, but maybe you have a lot of queries on name. So, if you do that, you may want to create an index on name. Now, how do you know you are going to get a lot of queries on name? When you do the schema design, you do not have any idea really. It is only when you build a system and create the queries on that system, do you know what queries are there? Even then, you may not know which queries run frequently and which queries run very rarely. You may not want to bother about a rare query. So, what happens typically is you build the system, load the data, run a typical query workload and see what queries have run. And then, you want to see what indices would have benefited these queries. So, one way to do it is you do it manually. You have a database tuner who sits and looks at these queries and figures out what could be useful. But it is actually quite hard because you do not know what plan the query processing engine is using. So, it is actually a hard thing for a human to do. So, today, most commercial databases, SQL Server, Oracle, DB2, SciBear, all of them, provide a tool which is called an index tuning wizard which will let you record a workload of queries which are executed. And then, for that workload, they will figure out what indices are most useful. And they will suggest that you create the index. And if you say, okay, go ahead, they will create the indices. So, for any real deployment, these tools are very useful. Now, in Postgres, such a tool is not available, but you can, it still provides some monitoring features. So, you can find out which queries took a long time to run. So, then if you look at that query, it took, you know, two seconds to run. Why did it take two seconds to run? So, you can look at that query and say, but this query really wanted only people with a given name. They say, okay, I should create an index on name. So, you can do it manually by this tuning process. And Postgres does support the tuning, supports manual tuning. Use the mic, please. Sir, when we are accessing the database, that B plus tree should be in the main memory. No, B plus tree is brought as sequined into the buffer. The entire tree is on disk, pages which you access are brought as needed into the buffer. And during, if the records are stored in the B plus tree, that previous slide shows this. The B plus tree file organization. Then, then fetching things, putting these things into the buffer, it will take a huge amount of time. Actually, we are, we are brought in the whole record in the buffer. Yes. And in any case, when you access the record, the block containing the record will be brought into the buffer. Now, in this case, the particular block is actually the leaf level of the B plus tree. There is no. If leaf contains the record itself, then huge amount of IO has to be done. So, let me reinterpret that question. The question is the leaf contains the record. Originally, we assumed it had a search key and a record ID, which is small. Now, if the record is large, then the number of leaves of the B plus tree can increase significantly. So, maybe the height of the B plus tree may increase. That is a trade-off. In any case, there was an implicit extra level where you followed the record ID to the page containing the record. So, that is now explicit in a B plus tree file organization. So, really, there is no performance difference between the two. It is not an issue really. The real issue is that records move around and all other parts of your database have to be written in such a way that this will not cause havoc if records move around. Okay. Now, to get back to this slide, another performance issue is if you do the following. If you create a table, create an index on it and now you load a large number of rows. Load a million rows into it. You will find it very slow. So, yesterday we were playing around with Perscrisql and we loaded 100,000 records into a table. And guess how long it took? It took like 45-50 seconds, which may not sound like much. But if you do a million records, it is 500 seconds. And why is it so slow? Actually, if you take the amount of time to read a million records from disk, it is nothing. If they are 50-byte records, I could read them in one second. Why should this take 500 seconds now to build an index? It turns out that on very large relations, if you insert records one at a time into a B plus 3 index, you end up with a lot of random IO. Similarly, if you do another reason for this is if you have a foreign key declaration, when you insert a record, it has to check if the foreign key is satisfied or not. So, for each record which you insert, it goes and checks the foreign key one at a time. All of this results in a lot of random IO, which is why 100,000 records took 40 seconds. Now, most databases provide a workaround for this problem. What they allow is what is called a bulk loading facility, where you can say here is a file containing 100,000 records, load this file into the database. Now, what are the tricks that the database will do now? First of all, for all primary key, foreign key declarations, instead of checking them one at a time, it will actually do something like a join of this relation with whatever it references and that is much faster than probing one at a time. It will verify the integrity constraints that way. If there are indices on this, it will bulk load the indices. There are algorithms which let you build an index on an existing relation very fast compared to inserting one at a time. Those are called bulk loading algorithms. So, all of these are done by the database transparently and therefore, if you are loading a lot of data, it is a bad idea to insert them one at a time from a query, insert, create a file and use the bulk load features of the database to load it. And this particular slide here talks of one aspect of which is how to build a B plus tree on an existing relation very fast compared to inserting one at a time into a B plus tree. Again, for lack of time, I am going to skip it, but this is called bottom-up B plus tree construction. If you are interested, you can read it up later. There is some surf on multiple key access which I think is straightforward. You should be aware of this already. I am going to skip that and wrap up one last thing. If you want to create an index, you can run this query in SQL. It is actually not part of the SQL standard, but most databases support it which is how to form create index, index name, on relation name with a list of attributes. And optionally, they take what kind of index. If there are multiple types of indices, you can specify what kind of index to create. So, in today afternoon's lab, we will actually play around with creating indices on PostgreSQL and then see the effect of creating an index on certain queries, on the query plan, on the time it takes and so on. So, that wraps up indexing.


Now one of the biggest consumer trends is the ever-growing need for personalized custom experiences. Potential customers no longer set it for one size fits all product and services. They choose companies that offer them something more. A customized product or nurturing customer journey. If you implement the right tools, we can meet customer needs as well as business needs. Every business goal is to ultimately increase revenue, attract more new customers and retain existing ones. Now one of the best ways to leverage technology is to improve your existing infrastructure and automate processes like email marketing, to better suit your target audience. Also the mobile app industry in Nigeria has seen tremendous growth over the last decade with increasing smartphone and internet penetration. Apps have become an integral part of daily life for many Nigerians. We will focus on how technology is boosting growth in businesses in Nigeria. Welcome to Business Insight and Plus TV Africa. I am Justin Akadone. Welcome back. Now the Deputy Secretary of the United States Department of the Treasury Wally Adeyemo has made a curtsy visit to Nigeria. During the visit he had an interactive session with Nigerians highlighting economic and cultural ties between the country and the United States. We'll take that report and I'll come back to talk to my guest this morning still with us. A large gathering of dignitaries and individuals at the Lagos Business School Deputy Secretary Adeyemo is the ice ranking Nigerian-American official and ice ranking member of African diaspora in the Biden administration. His visit to the country is simple to highlight the economic and cultural ties between the two countries. The team of the events which is tagged in our economic relations, people, entrepreneurship and investment create an avenue to promote economic ties with Nigeria and the United States. In our remarks, the Vice Chancellor of the Atlantic University, Professor Enade Okoleda, speaks on the importance of international relations as a single country cannot stand on its own without help from others, especially the areas of economic growth and development. As a state, this is a major investor and trading partner with Nigeria and we hope to see an enhanced trade and investment relationship between our countries with your visit to Nigeria. With economic relations and trade between both countries occurring at significantly high volumes, conversations between the Lagos Business School community and such an important trade and investment partner to Nigeria is most opportune. While he Adeyemo highlights the need for Nigeria and the United States to come together to promote international trade and boost Nigeria's security. He also discusses opportunities available through programs like the African Growth and Opportunity Act, which has provided eligible sub-saharan African countries, including Nigeria, with duty-free access to the U.S. market for thousands of products. I'm here because unlocking Nigeria's economic success can transform not just a country, but an entire continent. But in order for us to make progress, it is important for us to focus on and there are of course many reasons why the U. United States remains committed to this partnerships and the reforms that Nigeria needs to make. From our people-to-people relations to our shared values to our common economic and security interest. I want to spend the remainder of my remarks highlighting some of the steps needed for the type of growth that creates economic opportunity for the Nigerian people. First, Nigeria needs a stable Naira. You stop into any small business or market and you will hear shop owners and customers bemoaning the lack of a stable currency. Unifying Nigeria's foreign exchange rate will also create the kind of macroeconomic stability that is essential to attracting foreign investment. The meeting breaks into our question and answer session. Salient questions are raised on the contribution of the United States towards fostering support to the Nigerian government. As expected, the Deputy Secretary did justice to them. Foreign direct investment, including dollar-based foreign direct investment into the country. I think the early steps the government has taken are important in terms of what they've done in terms of fiscal policy and what they've done in terms of trying to unify the exchange rate but more needs to be done and they recognize that. And I think the truth is that as companies around the world and the private sector becomes more comfortable with their approach you would expect that Nigeria would be a destination for foreign direct investment because of companies like your own but also because Nigeria has such a huge talent pool when it comes to labor and opportunity. As you know or you may not know President Biden had a chance to see the new your new president on the sidelines of the G20 and talk about the security situations in the region and how we can deepen our relationships. We look forward to continuing those conversations because we know that in many ways security and economics are very tied together.


Hello and welcome to the session. Let's discuss the following problem today. Let every function defined from R to R be defined as fx is equal to 3x. Choose the correct answer A, f is 11 on 2, B, f is many 1 on 2, C, f is 11 but not on 2, D, f is neither 11 nor on 2. Now let us write the solution. Now let us first check for 11. Let x1, x2 belongs to R such that f of x1 is equal to f of x2 which implies 3x1 is equal to 3x2 which implies x1 is equal to x2. Therefore f from R to R is 11. Now let us check for on 2. Let y be any real number in R of codomain then fx is equal to y which implies 3x is equal to y which implies x is equal to y by 3. Now y by 3 belongs to R for y belongs to R such that f of y by 3 is equal to 3 into y by 3 which is equal to y. Thus for each y belongs to R of codomain there exists x is equal to y by 2 belongs to R of domain such that fx is equal to y thus f is on 2. Now f is 11 and f is on 2. Therefore f is a bijective function. Therefore the correct option is a which says that f is 11 on 2. Hence a is the correct answer. I hope you understood this problem. Bye and have a nice day.


Hello and welcome everyone, thank you for coming to this month's Poem Jam. I'm John Smalley, a librarian with the General Collections and Humanities Department in the Main Library. While we're waiting for a few more people to join us, I want to take a moment to acknowledge our community. On behalf of the Public Library, we wish to welcome you to the unceded ancestral homeland of the Ramatish Ohlone, who are the original inhabitants of the San Francisco Peninsula. As the indigenous stewards of this land, and in accordance with their traditions, the Ramatish have never ceded, lost, nor forgotten their responsibilities as the caretakers of this place. As guests, we who reside on their traditional territory recognize that we benefit from living and working on their traditional homeland. We wish to pair our respects by acknowledging the ancestors, elders, and relatives of the Ramatish community and by acknowledging their sovereign rights as First Peoples. Thanks again for coming to this poetry reading, which is part of an ongoing series, the second Thursday of each month, and it will continue next year. If you're interested in our poetry and other programs, there are flyers on the table, as well as newsletter. Feel free to help yourselves to those, as well as do coffee and cookies. So now I want to introduce the host of the series, our beloved Kim Shuck. Please give a warm welcome to Kim. Everyone should probably have a job where somebody introduces them as being beloved, and then you get applauded. It's kind of fun. This is a particular enjoyment for me tonight's show, because Sarah Beale and I have known each other almost 20 years, and we have worked on a number of different points of activism in unison, and we have read together a lot from poems about Barbie dolls to poems that ended up buying the Ninth Ward in New Orleans materials for their clinic after the levee breaks. So we've done a bunch of things together, and I'm really delighted with the new series of books that she has been working with other people on. So on this very cold night where we're all sort of huddled in here stress-eating Neapolitan Oreos and hanging out in the poem dungeon here in the San Francisco Main Library, I just really am delighted to introduce you to a good friend of mine, who is also a really amazing poet, Sarah Beale. Thank you so much, Kim. Thank you everybody for coming. I'm so excited to see all of you, and I'm so excited to talk about the work that Colossus Press, we've all been doing together. We started with Just Colossus, which is a short chapbook that we put together that helped fund Freedom for Immigrants when the former presidential administration was separating families at the border, and that really struck a chord with the poetry community in the Bay Area, and now here we are working on editing our fourth book. So welcome. We do have Books for Sale, both Colossus Home and Colossus Freedom, and I hope people are interested in buying them, and I'm really excited to be here in this room hearing all this amazing poetry from our books and also just from our amazing poets. So I thought I would start with reading my poem from Colossus Home, and then I'll read one other one. So, umbilical home. First there was an ember, a splintered spark, moment of catch, germination. Each history roots in unique terrain, unfurls from an umbilical home. We creatures are tender fruit, always vigilant. We listen for the peripheral call, God-recognition along this distant music, humming us back our crooked rambles, anthems, jingles, laments. Songs pulse the crackle of evening fires, surge a laughing cacophony of wing-filled flocks, croon the caress of newborn grass, tease with jump rope rhymes, smack and giggle sun-warm schoolyards. Some of us were sung in deep shade. Our songs whisper a memory of absence, perpetual cannons chronicle the weight of empty arms. Our symphonies rage, eruptions of fear, violence, marbles, fragile hearts. Our tunes are toxic, flickers of blue flame, poison rises in feathered rivulets, catches the ankle of every escape. Each song is a singular vessel, tenacious, not immutable. We could compose new hymns and sing them brash from porches, balconies and fire escapes. Let's sing for a constant, an endless offering, a place of return, of rhythmic possibilities, licked wounds, sing the smell of oranges, a kiss to the nape of a worry-wound neck, a refuge for dreams and remade plans, a refrain whole enough to hold all the tears, laughter, fights and midnight snacks we gather as we rock ourselves to sleep. Thank you. All of the money that we get from Colossus Home goes to support Moms for Housing, which is, as you may have heard, a local Bay Area nonprofit that was started by unhoused moms in Oakland who took control of an unoccupied building, which there are many, many, many of in both San Francisco and Oakland, many more unoccupied buildings than there are unhoused people. And that is 100% true tonight, right here in the rain in San Francisco. So we may need to rethink how we handle unoccupied buildings. And then all the money from Colossus Freedom goes to support California Coalition for Women Prisoners. Thanks, Kim. I'm going to read like the kids do from my phone. Okay, so this is a really new poem, but it was the one that was on my phone. And it is called Phase Change. After silence has curled to settle deep in dust-filled corners, after the front door remains closed, its weighty latch clicked flat and final. After your tea has gone cold, amber leaves float fertile with memory. After their names live on your lips, eager as bright morning prayers. After, explore your old places, the ones that pinch and the ones that rejoice. After, the mind unwinds, it rolls the same old stones between its dry palms. After all, we face the same moon, the same flawless unknown. Now, a tributary, a different type of spring, spreads fingers, unfolds flesh. Now, you see the workings of the wind, the cliffs it makes of grainy sand. Now, night after night, your thoughts grow thin, serious broken by rumpled dreams. Now, you're patient with weaving, with trying over, with cracks and mistakes. Now, on the way, there are rocks you hold, small lines that crimp around your heart. Now, with the light's gradual shift, you notice the glow because of the dark. Now and then, watch the sunrise bloom, reach for its offered palm. Thank you. Kellyanne Parker. You're next, so I'm going to give you a minute and say this. Sarah did great, didn't she? Can we have a really big applause for Sarah? Sarah didn't know she was reading tonight. She thought she was just introducing people, but I lure her to this stage so infrequently it's really important to get her to say things into the microphone when she's here.  She's been co-hosting My Word Open Mic for several years now and is a regular Bay Area feature. She has seen how her community has been set up by the engineered genocide of addiction built by the US to oppress communities of color. It's generational trauma by design that continues to lead the cycle of violence, addiction, and ultimately incarceration of friends and family. Her upcoming book, Down the Foggy Streets of My Mind, is due to be released by Nomadic Press in February 2022. Now that I'm reading that, that book exists because I have a copy on my desk. So please welcome Kellyanne Parker, the mic in the middle. Thank you, sweetie. Hello everyone. Oh wow, it's really wonderful to be here. Hugs. And I'm going to read a poem from Colossus Home that I was a part of that is actually in my book. And that talks about genocide. I'm going to start by reading my essay that is in Colossus Freedom. And what I would say is follow the Colossus series because it's doing really incredible work. And I know that some of the things I'm most proudest of is in Colossus. So thank you so much. And for those who don't know me, I talk a lot about mental illness and addiction. And of course, all these things tie into generational trauma. And so I'm going to read my essay called Genocide by Addiction. And this is an account of my family. My mother was born in East LA where my grandmother grew up. After the end of World War II, they were among the other colonized mind families who bought homes in the San Fernando Valley on the GI Bill. They settled into Panorama City, which would become largely Latinx. There they bought into the American dream, everyone working to get ahead. But my grandfather came back from a war, a casualty of it.  This pattern would repeat itself many times over. My family that stayed in East LA would face even more loss. Once when I worked on my genealogy, I found out that the war hero story about my grandfather was a lie. When I looked up his military records, he'd been in a military prison for two of the four years that he served. It matched with my grandmother's story of he and a friend waking up inside of a candy counter in some other country and being demoted back to private. Somehow he managed to get honorably discharged. Along with diabetes, liver and pancreatic cancer would take so many in my family. As each generation slowly denied its identity, it would make space for something awful and hungry to consume what was left. Still, we made room for traditions and every Sunday was an all-day event at my grandmother's. Many happy memories there. Soon another war would come and ask for poor and people of color to be on the front lines. I had five uncles that went to Vietnam. None came back whole. One on the very front line went AWOL every so often, hid in the jungle until he couldn't. He would come back by a motorcycle and disappear for many years. Another came back suicidal and would slowly die of the effects of Agent Orange. Others came back addicted to heroin, a gift from Uncle Sam. One would find himself in jail for selling heroin he needed to make money to keep using heroin. So while the U.S. was the original drug dealer, this small pawn trying to make it to the next day would find himself in jail. Having 12 siblings makes for a lot of letters to the judge, but still he went to jail. This story could be told by so many. That poverty, poor health, and drug addiction are engineered by design by this so-called great country. The differences became clearer to me as I got older. Growing up in Granada Hills, I was removed from the constant drive-bys that my friends who lived by dealt with. Like my friend who grew up in the tinder keg that was Lake Butaris. Her brother was the casualty of domestic violence who would be murdered in his jail cell. And then there's my good friend in school. She was a great student and a kind person. We ate lunch every day together in junior high and often in high school. We couldn't go to each other's house after school because she was bussed into the school. I remember the time she told me in the eighth grade that her boyfriend had died while cleaning his gun. All I could do was say I was sorry. I listened to what she told me and was careful not to ask too many questions. I think about her from time to time and I wonder if the system made her too. This next piece is in my book Down the Foggy Streets of My Mind and it's in Colossus Home. It's called Morning Mission Musings. Today I wandered the Mission District in San Francisco. I watched as construction people furiously polish it to a shine. It made me reflect on where the people go. The ones who are never new and shiny, where do they go now? Those gritty city folk who were born with old souls and world weary eyes. The ones whose faces are freckled with car exhaust. For while I love things new and shiny, I have a deep appreciation for places that have had their shiny worn down and threadbare. Worn down to a realness and sheer enough to see through a gesture rolled out of bed self. Those are the places for all people. For people unwelcome in shinier places. People who are different. Whose islands of refuge are constantly shrinking and shifting. As I walk today I think about what I love about the Mission. The mission I remember is a place of welcome to people familiar with being unwelcome. I think about the impoverished immigrants or even refugees from a more domestic yet hostile way of life. Trying to eke out some small space of comfort. I think about the homeless and how they're unwelcome not only in neighborhoods but sidewalks and parks and underpasses. Where next? As I walk down the Mission and then Valencia, I feel compelled to capture its essence before it's gone. There seems to be a pattern between alternating old with new. I linger at the older established businesses and look at the bumpy lacquer of tape melded to the window. Competing with the cloudy patina of hand prints. These are the hand prints of real people who once belonged to there. And I wonder where will all these people go? Thank you Kellyanne. It's good to have you back here. Now the thing about shutdowns and reading people's work and not seeing them read is that I have now asked for the pronunciation of this first name three times and I still don't have it in my head so I'm going to give it a whack. Elisa Salison is a poet and educator in Berkeley, California. She's had essays, op-eds, photography and poetry published in AMP, Always Electric, SF Public Library, Poem of the Day, Sparkle and Blank, Counterpunch in the Bay Area, Writing Projects, Digital Paper. Her first chapbook will be published by Finishing Line Press in 2023. Please come to my stage. I've taken to using a music stand when I read. It makes me less nervous. So does saying that I'm nervous make me less nervous, so. All right. I'm going to start with my piece from Colossus Freedom. It's a piece about my mother. In 1958 my mother, Susan Salison, was one of a string of young women who were brutally attacked on the streets of Portland, Oregon. She was 16 years old. Susan went on to dedicate her life to issues of women, trauma and PTSD as one of the grassroots organizers and founders of the trauma-informed care movement.  I didn't believe it for a long time, but then all of her friends and colleagues were like, no, no, that's true. It was her commitment and determination that kept trauma on the public mental health agenda. And a strong focus of her work throughout her life was building systems of healing and transformation for incarcerated women, their families and communities. This piece that I'm going to read is taken, some of the language is taken from newspaper reports at the time of these incidents in Portland. My mother used to say she died once. My mother used to say she died once. My mother died before she was my mother. She died once in the gutter on Southwest Green Avenue, portaged across the overflowing silence. My mother died before the next three sluggings, before the boy with the blunt instrument hit three more girls, portaled bodies clubbed and silence multiplied. His only confession was, I don't know why. The boy's blunt instrument hit again and again and again, my mother's first death, a light motif. He confessed, but the boy didn't know why. Her first death, a point of no return. My mother's first death, a survival, an echo through trembling connection. Her first death returns and returns layered into the DNA looped through me, echoed through you, reverberations ripple woman to woman awake, layered into our voices looped through every contraction, each new moonrise. Woman to woman to woman, an invocation from marrow and belly we roar into every contraction into each full moon. Our chant, we do know why. From marrow and belly we keen into our ever-dying selves. Our kindled fire, this chant, a flame with knowing. My mother used to say she died once. One more about my mom, owed to my mother's gold nail polish. My mother's ten fingers metallic hue shines halo onto lipstick smeared teeth that frame her boozy laugh, her hippie dress, her breast spilling out when she raises an arm to pull another wine jug from the grocery store shelves and teenage me hiding in the next aisle embarrassed by those golden nails and wayward boobs. I wanted nothing to do with her careening and crashing histories. My mother now paints my daughter's nails golden, wild delight and bling five-year-old hands glint in sunlight, flashing spirit to the world, tiny fingers invincible with priceless shine. My girl is glittery glam, her grandmother's golden gift, ten fingers of metallic wonder. She paints the sky with dazzling daggers and magical rays that shoot from newly adorned digits her power now complete. She is precious metal, she is a riferous joy. With a floor as my girl displays her glitzy glory to the neighbor lady, the one with artfully frosted hair, matched Kazmir's sweater set, the one who sips chardonnay but never too much, the one who is everything my mother is not. I hear that perfectly muted woman ask my 24-carat girl, does your grandmother really wear gold nail polish? My arm-shimmered child deflates ever so slightly she pulls her hands away. In the weight of my daughter's silence, I open my own hands. I spread my fingers wide, their naked nails close-cropped and ragged. Their accumulated dirt ridges, cracks, their imperfection, their promise of alchemy. It's all the same to the ocean. I am pressed flat between hearts of others and so I escape to the sea, standing high above roiling surf where the waves lure beckons. For a moment I sway on cliff edge ready to give myself to waves that do not ask and do not judge. The waves do not know of lists that keep me awake at night and they do not have to count my mother's pills tomorrow morning. The waves do not speak strained teen silence on the car ride home. They are indifferent to depression from below and dementia beyond. And the waves know nothing of my denial that the space in between can no longer bear the weight of his touch. The waves never have to search for the right words to say goodbye either too soon or way too late. My obligations, my aspirations, my turbulent desires are meaningless.  The waves will sweep me away as I cast my body into their beckoning arms. It's all the same to the ocean. I am a rotting sea lion carcass. I am giant bladder kelp untethered. I am no different from driftwood, tossed and floating wild, worn smooth, porous. And I have one more poem. This last one is from my chat book that will be released on Finishing Line Press in February. I brought some cards and put them over on the table there if you're interested. And many of the poems in this chat book are about my experience with my uncle. And in his last weeks of life, Sal Salison was a poet himself. And this is the Albaad for Sal. Oh, Shenandoah, I'm bound to leave you. Naked on his back with legs and arms grasping grasping air grasping wild fear and flailing anger grasping for his exploded desire. I climb into Sal's bed and sing to him. I hold him as he lunges for the window a last hope for escape on this his last morning on earth. I should let him jump through that portal down into a stranger's backyard. I'll follow and we'll scale the fence cross the street to Berkeley Bowl grocery where we'll buy his favorite double chocolate chip ice cream and sit together on the curbs, trading spoon back and forth, sweetness slowly melting on our tongues.  And I into my renewed materiality. But I hold him back from that window. I seal his final hours. I sing him away rolling river. I'm bound away as he invokes Shakespeare and whispers Rilke and Ray Carver. I initiate the farewell kiss as he softens and slows closes eyes and opens hands wide dropping seeds of morning into my waiting arms. I press the seeds between these words for safekeeping as Sal flies out that window pulling pulled upward away rolling river away by beloved oracles of language. And I watch him fade toward distant words. How can all this weightlessness survive? Thank you.  Suzanne Dykeman is the author of two full length collections of poetry. These are dark ordinary furniture press books and equilibrium's form. Sharesman books as well as the chapbooks counterweight, transitioning indigo source hearing loss and in collaboration with Elizabeth Robinson, Vivian Mar 11 photographs and 20 poems. Her work has appeared in a number of journals most frequent recently fence parentheses and Colorado review. She lives in rights in Albany, California. Thank you, Sarah. Thanks to the public library for having this reading. I'm very grateful to have been involved with two of the anthologies home and freedom and I care deeply about the work that these Sarah and others have done putting these books together. I'll start by reading from freedom. And this is a piece inspired by what happened at the border with babies and their families being separated and the babies being caged. It's called taken one. When one child is taken. When all the children are taken away. When you must have the child. When the child's belly is empty. When your belly empties of child. When the trees continue to grow. So many shades of green. When morning birds sing their songs. I know none of them. When childhood left when the heart is split. I want the hammer. I am the hammer that breaks as the earth opens a crack to gathered steam. Untenable pocket of heat as water rolls over the body it leaves salt on skin. As I write today's date as I wrote the date when the child was taken. It is molten to the hammer is small. I swing my arm aim beyond my hand. I keep swinging when the children are taken. When the hammer sings songs of birds. Childhood broken. When childhoods are ripped away. When blood is disturbed in the fissure. The fissure seeps. The hammer hits my nail the bruise not memory. When the hammer strikes rock it hopes. When the children are returned. When the child will never come back. When the fissure will not close. As I walk around it. As we talk around it. The egg that has split. The baby that is made. The child we hold. The dimpled hand. Next I'll read my pieces that two pieces that were in Colossus home. And though I have not been homeless. My mother experienced it. And that gets passed down within the family. Something that one continues to feel. So it's an important subject home. With little room for. With little to be held under a single roof. Shared but separated barely by walls. Run down as rain runs down to stain. Then hold. Being a village where one rests or lies. With many under one. As in the Irish from deer. Something near cherished. But how to cherish such source. Which is also the same as and. Our long and final purpose. From what one needs. Dear dream. You have me disputing the end of the road. Which highway terminates where. I am confusing myself. Isn't there a crossing of the two. No matter that truth I have landed here. Mossy memory. Not originally from me but given to my body. Always damp with the question. Where will we live. I was raised to ask that carving it as a theme. With one who was lost the one dead. Eviction as where to live now. You dream land in a junction close to a bay and sand. Near a river that makes its languid way through the edges of town. I call out home. And finally I will read a piece that's. More like prose than poetry. But you can decide that it's called. Punching the body. Uncertain of the state of my lungs. Breathe in and breathe out. The emotions associated with the lungs in Chinese medicine. Our sadness or grief. Uncertain of the state of my skeleton. Spine moves forward and spine moves back. Traditional Chinese medicine states that the kidneys are in charge of the bones. Essentially the skeletons growth and repair are related to the kidneys. And the kidney is related to fear. Emotions. Weak willpower insecure aloof and isolated. Let me draw this out. The news has not been good. Yet remember how not long ago you stood on a levy and watched the motorboat slow as they passed the dock. And recall how the road built across that levy was too narrow for more than one car. But had a broken yellow line painted down the middle of the pothole asphalt anyway. And that the field stretched to the horizon. And as you walked the high ground you saw chicory and cowsbane and wild California rose. And a tangle of blackberries with flowers but no fruit yet. And remember the orchards. Those were acres of pear trees have been pulled out. Trunks and limbs left to dry in the sun and wind. And how it felt looking at it like a slaughter of innocence. The orchards bounty. That I won't draw out. But the levees were peaceful bordering the waters that drifted across the land as they made their way westward to the ocean. Unseen from where one stood. But knowing that was where they were going. Moving like fingers to all connect eventually to the one palm of the hand. And how we had to discuss how to say slew even though we are native English speakers. But ones who read more words than we can speak. Is it pronounced like slew? Or is a rhyme to thou? Or should we forget it altogether and substitute the word tributary? Simply because we find some words difficult to say. Thank you very much. Rebecca Lee Whiting is a lawyer and a queer writer of color based in San Francisco. Rebecca's poetry has previously appeared in Colossus Freedom, Feminine Collective, and Prometheus Dreaming. An MFA candidate in poetry at Bennington College, Rebecca also serves on the board of editors of Colossus Press. Welcome. Thank you so much, Kim, and thank you, Sarah, for hosting this. I'm really excited to read a piece for you all that is in Colossus Freedom. I wrote this, it's called Chento for Roe, after the oral argument in the Dobbs decision last year, which later became the decision overturning Roe. And I chose the Chento, which is a sort of patchwork poem, for those of you who are not familiar, based on sources that include both poems and then also Supreme Court decisions. So drawing on my legal practice. So this is Chento for Roe. Tell me about despair, yours, and I will tell you mine. Choices concerning contraception, family relationships, procreation, and child-rearing. Every single one of these laws is called a dequestion. My responsibility is to tell you the truth. They used to say, the right to personal choice is implicit in the concept of order liberty, fundamental to our very existence and survival. I was newly naked, aware of myself as a separate self, distinct from dirt and bone. They used to say, our whole constitutional heritage rebels at the thought of giving government the power to control men's minds, women's bodies. Anything may happen when womanhood has ceased to be a protected occupation. They used to say that all men are created equal, that they are endowed by their creator with certain unalienable rights. Most of the time, my mind gnaws on such ridiculous fictions. We are born with dreams in our hearts, so free we seem, so fettered fast we are. When we learned how to behave in America, they put me in the closet because they liked me still. There's never been equality for me nor freedom in this homeland of the free. Each month it got a little less civil, terrible weights of stone, relentless. Darkly I gaze into the days ahead, I imagine the body giving itself up for another system. What will they say? That the paramount destiny and mission of women are to fulfill the noble and benign offices of wife and mother. That life in a box is better than no life at all, barely daring to breathe or a chew. Will you speak before I am gone? Will you prove already too late? You are wasting time and we have so little. Who can open the door who does not reach for the latch? When it's over, I don't want to wonder, how will we survive?  For the eyeing of my scars there is a charge. You may write me down in history, but there is no gate, no lock, no bolt that you can set upon the freedom of my mind. I am treacherous with old magic. A woman like that is not ashamed to die, and it will never end until it all ends. Open this when you need me most.  When it's over, I want to say, oh my enemy, this is a torch song. Touch me and you'll burn. And then I have another poem for you, which I think is also apropos on the subject of freedom. It's called American Dreams. In my dream, I am a conscript sitting on my pack with my band of brothers in arms and a clearing at the edge of a lush hillside forest, at the end of a day of mindless walking, tending to my imagined soldiery tasks, changing my socks, cleaning my gun, the sky above us, a wash of pastel rainbow sherbet melting into lazuli. The way dream sunsets are somehow more perfect even than a technicolor showstopper prismed into being by flecks of carbon on a winter day. Cold gun in my warm farm boy hands, I marvel at the piercing beauty of this place I never should have seen, terraced fields of rice carved from cragged limestone mountains, riffling brown river below. And just when I begin to forget why I am where I am, the hillside royals erupts in vermilion clouds of fire billowing to black.  The sharp sounds of the jungle and my own ragged breath and then silence. I know it's just a recurring dream and not a memory from a former life, even though it's always the same, same pink sky, same wide calloused hands, because it doesn't make any sense. We were the ones with napalm. And anyway, the Tibetan Book of the Dead says that you pass through the womb door into the next life in an instant. And I was born in 1985, not 1968, and I don't think I was lucky enough to be someone's coddled house cat in between. So I know I could not have been this reluctant teenager sent halfway around the world to kill people who look like me, granddaughter of a paper son. Our family tree, a paper trail of fictive sons and real nephews reaching all the way back to Guangdong and our own rice patties. Paper, not blood, because we had the wrong blood for America, but still we managed to be in the right place at the right time. In San Francisco in 1906, when that famous fire burned the public records, and my great-great-granduncle made himself a 14th Amendment citizen, born here, he said, not in China, where, nevertheless, he said, he had two sons and four grandsons among them, my grandfather. Shipped to California by way of Angel Island at 10 years old with our family's dreams printed on a scrap of paper, fleeing the communists who made his real grandfather kneel on broken glass. Not the same communists my dream self meant to kill, but also the same. To live with a father he'd never met, an uncle grandfather who hated them both. Two years younger than his paper said, my gung-gung graduated at 16 and enlisted in that other so-called good war, though he was too late to be sent to kill the Japanese woman my teenage grandmother was mistaken for and spat on before she began wearing a button that told white people she was your friend, she was Chinese. So I tell myself it's just a dream when I wake with ash from someone else's life in my mouth again, that the only part that's real is that it isn't easy for any of us to love a country that doesn't always love us back. Thank you so much. My somewhat inappropriate compliment for that writing is that you do not write like somebody who's doing an MFA in poetry. And that is a compliment. Donald X. Fakarino was born in 1969 after years of not existing. He's a world-famous board game designer having made Dominion, among others. His previous writing credits include the funny paragraphs on all of the Dominion expansion boxes and in this neighborhood after the war in Colossus' home. Don't bet against yourself. Yeah? I know what you meant. You know what I meant. Oh, okay. So I have this thing from put mouth in correct spot. I have this thing from freedom to read. But I wanted to tell this personal anecdote first because I realized that it was on theme and that seemed amazing because, I don't know, I worried about that. Now tonight, no one was on theme. Like, but the last time it was all relentless prison. And I mean, not that no one was on theme tonight. So I better just get to this anecdote. So it's one of those, for me, it's a six degree of separation thing because it's like, you know, what do I know about prisons? And, you know, well, I'm 53 probably. I know something. I've known somebody who had some. And it turns out I did. So in the 90s, and we're all friends here. I'm just going to tell this story. In the 90s, I was a computer programmer at Fresenius, a East Bay company programming dialysis machines. And there was this guy who worked there named Scott. And he was a tech or something. He wasn't an engineer, but he helped out engineering in some fashion. Sometimes they interacted with him over that. And sometimes he would come by my office and we'd split a bag of microwave popcorn and talk about our lives, the movies or whatever. He had a 17 year old kid, and this was the early 90s. And the state of internet pornography was not what it is today. It was like ASCII. And so his kid rang up huge phone bills calling 900 numbers. And Scott would be like, oh, my kid calling these 900 numbers.  And there was one time I had a, you know, I know almost nothing about Scott really, right? It was just these conversations. There was one time when I had a kidney stone at work, my first kidney stone, and I lay on the floor of my office in agony. And the other programmer sheepishly went to our boss Wayne to say, maybe he's just kidding or maybe something's wrong. And quickly I was surrounded by nurses because it was a dialysis machine company. And they immediately thought it's a kidney stone. And Scott offered to drive me to the hospital, which was five minutes away. But the manager showed up and he said, no, we have to wait for an ambulance, curse his black heart.  So one day I noticed Scott hadn't showed up at work in a while. And I went and asked Wayne, what's the deal? It's got on the long vacation or what? And Wayne said, well, Scott's not coming back. And I can't tell you why. It's like super mysterious, right? What in the world? And I said, is he dead? And Wayne said, no, he's not dead, but he's not coming back. And I just can't tell you. So that was just a mystery for two or three days. And then Wayne called me to his office and said, OK, now he's dead. And so there was a, he had a roommate who was a co-worker. And so I was able to get the story of what had happened here. So Scott had, some night had gotten drunk and yelled at his kid about the 900 numbers. And his kid had been scared and called the cops and the cops showed up. And the kid said, no, just kidding. And the cops went away. But it happened again sometime later, some other night. You know, got drunk, yelled at his kid. Kid called the cops, the cops showed up. Kid said, just kidding. And the cop said, well, it's the second time we have to take him in.  But the police think maybe you're not a good parent. And so the initial report was that he had died of a brain aneurysm.  One day everything's fine. The next, you're in jail, dying of a brain aneurysm. But it turns out that brain aneurysm is just something you can write on the form that looks a lot prettier than what actually happened. And this wasn't exactly covered up and came out that in fact he'd been beaten to death. And somebody eventually found there was a newspaper story about it and someone showed it to me. And, you know, buried in this East Bay newspaper, there was a little article that said, you know, inmate in whatever East Bay prison dies after altercation with other inmate. A few more details about the other inmate. And note that this was being looked into. Nothing to worry about. And, you know, if you'd stumbled on this article at the time, you just would have thought, well, one bad man in prison killed another. I guess that's how it goes. So that's my personal anecdote that was totally on theme. Now I'm going to read this story. So this story will be much weirder and lighter. Is it light? It's not light at all. But I wrote a series of 20 stories, one for each song title on the guided by voice's album, B1000, and it ended up kind of having an overarching theme of people trapped being themselves. And this is this one, track six, mothered in hugs. Our hero has been imprisoned, trapped by his arch nemesis, the nefarious Dr. Brain. He awakens in a small prison cell deep within Dr. Brain's lair. The prison cell is not the only barrier to our hero's freedom. The cell is surrounded by a series of ever larger walls of Dr. Brain's design, by itself a potent obstacle designed to trap our hero here forever. But our hero is not to be beaten by the mere idea of prison. He immediately sets to work on his escape plan. He is our hero for good reason. He is mighty and clever and resourceful. He will take an ingenious prison to hold him. The first obstacle is the physical obstacle of the prison cell's walls. These are no match for our hero. He tears great chunks out of them with his bare hands and is soon through. But Dr. Brain is devious and is not only physical obstacles that our hero will face. The cell is surrounded by the second obstacle, an oozing wall of reality. The stuff is finely detailed, nitty gritty, cold harsh and everywhere. Its tangibility is undeniable and no mortal could hope to pass through it and survive. But our hero is not stopped so easily. He is imaginary and so reality is no obstacle to him. He slides through the wall with ease. Beyond it is the third obstacle, a jagged wall of statistics. Numbers piled on numbers in arbitrary relationships. Primes, fractions and repeating decimals approaching infinity. Even the sanest mathematician would be baffled by this wall, could not hope to thunder it. But our hero does not even pause. Like always he defies the odds and thus easily breaks through. The fourth obstacle is a vague wall of ethics. It is a gray area, an obscure jumble of causes and effects, justifications and white lies. It is unclear if breaking through this wall would be good or evil. The ramifications are impossible to work out. But our hero doesn't care. He is our hero. He is good by definition. He breaks through the wall with ease and once he has done so, it is clear that this was the right thing to do all along. He advances. The fifth obstacle is our hero himself. But our hero is not to be beaten by such obvious trickery. He merely steps aside and lets himself pass. The sixth obstacle is a pulsing wall of desire. And here at last our hero falters. For our hero wants to break through this wall, but this wanting is the stuff of the wall itself. And if our hero did not desire, then he would not act and would remain trapped. There is no escape, and even though our hero desperately wants to not want, he is still wanting. Our hero paces back and forth, trying to think of a way out. Dr. Brain, it appears, has defeated him at last. What our hero does not realize, however, is that this last obstacle is not part of Dr. Brain's plan. Our hero, so intent on escape, has found an obstacle that has always restrained him, though he has never noticed it before. Dr. Brain, too, is trapped by desire as are the rest of us. When our hero sees this, he thinks only that Dr. Brain's victory is complete, that Dr. Brain has finally conquered the world. Well, people, thank you. Thank you for being here. Another round of applause for all of our readers, please. Thank you, Sarah. Thank you, A.V. Folk. Thank you, Library. Our next show is going to be for the anthology Beat Not Beat, which I helped edit, but also Rich Ferguson, and will involve some pretty spectacular local readers. And that will be the second Thursday of next month, which will be also next year. So please feel free to join us then. Have a good evening.