Mega March Sale! 😍 25% off Digital Certs & DiplomasEnds in  : : :

Claim Your Discount!

Module 1: File Organisation

    Study Reminders
    Support

    Start off a new section of the course which is to do with how data is stored oncomputing systems. The data ultimately needs to be stored in some stable storage, right. So we needstorage that is not volatile. So we cannot be in memory of the computing systemsbecause computer systems may lose power and then you know lose data if it is thereany main memory. And the amount of data that typical databases hold with notanyway fit into main memory.So and at this at any point of time you may not need the whole of the data that is therein a database. You need to store some part of the database in the, in the main memory.We will see how exactly the transfer of data from the non-volatile storage to the mainmemory will take place. So disks, these hard disks have been the mainstay of thisnon-volatile storage for a number of years.So these are relatively inexpensive, you know storage medium. And they are in factalso random access addressable devices. So we will see how exactly they are randomaccess. Just like your memory is random access these are also random access devices.Random access devices to be contrasted with serial kind of devices, which are youknow which are actually not any longer being used like tapes.Tapes are not animax. They are to be you have to rotate the tape to a appropriate placebefore you can actually start using data from some segment of the tape. Now there areof course, advances that are taking place in storage technologies. So flash drives arealready you know are available and we can see that this the flash drive based externaldrive disk storage is also available, right.So but these things largely are we are currently using them for personal backups andthings like that. It is also possible to use them for database data storage. But as oftoday, though they do offer performance benefits, cost of these devices compared tothe disks is actually pretty high. So for I think for a few more definitely a few morenumber of years, we will continue to use this magnetic medium based disk, hard disksas the main storage for databases.Now actually one more thing that you need to know is that in large enterprises, asingle disks are not any more use actually. It is a collection of disks that are used andthe collection is organized in such a way that it will give you faster access to the dataand also the failures of this disks can be tolerated. The date of a. database has to beavailable to us at any point of time.Once we accept that we are going to manage this data, the data has to be availablepermanently for us. We cannot afford to lose data at any point of time. So but disksare electromagnetic devices. They do fail and so we have to take adequate precautionsto ensure that the data is available in spite of the failure of a single disk sometimes (())(4:32). So we will see how exactly we can address that issue a little later in themodule.Right now we will take up and understand a single disk how it is and then in general,we will abstract out the lot of details about the disks and then think of them as amedium that offers you a bunch of blocks, and then we will see how exactly we canorganize information on this blocks.Now another important question that comes up in the context of management, storagemanagement is that should the operating system on which the system is workingcannot we make use of the operating system services as and then you know get theoperating systems to kind of manage the disk space that the RDBMS actually needs.Now you would have studied how paging systems have you know are to beimplemented in the operating systems course, right.So how virtual memory organization is handled and when a processor demands aparticular data, how it is brought from the disk and is made available on any memorybuffers and how when a block or a page it is also called page right, a page is writtenby the process that is under consideration, how is it again transferred back to thememory all that, right. Now and it has its own policies right.So when to replace the so if there are you have seen a buffer of pages available for inthe main memory and if you want to bring in a new page from the disk and then youwant to vacate some frame in the memory where you can put the new block which ofthe frames to kind of empty. So that is an issue. So there are some specific policieswhere you will use and then transfer certain pages.Certain pages will be transferred automatically by the operating system back to thedisk right, least recently used and so on. You have studied some policies there in theoperating systems course. So the main point about this, from our perspective, from thedatabase management system perspective is that if you go by the root of the operatingsystem, then the operating system has the control about when to transfer a page that isthere on the main memory back to the disk, okay.Now the crucial question is, is this okay for us? And the answer for in from theperspective of a database management system is that, that state of affairs is actuallynot acceptable for us. DBMS, the database management system needs to really havevery tight control on when a page that it is being modified by the RDBMS system isactually transferred back to the disk.See once it reaches the disk, then it is in permanent storage, it is in permanent storage.So you recall that in the discussion for the database management systems, we madestatements about when you know the when the transactions run when the transactionsor logical, you know pieces of work that the server accepts to do on behalf of a enduser, like transferring money from one account to another account.And in reality, these operations consists of several sub operations, okay which need tobe performed on the database which is residing on the disk etc. So under thesecircumstances, you want to give a guarantee saying that this entire operation will bedone in an atomic manner. That means it will be done entirely or it will be deniedcompletely.You cannot you know have thousand rupees reduced from A’s account and notcredited to B’s account if you cannot stop the transaction somewhere in the middle,right. So it has to be done in the entirety. So this kind of guarantees are expected outof the RDBMS system when it does this transaction management.So under these circumstances, if you update something in the main memory and thepage that you have updated slips out of your control and goes to the disk and youactually do not want it to go to the disk, you are in trouble. So you really want toknow when exactly it is going and if it is going then you know then you should knowthat it is going and you should take appropriate measures for you know cancelling thatin case it is necessary.What if the transaction has to be aborted in between. For some reason, if thetransaction has to be aborted, then whatever partial work that it has done should notbe visible for the end users at all. It should not affect the database on the disk.Ultimately the database is on the disk or on the stable storage. So these are so we willappreciate these concerns when we actually talk about transaction management anderror recovery in the next module that we are going to study.But as of now we can assume that there are these issues related to transactionmanagement which will which are which has to be taken into consideration. Andthose things dictate that we actually need to have a very tight control on when pagesmove from the main memory to the disk from buffers to the disk. That is why most ofthe RDBMS is actually takes control of a certain amount of disk space.It completely takes off the whole amount of disk space from the operating system andmanages the disk space all by itself, okay. So this is the second option that I amtalking about, should RDBMS manage the disk space by itself? Yes, that is what ispreferred. Because we really need to have very tight control on when a buffer iswritten to the disk. We will appreciate this when we actually study the error recoverymechanisms in transaction management module.Okay, so now let us move on to looking at a single disk. And as I was telling you thatwe may actually not store you know data only in a single disk. We will see later onhow to handle multiple disks and what are the issues that are there in multiple disksand things like that. We will start studying a single disk. These are electromechanical devices. I am sure you would have used the external harddrive for backing up and things like that. And in addition to the USB flash drives, wealso sometimes if you want a largest array, you will actually buy an external harddrive, right. So if you place a hand on your external hard drive, you can see thevibrations as it is operating. So it is an electromechanical device.So it has, the structure inside is that there is a fixed you know some kind of a standkind of thing and then you have a rotating spindle. You have a rotating spindle. To therotating spindle, we have lots of platters that have attached, circular plates that are thatare permanently fixed or attached. So that when the spindle rotates the plates rotate.So these plates are also called platters. So there are multiple platters on the spindleand the spindle rotates at a speed of 7 to 10 to 12,000 rotations per minute. You cansee how fast it rotates. It keeps spinning. So they are called spinning disk. That is whywe are calling it spinning disk. They spin at very fast rate. The current spin rates aresomething like 12 to 15 RPM rotations per minute.Now while they okay, so let us first look at the physical structure. So we have thisrotating spinning spindle to which lots of platters are attached. And then we have ahead assembly which has several read/write heads, several read/write heads. Andthese read/write heads can actually be node mode so that they can read, they can readsome part of the disk, okay.And the disk material is magnetically coated so that you know you can electricallytransform that to score update. And then you can read it that read that you know andthen figure out that there is a bit there, a 0 or 1 something. So basically read of courseis 0 or 1. Now so the important thing to remember here is that these read/write head,has to be physically moved inside and outside so that it can read a circle like this.So if it is on this particular circle, it can read off bits from this particular circuit. Sowe have this concentrated circles. So each of these things are actually called a track.This is called a track. So when the read/write head is positioned on a particular track,then it can read off bits on the track. It has a sensor. Now how many tracks are thereyou will be very surprised that there are actually very densely packed track cell.Something like 10,000 per inch. So an inch is 2.54 centimeter size. So within 2.54centimeters we have 10,000 of these tracks. You can see how closely they arepositioned. And so each of these this read/write head has to position itself on exactlyone of those tracks. So it has to be very precisely controlled and you know steppermotors are used in order to position that on exactly one track.Now the tracks are optionally sometimes, you know partitioned into what are calledsectors. If it is there sectors are hardwired when the device is manufactured. But it isoptional to keep sectors. But the track is of course the most important thing. So andnow if it has sectors, either the sectors or the entire track itself is divided into blocks.A block is the basic unit of data transfer from the disk, okay.And these blocks are the ones that are given certain numbers. So there are a numberof blocks within each track and those blocks are numbered and you can actually put,you know ask for a particular block number and then that block will be read. Nowanother interesting thing here is that these things are all fixed to a particularmechanism. So they all move in unison, they move in unison okay.So it is not the case that this read/write head is on one track and this other read/writehead is on another track that is not possible. These are not independently movingread/write heads. They all move in unison, okay. And so at any point of time they areon the ith track say 100th track on all the platters. On all the platters they are on the100th track, okay. So now you can imagine that this 100th track on all the platters isin some sense forms a virtual cylinder.It is a cylinder, okay. So within this cylinder, we have so many surfaces. So each sowe are on 100th track, let us say. So 100th track on surface one. And then eachsurface actually has, each platter has two surfaces. The top surface and the bottomsurface. So both surfaces are actually used for storing data, okay. So that is why thisthis has two arrowheads. You can see that it can either read that or read this, okay?But the most interesting thing is you should remember that at any one point of time,we are only reading one track, one track of one surface. We are not simultaneouslyreading several tracks. So that means what so these, one of these, one of theseread/write heads, there is a read/write head for a per surface, right. So one of thesesurfaces one of these read/write heads will be electronically chosen.It will be electronically activated so that information from that particular read/writehead starts coming off, okay. You can switch between this track to this track in a jiffybecause it is electronic switching. It is a electronic switching. You just switch off this,this sensor and then switch on this sensor. Then you will start reading from thatsurface and then stop reading there and then start reading some other surface.So it is possible to do that. So that is why we will think of the 100th track that is thereon all surfaces as some kind of a virtual cylinder. And then we can actually read offseveral blocks from this virtual cylinder one after the other, okay. Once you are onsurface one, so how does the reading actually happen? This only moves this way in ahorizontal manner. So suppose it is on 100th track it will stay fixed there.Now your read/write head is fixed and the platter is spinning. So you basically, if youare looking for the 100th block under particular track, then you basically wait for the100th block to pass over you in this process of rotation. And once it starts processingover you, you will start picking up bits. That is how data transfer happens. So and theunit of data transfer is one block okay.And the block, the size of the block ranges from half a kilobyte to something like 8kilobytes, kilobytes. A kilobyte is 1024 bytes. So something like 512 bytes to 8kilobytes. That is the kind of typical size. So this is fixed. And this is set at theinitialization time for the other formatting of the other disk. And you can dynamicallychange it. Once a block is fixed, it will be permanent as long as using this other disk. Now let us look at what is an address of a block. So I told you it is a randomaccessible device. So it will, the disk controller actually accepts a block address. Ablock address consists of the surface number, the cylinder number, and the blocknumber. Surface number can also be thought of as a track number.You can also call it like that, but it is the cylinder that actually decides cylindernumber is the one that decides what I see in the track. So there are the 10,000 trackshere. So there are 10,000 virtual cylinders. So a cylinder number will be given andthen within the cylinder which track you are reading because it consists of as manytracks as there are surfaces here. So that is why you need a surface number.Surface number, cylinder number and within the track what is the block number thatyou are interested in. So then the data transfer will actually take place. So in order forthe data transfer to take place, what you need to do is to move the read/write head tothat particular cylinder. So the read/write head might be somewhere here, somewherehere and you are asking for the 100th thing.So the entire assembly has to be moved to that place, okay. This is what is called theseek time. You have to seek the appropriate cylinder. This is the one that actuallytakes, this is a physical movement based on stepper motor. So this is the one thatactually takes a longer time. So it is about 10 to 12 14 milliseconds for you to move toa appropriate track, right. And also of course, depends on where you are starting.If you starting at one place and then you know you have to pass over 500 tracks, thenit obviously takes longer time to go. And then you basically the switching the surfacenumber is actually used to switch the read/write head appropriately, okay. So youhave to, depending on the surface number, you set the read/write head from whereyou are reading.Then you basically then after moving to that particular cylinder, you wait for theappropriate block number to pass over the read/write head. And how long does it taketo pass over? It will take one rotation, maximum one rotation. So the one rotation isabout 3 to 4 milliseconds because it is making 10 to 12,000 rotations per minute persecond sorry RPM. RPM it is RP sorry rotations per minute.So from this RPM that is given, we can calculate how much is the time it takes to doone rotation. So one rotation time is what it can maximum take for you to get theblock under your read/write head sensor. So this is what is called rotational delay. Sothere is a seek time where you know you need to go to the appropriate track and thereis a rotational delay where you will wait for the appropriate block to come under aread/write head sensor.And once it comes there is a transfer time. But the transfer time is so little so you willactually ignore that. The transfer time is when you are transferring this 4000kilobytes. The block size let us say is 4000 kilobytes then you have to transfer this4096 bytes from the surface. That happens in a jiffy, so you really do not bother toomuch. This is compared to this, it will be very small.So the access time is modelled as seek time plus rotational delay. Now you will noticeone thing that now the blocks on a particular cylinder, there is a cylinder, right virtualcylinder, the blocks that are there on that cylinder in some sense, they are all closer toeach other from an access point of view, access point, from access time point of view.From an access time point of view, all these blobs that are sitting on a virtual cylinderor closer to each other compared to another set of blocks that are sitting on the othercylinders. The moment you switch from the 10th cylinder to the 50th cylinder theread/write head has to be moved, okay.So but as long as you are in the same on the same cylinder, and you are asking fordifferent blocks on the same cylinder, all that you are doing is if necessary, switch thesurface numbers, and then wait for the block to come under the read/write head. Youdo not have to move the read/write head. There is no seek time involved as long asyou are reading blocks from the same cylinder, you get that.So that is why we will say that the blocks on a particular cylinder are in some sensecloser to each other from a access time pointer. And so if you want if a file wants, say500 blocks, then you try to allocate all those 500 blocks on a particular cylinder. Donot put them on one surface. But if you put in a surface then the read/write head has tokeep moving like this on the surface. Instead what we will do is to put them on thecylinder.Because if you place them on the cylinder, then read/write head will go to thatcylinder first and then probably switch between the platters and then pick up. So thereare so many say let us say there are 20 some 10 platters, let us say. So you have 10tracks available. On those 10 tracks, there are so many blocks. So within those blocksyou try to put your file, okay. So from an abstract point of view, the blocks on thesame cylinder are kind of closer to each other.So and if you start ordering them on that particular you know access time point ofview then the cylinder i blocks are all close to each other. And after that this it is theclosest bunch of blocks are on cylinder i + 1 then in next cylinder and then and so onthe next cylinder. So when you have to pick up or you know ask for a consecutive insome sense a consecutive set of blocks then you will pick blocks from cylinder one,then cylinder two and cylinder three etc., okay.So from a abstracting the way all these it is actually such a amazing thing that on asmall about a one and a half, you know centimeters height we have so many plattersand then the platters are rotating at such high speeds and then certain read/write headgoes inside these platters and then the probability of this read/write head touching theplatter is you know very high actually.But then it actually is a fantastic piece of engineering that it actually works. And thenyou know and as it works, as it works, it actually generates small amount of dustparticles as it ages it starts generating like this purpose. The whole assembly isactually is hermetically sealed. The whole thing is hermetically sealed. So anythingfrom outside will not enter.But inside there can be certain particles that are getting generated and so slowly, theair quality changes so to say, okay. So there are I met a colleague in chemicalengineering, who spent a huge number of years studying the ecosystem inside thedisk. He was working in IBM. Soin these disks, how exactly the, you know as the disk gets used, how does the wholeinside things you know changes and things like that.So based on that they will be able to you know tell predictions about what is the meantime to failure, when is it likely to fail. So the failures in hard disks typically happenwhen the read/write head crashes onto the surface. Once the read/write head crashesonto the surface, then surface crackers will happen and the whole assembly will notwork properly. So we will look at the failure probabilities and other things little later.But right now let us understand that we can abstract out all these things and thenassume that this secondary storage is controlled by a disk controller. And what thedisk controller will do for you is to take a disk address, and then a buffer address inthe memory. And then you block transfer that block of data, which is about say 4kilobytes onto this buffer in about depending on where the read/write head right nowis, things like that.So it may take on the average 10 to 12 milliseconds for you to get back that 4kilobytes of data, okay. That is a lot of time ahead for us when the processors arerunning at 2.5 gigahertz or something like that. So the memory operations arehappening so fast milliseconds look like centuries. So that is the main one of the mainissues with the forward block. Now let us look at how the, so we will all be looking at file organizations. So beforewe do that, what do we place on files? It is the data records that we place on the files.So and what are the kinds of data records that are possible? They can be either fixedlength record types, where each field is a fixed length. Now you know the length ofthe field. It takes so many 25 bytes okay 25 bytes.This field takes 25 bytes, next field takes 30 bytes, next field takes 40 bytes, etc. Youknow the length of the fields. So such kind of thing if you have 10 fields in the record,then you know you can add up the field size as and then you will get the recordlength. So you know how much exactly for the record or you know takes so manynumber of bytes of data.So the advantage with this kind of records is that within the a file is nothing but asequence of bytes for us. A file is nothing but a sequence of these bytes basically,okay. So within that sequence of bytes you can actually precisely locate as to whereyour record starts, because you can calculate how many you know bytes to movebefore you can pick up your record. Because all records are of fixed length.So if each record is taking 100 bytes, then you know that the fifth record starts on (())(33:43) right. So you can use the record number, suppose you are given the recordnumber you can precisely calculate which byte it starts from and then start readingfrom that byte onwards. Now these number of records that are there and the length ofeach of these fields all this information has to be stored in the file header.A lot of information gets stored in file header. So when you are doing a filemanagement, you will first read the file header and then figure out the metainformation about how information is organized in the file and then start operatingthat file, okay. So as against this fixed length records, we have variable length recordfiles also. We are looking at basically just data records, we have fixed length recordsand variable length records.The variable length records they do arise because there can be some missing fieldsand there can be some repeating fields in a particular file. And there can be variablelength, you know a field is naturally modeled as a variable length value. So if this isthe case then we need to put some special separator symbols to indicate as to what arethe field boundaries, where one field has ended and where another field is starting.So if you imagine a record as a sequence of bytes, then if you do not have a fixedlength records, obviously fixed length fields obviously then when a field ends, youshould know when it ended. So you need some end markers for the fields. So youneed separator symbols to indicate when the field and then you also now requireseparate separator symbols to figure out when the record has ended, okay.So record and what are these separator symbols that are used to indicate the field youknow field separation and the record separation, that also has to be recorded in the fileheader. And how many number of records are there? What are the separator symbolsused etc. all this information thing has to be there in the file header, okay.