` 42
`Patl Basic Concent,
`right. However, since the DC manager and the DBMSareclear]
`y required 10 Work
`harmoniously together,they are sometimes regarded as equalpartn
`ers ina higher-toq
`cooperative venture called the database/data-communicationss
`ystem (DB/Dc Sys
`tem), in which the DBMSlooks after the database and the DC
`manager handles al
`messages to and from the DBMS,or moreaccurately to and from
`applications that use
`the DBMS.In this book, however, we shall have comparatively lit
`tle to Say about mes-
`sage-handling as such (it is a large subject in its own right), Secti
`ion 2.12 does briefly
`discuss the question of communication between distinct systems(
`L.e€., between distingy
`machines in a communications network), but thatis really a separ
`ate topic.
`
`2.10 Client/Server Architecture
`
`Chapter 2 An Architecture for a Database System
`
`43
`
`ms
`
`level support discussed in Sections 2.3-2.6, Thus, “server” in this contextis just
`another namefor the DBMS.
`Theclients are the variousapplications that run on top of the DBMS—both user-
`written applications and builtin applications, i.e., applications provided either by
`the vendor of the DBMSor by some “third-party” software vendor. Asfar as the
`server is concerned, of course, there is no difference between user-written and
`builtin applications—they all use the same interface to the server, namely the ex-
`ternal-level interface discussed in Section 2.3.
`Note: Certain special “utility” applications might constitute an exception to the
`foregoing. As mentionedin Section 2.5, such applications sometimes need to op-
`erate directly at the internal level of the system. Suchutilities are best regarded as
`integral components of the DBMS,rather than as applications in the usualsense.
`Utilities are discussed in more detail in the next section.
`
`Applications in turn can be divided into several reasonably well-defined catego-
`ties, as follows.
`
`SLEY
`
`T d
`
`ition,
`1993
`
`1993
`
`er,
`), 1992
`
`991-1994,
`
`991,
`1992
`
`989,
`
`1gs,
`
`989
`
`1s,
`33
`
`375, 1994
`
`ented and
`ns,
`
`994
`
`52, 1993
`
`1. First, user-written applications. These are basically regular application programs,
`written (typically) either in a conventional programming language such as C or
`COBOLorin someproprietary language such as FOCUS—thoughin both cases
`the language needsto be coupled somehowwith an appropriate data sublanguage,
`as explained in Section 2.3.
`ted and
`m==Theserveris the DBMSi
`:
`itself, It
`:
`2. Second, vendor-provided applications (often called tools). The overall purpose of
`ns,
`cussedin Section 2.8 atl
`Supports all of the basic DBMSfunctionsdis-
`1994
`suchtools is to assist in the processof creating and executing other applications !—
`f
`efiniti
`:
`‘
`rity, and so on.In particular. it Beis oul manipulation, data security and integ-
`i.¢., applications thatare tailored to some specific task (though the created applica-
`i Provides all of the external, conceptual, and internal
`tion mightnot look muchlike an application in the conventional sense; indeed, the
`whole pointof the tools is to allow users, especially end users, to create applica-
`tions without having to write conventional programs). For example, one of the
`vendor-provided tools will be a query language processor, whose purpose of
`courseis to allow endusersto issue ad hocqueries to the system. Each such query
`is basically nothing more than a small (or maybe not so small) tailored application
`thatis intended to perform somespecific application function.
`Vendor-providedtools in turn divide into a numberofdistinctclasses:
`
`End users
`
`Clients
`
`Server
`
`" query language processors
`= report writers
`" business graphics subsystems
`= spreadsheets
`
`Database
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 024
`
`

`

`
`
`,
`
`.
`
`oh
`
`We
`
`We
`
`i
`
`i
`
`:
`
`‘
`
`9
`
`can be s
`
`se
`
`See
`
`waythata sing]
`
`a
`
`Part! go.;
`ASIC Co
`"ents
`and so on. Details of such tools are beyond the scope of this book:
`remarkthat since (as stated above) the whole point of a database ¢
`» OWeVer, 5,
`portthecreation and execution ofapplications, the quality ofthe aae IS £0 sup.
`tools is, or should be, a major factor in “the database decision”(j ae fronte
`Le., th
`Mend
`choosing the right system for a given customer). In other words th ae PLOCessof
`e BMS Per Se
`is not the only factor that needst
`1
`0 be taken into account» NOT Even nececc.,:
`mostsignificantfactor.
`SSarily the
`feafly Geseee, a forward pointer. Since the overall System can
`two on differentmasts tt ee ae Gaels)ithe Possibility arises of i wi
`ineDisneytee ae erae potential exists for distributed Fi Ps
`somekindofebmnteanitedionenaveRReeected ietherie
`siitenanteS in the network. (In fact, Laeoy
`come to apply almost exclusi ons, mainly economic—that the term “client/s
`ee
`Clusively to the case where the server andclients Meitcedaon
`different machines Thi
`i
`iS. TIS usage is sloppy buty.
`i
`tributed Processing in moredetail in Secesk HeSS —*
`
`2.11 Utilities
`
`Utilities are progra
`i
`Pecuiicacd iF:aihee to help the DBA with various administration tasks. A
`System, and thus are efiseivaly=e Programsoperate at the external level of te
`might not even be Fit
`Ing more than Special-purpose
`ications:
`provided by the DBMS vendor, but Se. éy eeelon Re
`WEvVer, operate direct]
`a
`
`Here are some typi
`In practice:
`
`= Load routines, to cre
`:
`databasefiles
`
`ate the initial
`
`i
`Version ofthe database from one or more non-
`
`Transparent
`remote access
`
`to backup
`©, OF portions thereof,
`ery purposes and to 1
`:
`‘
`el
`course, the “reload utility” is basically aneae from such backup copies (of
`0
`
`Server machine
`
`
`
`
`
`
`
`Chapter 2 An Architecture for a Database System
`
`45
`
`The foregoing list represents just a small sample of the range of functions thatutilities
`typically provide. A wealth of other possibilities exist.
`
`2.12 Distributed Processing
`
`To repeat from Section 2.10, the term “distributed processing” means that distinct ma-
`chines can be connected together into a communications network such that a single data
`processing task can span several machinesin the network. (The term “parallel process-
`ing’is also sometimesused with essentially the same meaning, exceptthatthe distinct
`machinestend to be physically close together in a “parallel” system and need notbe so
`in a “distributed” system—e.g., they might be geographically dispersed in the latter
`case.) Communication between the various machinesis handled by somekindofnet-
`work management software—possibly an extension of the DC manager discussed in
`Section 2.9, possibly a separate software component.
`Manylevels or varieties of distributed processing are possible. As mentioned in
`Section 2.10, one simple case involves running the DBMSbackend (the server) on one
`machine and the application frontends(the clients) on another. Referto Fig. 2.5.
`As mentionedat the end of Section 2.10, “client/server”—althoughstrictly speak-
`
`Applications
`
`Client machine
`
`
`
`SLEY
`iT
`
`‘dition,
`1993
`
`’
`
`1993
`
`er,
`0, 1992
`
`991-1994,
`
`991,
`1992
`
`989,
`
`ngs,
`
`L989
`
`1S,
`33
`
`375, 1994
`
`ted and
`ms,
`1994
`
`lented and
`ms,
`
`994
`
`152, 1993
`
`993
`
`192
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 025
`
`

`

`ing a purelyarchitectural term—has cometo bevirtually Synonymouswith
`mentillustrated in Fig. 2.5, in which client and server run on different etac Tangee
`ines, lh.
`deed, there are many argumentsin favor of such a scheme:
`operate. It is quite commonfor a single enterprise—abank, for example—to operate
`many computers, such that the data for one portion of the enterprise is stored on one
`Thefirst is basically just the usual parallel processing ar
`computer andthat for another portion is stored on another. It is also quite commonfor
`many processors are now being applied to the overall task
`users on one computerto need at least occasionalaccess to data stored on another. To
`and client (application) processing are being donein parall
`pursue the banking example for a moment,it is very likely that users at one branch
`throughput should thus be improved.
`office will occasionally need accessto data stored at another. Note, therefore, that the
`Furthermore, the server machine mi
`client machines might havestoreddata of their own,and the server machine might have
`ght be a custom-built m
`achinethatis ta;
`“
`to the DBMSfunction (a
`database machine”), and mig
`tailored
`applicationsofits own.In general, therefore, each machinewill act as a server for some
`ht thus provide better
`DBMSperformance.
`users andaclientfor others (see Fig. 2.7); in other words, each machinewill support an
`991,
`entire database system (in the senseofearlier sections of this chapter).
`1992
`Thefinal pointis that a single client machine mightbe able to access several dif-
`
`Page 026
`
`SLEY
`
`T d
`
`ition,
`1993
`
`47
`
`Chapter 2 An Architecture for a Database System
`
`1993
`
`er,
`), 1992
`
`991-1994,
`
`989,
`
`1gs,
`
`989
`
`1S,
`
`3 3
`
`75, 1994
`
`ted and
`ns,
`1994
`
`ented and
`ns,
`
`994
`
`152, 1993
`
`, 9
`
`93
`
`1,
`
`92
`
`Clients
`
`Communication
`network
`
`<=
`
`Client
`Machines
`
`Communication
`network
`
`BuMent—name),
`and server (da,
`el. Response time
`
`that
`ase)
`and
`
`responses, and overall improved ease of use to the user
`Several different client machines mi
`ght be able (in fact, probably will be able
`ccess the same server machi
`es
`chine. Thus, a sin
`i
`several distinct client systems (see Fig. 2.6) peecanbise oes
`emits) Sedaka eeSR there is also the pointthat runningthecli
`machines matches the way Many enterprisesactually
`
`In addition to th
`n
`
`e
`
`i
`
`.
`
`) to
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 026
`
`

`

` 48
` LEY
`
`sos
`
`.
`
`;
`
`
`Chapter 2 An Architecture for a Database System
`49
`
`T d
`
`ition,
`1993
`
`1993
`
`er,
`|, 1992
`
`191-1994,
`
`191,
`1992
`
`Part | Basic Conce Rts
`ferent server machines(the converse ofthe caseillustrated in Fig. 2.6). This
`is desirable because, as mentioned above, enterprises do typically Breare “APabiliy
`g
`mannerthattheir total data collection is not stored on one single machine é IN Such
`spread across manydistinct machines, and applications will sometimes need ; ratherjg
`Ne
`to access data from more than one machine, Such access can basically b
`‘ili
`two ways:
`© Provided in
`1. A givenclientmight be able to access any numberofservers, but only one
`a1.
`,;
`(i.e., each individual database request must be directed toJust one ai eeu
`a system it is not possible, within a single request,
`to combine data ae po
`
`:
`
`.
`
`,
`
`Ul
`
`fr:
`
`{
`
`nal schemaand the conceptual schema,and (b) the conceptual schemaand theinternal
`schema.
`Users—i.e., end users and application programmers, both of whom operateatthe
`external level—interact with the data by means of a data sublanguage, which breaks
`down into at least two components, a data definition language (DDL) and a data
`manipulation language (DML). The data sublanguage is embeddedin a host lan-
`guage. Note: The dividing lines between the host language and the data sublanguage,
`and between the DDLand the DML,are primarily conceptual in nature; ideally they
`should be “transparentto the user.”
`Wealso took a closer look at the functions of the DBA and the DBMS. Among
`other things,
`the DBA is responsible for creating the internal schema (physical
`
`189,
`database design); creating the conceptual schema (logical or conceptual database
`design), by contrast, is the responsibility of the data administrator. And the DBMS
`is responsible (among other things) for implementing DDL and DMLrequests from
`the user. The DBMSis also responsible for providing some kind of data dictionary
`function.
`Database systemscan also be conveniently thought of as consisting of a server (the
`DBMSitself) and a set ofclients (the applications). Client and server can andoften will
`run on separate machines,thus providing one simple kind of distributed processing.
`In general, each server can serve manyclients, and each client can access many servers.
`If the system providestotal “transparency”—meaningthateach client can behaveasif
`it were dealing with a single server on a single machine,regardless of the actual phys-
`ical state of affairs—then we havea true distributed database system.
`
`
`
`; (i.e.,asiSly at
`
`
`
`2. Theclient might be able to access many servers simultaneou
`
`to make such systems
`Chapter 21.
`
`2.13 Summary
`
`point of view. First, we describ
`’
`eae
`database system into three
`levels, as follows: PARC architecture, which divides a
`
`ed
`
`Exercises
`
`2.1 Draw a diagram of the database system architecture presented in this chapter (the
`ANSI/SPARCarchitecture).
`2.2 Define the followingterms:
`
`backend
`client
`conceptual DDL,schema, view
`conceptual/internal mapping
`data definition language
`
`frontend
`host language
`load
`logical database design
`internal DDL, schema, view
`
`ented and
`1S,
`
`I94
`
`52, 1993
`
`193
`
`32
`
`475, 1994
`
`ed and
`1S,
`1994
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 027
`
`

`

`
`
`LEY
`
`T l
`
`ition,
`1993
`
`1993
`
`1,
`, 1992
`
`91-1994,
`
`91,
`992
`
`189,
`
`BS,
`
`989
`
`S;
`3
`
`75, 1994
`
`ed and
`1s,
`1994
`
`‘nted and
`LS,
`
`194
`
`32, 1993
`
`193
`
`2a
`
`51
`
`Chapter 2 An Architecture for a Database System
`ample involving the activities of a hypothetical Car Registration Authority. The three sets
`of contenders are (1) “entity-attribute-relationship” approaches, (2) “binary relationship”
`approaches, and (3) “interpreted predicate logic” approaches. Thereport also includes a
`discussion of the fundamental concepts underlying the notion of the conceptual schema,
`and offers someprinciples for implementation of a system that properly supports that no-
`tion. Heavy going in places, but an important document for anyone seriously interested in
`the conceptual level of the system.
`Data Dictionary Systems Working Party of the British Computer Society. Report. Joint
`Issue: Data Base (ACM SIGBDP newsletter) 9, No. 2; SIGMOD Record (ACM SIGMOD
`bulletin) 9, No. 4 (December 1977).
`Anexcellent description ofthe role of the data dictionary; includes a brief but good discus-
`sion of the conceptual schema.
`P, P. Uhrowczik. “Data Dictionary/Directories.” /BM Sys. J. 12, No. 4 (1973).
`A goodintroduction to the basic conceptsofa data dictionary system. An implementation
`is outlined based on IMS (IBM’s original Data Dictionary productin fact conformedto that
`broad outline).
`Paul Winsberg. Dictionary Standards: ANSI, ISO, and IBM; and Industry Views ofthe Dic-
`tionary Standards Muddle. Both in InfoDB 3, No. 4 (Winter 1988/89).
`Anexcellentintroduction to, and analysis of, the world ofdictionary standards—including,
`in particular, the ANSI Information Resource Dictionary Systems (IRDS)standard.
`William Kent. Data and Reality. Amsterdam, Netherlands: North-Holland/New York, NY:
`Elsevier Science (1978).
`A stimulating and thought-provoking discussion of the natureof information, andin partic-
`ular of the conceptual schema. The book can be regardedin large part as a compendium of
`real-world problemsthat(it is suggested) existing database formalisms—inparticular, for-
`malismsthat are based on conventionalrecord-like structures, which includes the relational
`approach—havedifficulty in dealing with. Recommended.
`
`Utence
`
`Part | Basic Conte §
`Explain the sequenceofsteps involved in retrieving a particular externalrec dOr Oce
`List the major functions performed by the DBMS.
`List the major functions performed by the DBA.
`Distinguish between the DBMSand a file managementsystem,
`Give some examples of vendor-provided frontendsortools.
`Give some examples of databaseutilities.
`Examineany database system that might be available to
`you. Try to mapthat systemto the
`ANSVUSPARCarchitecture as described in this chapter
`Doesit cleanly Support the three
`levels of the architecture? How are the mappings betw
`een levels defined? What do fe
`various DDLs(external, conceptual, internal) look like?
`Whatdata sublanguage(s) does ie
`system support? Whathost languages? Who performs
`the DBA function? Are there *
`secunty or integrity facilities? Is there a dictionary?
`What vendor-provided applications
`doesthe System support? Whatutilities? Is there a
`eparate DC manager? Arethere any
`distributed processing capabilities?
`:
`
`References and Bibliography
`
`2.1
`
`ee
`
`th
`
`:
`
`g
`
`i
`
`nces are b
`i
`1
`present chapter
`ANSI/X3/SPARCStudy Group on Data B
`OM SIGMOD bulletin) 7, No. 2 au eine
`gement Systems. /nterim Report. FDT
`Dionysios C. Tsichritzis and An
`Rarwie The ANSI/X3/SPARC DBMSFrame-
`work: Report of the Study G
`tems 3 (1978).
`er
`ase Management Systems.” InformationSys-
`~2.2] are the Interi m and Final R:
`respectively, of the so-
`dy G
`€ports,
`Management Systems (to give
`irreigenOLSS/SPARC Stud
`giveitit
`;
`i
`Planning and Requireme
`its full title) was established in late 1972 by the Standards
`nts Commi
`Standards Committee on Compute ule (SPARC)of ANSI/X3, the American National
`Ts and Information Processing. The objectives ofthe
`Study Group were
`7
`i
`3
`to determin
`ate for standardization, and
`© which areas, if any, ofdatabase technology were appropt'-
`to produce
`2
`area. In working to meet these objecti
`s the steasmmendations for action in each such
`were the only aspectofa datab.
`Ives, the Study Group took the position that interfaces
`lion, and accordingly defined a aere
`ue that could Possibly be suitable for standardiza-
`aSE syste
`that emphasizedtherole of such i
`ralized database system architecture, or framework.
`tion ofthat architecture and ofSee Final Report provides a Hetailed descrip-
`an earlier working doc
`42 identifiedi
`i
`i
`nt thatis still ofsome interest; in some AeBeaceaddi
`ume
`sage
`interfaces.
`5
`
`2.4
`
`2.9
`
`2.6
`
`2.7
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 028
`
`€
`

`

`
`
`3
`
`{An Introduction to
`Relational Databases
`
`3.1
`
`Introduction
`
`53
`
`Chapter 3 AnIntroduction to Relational Databases
`
`
` DNAME
`
` Marketing
`
`
`Development
`
`Research
`
`
`SALARY
`40K
`
`42K
`30K
`35K
`
`
`
`
`
`FIG. 3.1 The departments-and-employees database (sample values)
`
`The PROJECToperation extracts specified columns from a table.
`The JOIN operation joins together two tables on the basis of common values in a
`common column.
`
`Ofthe three examples, the only one that seems to need any further explanation is
`the JOIN example.First of all, observe that the two tables DEPT and EMPdoindeed
`have a commoncolumn, namely DEPT#, sothey can be joined together on the basis of
`
`
`
`91-1994,
`
`91,
`992
`
`189,
`
`175, 1994
`
`ed and
`1s,
`L994
`
`2nted and
`1s,
`
`I94
`
`52, 1993
`
`193
`
`3.2 Relational Systems
`Webegin by defini ng arelati
`for short) as a syst
`SS ae
`managementsystem (relational system
`fr
`:
`e
`€m In which,at a minimum:
`1. Thedatais Perceived by the USEras tab
`les (and nothing buttables); and
`. The operators at the
`’s
`di
`user’s di
`generate new tables from old ra
`ame for data retrieval—are operators that
`knownas RESTRICT) PROJECT
`Osea Include at least SELECT(also
`Thisdefinition, tho
`;
`ugh still y
`ery brief, is slightly more Specific than the one given
`;
`in Chapter |.
`samplerelational dat
`in Fig. 3.1. As you can 5:aaa startments-and-employees database, is shown
`
`lef,
`
`is
`
`sli
`
`r;
`
`BEIEM (RESTRICT):
`
`Result:
`
`DEPTs where BUDGET > 8M
`
`Marketing
`D1
`Development
`D2
`
`
`es
`
`10M
`12M
`
`PROJECT:
`
`Result:
`
`DEPT#
`
`BUDGET
`
`DEPTs over DEPT#, BUDGET
`
`JOIN:
`
`DEPTs and EMPs over DEPT#
`
`10M
`D1
`12M
`D2
`5M
`D3
`
`
`
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 029
`
`

`

`
`
`54
`
`.
`
`.
`
`‘
`
`Pls
`
`a
`
`CY
`
`rows
`
`rt] Basic Conce
`commonvalues in that column. Thatis, a given row from table DEp
`givenrow in table EMP—to produce a new, wider row—ifand only eh Will join tog
`question have a common DEPT#value. For example, the DEPT and EMP 0rows in
`
` DNAME
`BUDGET
`
`
`
`
`(column names shownforexplicitness) can bejoined together to produceth
`result roy
`
`Tve that the common (DEPT#)
`value appearsjust once, not twice
`"e, in each result row.
`Observe too thatsince no EMP
`row has a DEPT#value of D
`3 (i.e., no employeeis c
`urrently assigned to that depart-
`ment), no rn
`the
`in
`aaa ow for D3 appearsin the result, even thou
`gh there is a row for D3 in table
`
`Chapter 3 An Introduction to Relational Databases
`
`55
`
`Letus return to Fig. 3.1 fora moment. There are a few additional points to be made
`in connection with the sample database of that figure:
`
`51,
`992
`
`89,
`
`75, 1994
`
`‘d and
`Sy
`994
`
`First, note that the “relational system”definition requires only that the database be
`perceivedby the user as tables. Tables are the logical structure in a relational sys-
`tem, not the physical structure. At the physicallevel, in fact, the system is free to
`use any orall of the usual storage structures—sequential files, indexing, hashing,
`pointer chains, compression, etc.—provided only that it can mapthosestructures
`into tables at the logical level. Another way of saying the samethingis that tables
`represent an abstraction ofthe waythe data is physically stored—an abstraction in
`which numerous storage-level details, such as stored record placement,stored re-
`cord sequence, stored data encodings, stored record prefixes, stored access struc-
`tures such as indexes, and so forth, are all hidden fromthe user.
`Incidentally,
`the term “logical structure” in the foregoing paragraphis in-
`tended to encompass both the conceptual and external levels, in ANS/SPARC
`terms. The point is that—as explained in Chapter 2—the conceptual and external
`levels in a relational system will be relational, but the internal or physical level will
`not. In fact, relational theory as such has nothing to say about theinternal level at
`all; it is, to repeat, concerned with how the database looksto the user.
`i
`le. This is the
`relat
`tant. Basically, because the
`o) ieee ret
`Second,relational databaseslike that of Fig. 3.1 satisfy a very nice property: The
`entire information contentof the database is represented in one andonlyone way,
`input—a ng are all tables—sothe outputfrom one 0
`namely as explicit data values. This method ofrepresentation (as explicit values in
`eration can becomeinputto an-
`eee ‘nus It Is possible (for €xample)
`to take a
`;
`column positions in rowsin tables) is the only method available in a relational
`:
`ctions, etc., etc. In other words, it is
`possib
`Projection ofa join, or a join of two
`database.In particular, there are no pointers connecting one table to another. For
`eeesons In which the Operands thetacelecs
`le to write nested expressions—i.e.,
`example, there is a connection between the D1 row of table DEPT and the El row
`Just simple table names, This
`fact
`;
`a
`© represented by expressions, instead
`of table EMP, because employee EI works in department D1; but that connection
`-
`This factin ¢
`i
`eae
`nes.
`Thi
`urn has num
`Nieie (both aeschapterandin many aires+e—
`is represented, not by a pointer, but by the appearance of the value DI in the
`DEPT#position of the EMP rowfor E1. In nonrelational systems, by contrast, such
`
`ythatthe output from each operation is anothertable,it is very
`informationis typically represented by somekind ofpointer that is explicitly visi-
`ble to the user.
`Note: When weSay there are no pointers in a relational database, we do not
`mean that there cannot be pointers at the physical level—on the contrary, there
`certainly can be pointers at that level, and indeed there certainly will be. But as
`already explained,all such physical storage details are concealed from the user in
`a relational system.
`Finally, note that al! data values are atomic (or sealar). That is, at every row-and-
`column positionin every table there is always exactly onedata value, never a group of
`
` 1-1994,
`
`i
`
`We Sa
`
`at |
`
`I
`
`ee
`
`94
`
`2, LOGS
`
`nted and
`Sy
`
`93
`
`2 E
`
`T example
`r example, suppose weare trying to compute a
`‘
`3
`» aS Soon as
`eo
`can immediately apply the restrict
`4 g1Ven row ofthe JOin is constructed,
`the system
`10n to that row to see whetherit Beloneein the final
`the output from the join
`m;
`Join might
`at all. As a general rule,j onNetexist as a fully materialized tablein its ownright
`ate tein their enuirety, forobvious ee etaagize sntermest
`
`:
`
`:
`
`:
`
`“eXist
`
`ac.
`
`System tri
`
`ae:
`
`i
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 030
`
`€
`

`

`
`
`Part | BasicCK
`
`Neen
`
`Chapter 3 AnIntroduction to Relational Databases
`
`57
`
`SLEY
`iT
`
`‘dition,
`1993
`
`Nhat j¢
`Nation
`
`;
`
`m
`
`Since that time, those ideas—by now almost universally accepted—have had a
`wide-ranging influence on just about every aspect of database technology, and in-
`deed on otherfields as well, such as the fields of artificial intelligence, natural
`language processing, and hardware system design.
`
`Now, the relational model as originally formulated by Codd very deliberately made
`use of certain terms, such as the term “relation” itself, that were not familiar in IT
`circles at that time, even though the concepts in some cases were. The trouble was,
`many of the more familiar terms were very fuzzy—they lacked the precision necessary
`to a formal theory of the kind that Codd was proposing.
`
`mu
`
`Example: Consider the term “record.” At different times that single term can mean
`either a record occurrence or a record type; a COBOL-style record (which allows
`repeating groups)or a flar record (which does not); a /ogical record or a physical
`record; a stored record or a virtual record; and perhapsother things as well.
`
`1993
`
`rer,
`0, 1992
`
`991-1994,
`
`991,
`1992
`
`989,
`
`ngs,
`
`ns,
`83
`
`1375, 1994
`
`ited and
`ms,
`, L994
`
`instead of
`
`
`
` 56
`
`(see reference [4.,a7 Chee Model ofData
`
`:
`Column EMP#in the second version of this table is an exa
`usually called a repeating group.A repeating groupis a column pect
`of columns, that contains several data values in each row (diffi hee
`values in different rows, in general). Relationa
`ee
`| databases do not allow + et
`groups; the second version ofthe table above w
`FeDeatin D
`ould not be permitted in a relational
`System. (The reasonforthis apparentlimitatio
`N is basically simplicity, See Chap.
`ters 4 and 19 for further discussion.)
`We Close this section by remarkin
`at the beginning ofthe section is onl
`[3.1], and is essentially the definitio
`The formal relational model therefore does not use the term “record” at all; instead,
`it uses the term “tuple” (short for “‘n-tuple”), which was givenaprecise definition by
`1989
`Codd whenhefirst introducedit. We do notgive that definition here; for present pur-
`poses, it is sufficient to say that the term “tuple” corresponds approximately to the
`notion of a flat record instance (just as the term “relation” corresponds approximately
`to the notion of a table). When we moveon(in Part IT) to study the more formal aspects
`of relational systems, we will make use of the formal terminology, but in this chapter
`weare nottrying to be very formal, and we will mostly stick to terms such as “table,”
`“Tow,” and “column”that are reasonably familiar.
`
`iented and
`ms,
`
`S:
`
`1994
`
`652, 1993
`
`8,
`1993
`
`in,
`
`5 9
`
`92
`
`ts it is usual to treat the term
`Ss af
`:
`”
`é
`”
`1
`1
`es
`==
`Telation” and “table” as if
`eed,the term “table” is used much morefrequently than the
`
`3.4 The Relational Model
`
`So whatexactlyis the relational model? A good wayto characterizeit is as follows: The
`relational model is a way of looking at data—thatis, it is a prescription for a way of
`representing data (namely, by meansoftables), and a prescription for a way of manip-
`ulating such a representation (namely, by means of operators such as JOIN). More pre-
`cisely, the relational modelis concerned withthree aspectsof data: data structure, data
`integrity, and data manipulation. The structural and manipulative aspects haveal-
`ready beenillustrated; to illustrate the integrity aspect (very superficially, please note!),
`we consider the departments-and-employeesdatabase of Fig. 3.1 once again. In all like-
`lihood, that database would be subject to numerous integrity rules; for example, em-
`ployee salaries might have to be in the range 25K to 95K, department budgets might
`
`they were synon
`
`7
`mous; ind
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 031
`
`

`

`Answers to Selected Exercises
`
`
`592
`
`.
`
`5
`
`y l DiStributed Dat b
`ie
`aDase and
`Ch ot/S
`S
`erver ystems
`
`,;
`
`;
`
`k.
`
`(b)
`
`true. (c) true. (d) unk (note t
`
`he counterintuitive nature of
`of
`
`th;
`this on
`
`a(©)false
`re (falsetiesthatIS_UNKneverreturnsunk).(g)false.(h)true.
`202 (kn(re.fle(an(a.
`203 Because “TSUNK(x)” returns pee 17 an he y 1
`Xi
`Yin
`re aus unk (forarbitr,
`arbitraryy), and it returnsfalse ifand only if “x =y OR x#y”
`returns true (foroeand
`trary
`nonUNKy).
`20.4 Because(e.g.) “MAYBE_RESTRICTRWHEREp”
`is the Sue as “RWHEREMAYBE()Fs
`20.5 The four monadic operators can be defined as follows(A is the single operand):
`.
`
`A N
`
`OT (A)
`.
`A OR NOT(A)
`21.1 Introduction
`A AND NOT(A)
`
`The 16dyadicoperatorscanbedefined as follows(A andBarethe twoOperands): Wetouchedonthe subjectofdistributeddatabasesattheendofChaptertereee
`
`
`
`
`A OR NOT(A) OR B OR NOT(B)
`said that “. .
`. full support for distributed database implies that a sing]
`licati
`A AND NOT(A) AND B AND NOT(B)
`.
`gle application
`:
`should be able to operate transparently on data thatis spread across a variety ofdiffer-
`NOT (A)
`entdatabases, managed by a variety ofdifferent DBMSs, Tunning ona variety ofdiffer-
`_
`ent machines, supported by a variety of different operating systems, and connected
`NOT(B)
`together by a variety ofdifferent communication networks—wherethe term transpar-
`: ee
`entlymeans that the application operates froma logical pointofviewasifthedatawere
`A OR NOT(B)
`allmanagedby a single DBMSrunning ona single machine.” Weare now ina position
`A AND NOT(B)
`to examine these ideas in somedetail. To be specific, in this chapter we will explain
`NOT(A) OR B
`exactly what a distributed databaseis, whydistributed databases are important, and
`a z wes x
`what someofthe unsolved technical problemsarein thedistributed databasefield.
`NOT(A) AND NOT(B)
`Chapter 2 also briefly discussedclient/server systems, which can be regarded as a
`(NOT(A) OR B) AND (NOT(B) OR a)
`Particularly simple special case of distributed systems in general. We will consider
`(NOT(A) AND B) OR (NOT(B) AND a)
`chent/server systems specifically in Section 21.6.
`y,
`g
`:
`Incidentally, to see that we do not need both AND and OR,observethat, e.g.,
`The overall plan ofthe chapteris explainedatthe endofthe nextsection.
`A OR B = NOT(NOT(A) AND NOT(B))
`‘
`ee
`aan
`20.6 See the annotation to refere
`20
`21.2 SomePreliminaries
`20
`tee Sena aae
`7 (c). For further discussion, see reference [20.8].
`
`20.8 Webriefly describetheTepresentation usedin IBM's DB2product. In DB2,agu 3 Webegin with a working definition (necessarilyalittle imprecise at this stage):
`7
`:
`oa
`a
`i
`;
`that
`:
`:
`can acceptnulls is physically represented in the stored database by two columns,
`fie
`am.
`columnitselfand a hidden indicatorcolumn,onebyte wide,that is stored as aprefixoa
`\ distributed database system consistsofa collection ofsites, connected together
`
`i finedasfoll A and B ; : ee
`
`
`
`
`
`___
`
`\
`
`i
`
`ad
`
`3
`
`Meta Platforms, Inc.
`Exhibit 1024
`Page 032
`
`

`

`
`
`PartV F
`
`NTRMer Topic
`(in effect, it is the logical unionofthosereal databaseS), RiQ,
`a number ofdistinct sites
`‘Jac
`:
`le.
`ye.
`21.1 provides an examp
`Roeeay:
`an
`a database systemsite in its o
`;
`Notethat, to repeat, each site Is
`y
`Wn right. Ing
`ther
`words, each site has its own local “real” Dees is a local users,its Own|
`Ocal
`DBMSand transaction management software (including its own local locking, loggin
`recoveryeles software), and its own local data SUTIN manager (DC man,
`ager). In particular, a given user can perform operations on dataat that user’s own local
`site exactlyas ifthat site did not participate in the distributed systemat all (at least, this
`is an objective). The distributed database system can thus be regarded as a king of
`partnership among the individual local DBMSs at the individual localsites; a new
`software componentat each site—logically an extension of the local DBMS—provides
`the necessary partnership functions, and it is the combination of this new component
`
`New York
`
`eendon
`
` ; pistributed Database and Client/Server Systems
`595
`chapter2
`“ah
`the existing DBMSthat constitutes what
`j
`togetheraieement system (sometimes RicSpee inedistributed
`gata
`ientally,
`it
`is common to assume that the com
`:
`Ponentsites are physically
`eee ossibly in fact geographically dispersed also,
`as suggested by Fig. 2],
`trot actually it 1s sufficient that they be dispersed logically. Two “sites”
`mi
`atcoexist on the same physical machine (especially during the period ae ree
`i .qstallation and testing). Indeed, the emphasis in distributed systems hisShi
`or the past few years: Whereas mostof the original research tended to assume geo-
`ov ie distribution, most of the early commercialinstallations have involved lo :
`jistribution instead, with (e.g.) several “sites” all in the same building and came
`peter by means of a local area network (LAN). From the database point of view,
`however, it makeslittle difference—essentially the sametechnicalproblemsstill have
`ibe solved—and so wecan reasonably regard Fig. 21.1 as representing a typical sys-
`tem for the purposes of this chapter.
`Note: In orderto simplify the exposition, we will assumeuntil further notice that
`the system is homogeneous, in the sense th