Modeling -------- What is modeling ? - reasoning about the data - From Wikipedia: Data Model Theory: 1. "structural part" - collection of data structures that represent the data 2. "integrity part" - constraints on the data to ensure integrity 3. "manipulation part" - collection of operators to manipulate the data Given: A set of application domains Data representation needs, e.g. query, integrity, manipulation Find A representation language A set of building-blocks Objectives Expressiveness Convenience, i.e. reduce semantic gap (given, find) Constraints Usability Performance - needed because if you didn't know anything about the data, you won't be able to write general purpose programs - how do you write code if you didn't know that each account is associated with a customer etc. - e.g. imagine a set of "resumes" as available on the webpages. Not possible to write any code that does comparison. Each resume is written differently. One calls it "education", another one calls it "schools". - leads to informed decision making - Strategies based on corporate-wide information Example: Customer relationship management - Operational efficiencies Inter/Intra-organization communication Example: Supply chain management Reduced cost of collaboration Scientific problem solving - Genome sequencing - Lack of common data model leads to Makes data sharing difficult Redundant and inconsistent data across applications Hampers informed decision making, collaborations, communication, ... - the history of modeling can be seen as an attempt to capture the structure in the data. - pre-relational model, people wanted to structure the data and then write code on it. - network model did an okay job at it. But writing programs was tough, navigational only. - especially after relational model, all attempts are to increase the power of it. e.g. relational model won't be able to model the above "resumes" correctly. so use XML instead etc. Why is this problem important? Common data model yields benefits Why is this problem hard ? Changes Set of applications evolve Business data processing (1960s) - COBOL Scientific Apps, Software development (1980s) - Objects Web (1990s) - XML Sensor networks (2000s) Natural language processing/text analytics (late 00s) Platforms evolve Computer Hardware, Languages, Operating Systems Storage: Tapes -> Disks (1960s) -> RAID (1990s) -> SAN ->.. CPUs: Mainframe -> Mini -> Desktops -> Multi-core CPUs (2000s) A nice DBMS History: http://www.cs.berkeley.edu/~brewer/cs262/SystemR.html We use the following data: Supplier(sno, sname, scity, sstate) Part(pno, pname, psize, pcolor) Supply(sno, pno, qty, price) 1. Hierarchical (late 1960's and 1970's) - IMS: IBM designed IMS with Rockwell and Caterpillar starting in 1966 for the Apollo program. IMS's challenge was to inventory the very large Bill of Materials for the Saturn V moon rocket and Apollo space vehicle. Still going strong -- Why ? "Legacy data". Estimated to $1 Billion business for IBM. From wikipedia: In fact, much of the world's banking industry relies on IMS, including the U.S. Federal Reserve. For example, chances are that withdrawing money from an automated teller machine (ATM) will trigger an IMS transaction. - What is it ? Hierarchical arrangement of records; each record has fields and must have a "key". The tree-edges denote "association" between data types. Had a "data description" that the data must conform to ("schema"). Here are two ways to do the example data: Supplier(...) ---> Part(...) Part(...) ---> Supplier(...) Problems: (1) Repetition of information -- can lead to anomalies. (2) Inability to represent information -- can't represent a "part" without a "supplier". Language: DL/1 - Allows retrieving the segments from any programming language (specifically, COBOL) Each record has a HKS (hierarchical sequence key) - concatenating the keys from the root. Defines a natural order (pre-order ?) which is used for "get_next()" Find all red parts suplied by Supplier 16: Get unique Supplier (sno = 16) Until failure do Get next within parent (color = red) Endodo Another way is to eliminate the supplier condition. Inefficient. Programmer has to decide.o "Access Methods": For root nodes: (1) sequentially -- won't support inserts - must make changes separately and write new database (2) using a B-Tree??, (3) using a Hash Index -- won't support get_next(), since can't return in the HKS order. For dependend nodes: (1) physical sequentially, (2) various forms of pointers Has many performance optimizations, but the programs are very much tied to the physical organization. "Physical data independence" --> Ability to continue running the programs regardless of what tuning is performed at the physical level. Supports a certain level of "logical independence", because DL/1 is defined on a logical database. So exclude the data that does not conform. Note that this is wierd in that the physical organization assumed by the program must still be a subset of the actual organization. But this allows support for adding new data types etc. Support for handling the above problem. Supplier(...) --> Supply(pno, qty, price) Part(...) Two different databases. DL/1 sees them as "fused". Suppler(...) --> Supply(pno, qty, price) || Part(pno, pname, psize, pcolor) Can access them hierarchically. Lessons: 1. Physical/logical data independence are highly desirable. 2. Tree structured data models are very restrictive. 3. Challenge to provide logical reorganizations of tree structured data 4. Navigational --> requires programmer to optimize 2. Network Data Model / CODASYL (1970's) Could have a "network" structure instead of a hierarchy Supplier() Part() supplies \ / supplied_by V V Supply(qty, price) Must have at least one entry point (no parents) Each named arc is called a "set" 1-to-n relationship (each supplier has many supplies) Okay to have "part" not associated with a "supplier" No support for "ternary" relationships (like bride, groom, and minister perform a ceremony) Program: Find supplier(sno = 16) Until no-more { Find next Supply record in Supplies Find owner Part record in Supplied_By Get current record } CODASYL proposal suggested hashing teh records in each "entry points" No physical data independence. No logical data independence either. Much more complex. Programmer navigates in a multi-dimensional hyperspace. Must keep track of: The last record touched by the application The last record of each record type touched The last record of each set type touched The DML commands update these "currency indicators" Can imagine programming as moving around in the hyperspace using these and locating the data of interest. Charlie Bachmann called this "navigating in hyperspace" in his Turin Award Lecture, 1973. Recovery etc was more complex; can't reason about "Supply" without supplier and part etc. Lessons: 5. NEtworks more flexible than hierarchies but more complex 6. Loading and recovering networks is more complex than hierarchies 3. Relational (1970's and 1980's) Ted Codd, IBM, 1970 "IMS programmers spending too much time programming" Proposal: Store the data in a simple data structure (table) Access it through a high level set-at-a-time DML No need for a physical storage proposal. No issues with logical data independence - data structure is simple. No issues with physical data independence - access is using a high-level language. The underlying file can be sorted, hashed or whatever Can easily represent almost anything - including the ternary relationship. Ceremony(bride-id, groom-id, minister-id, when, where etc). Great debate: Ted Codd: - Nothing as complex as CODASYL can possibly be a good idea - unacceptable data independence - record-at-a-time too hard to optimize - CODASYL not flexible enough to represnt common situations Charlie Bachmann: - nobody can understand this "relational calculus" etc - impossible to implement relational efficiently - CODASYL can represent tables, so whats the big deal ? Best quote by Don Chamberlin (co-inventor of SQL): "He (Codd) gave a seminar and a lot of us went to listen to him. This was as I say a revelation for me because Codd had a bunch of queries that were fairly complicated queries and since I'd been studying CODASYL, I could imagine how those queries would have been represented in CODASYL by programs that were five pages long that would navigate through this labyrinth of pointers and stuff. Codd would sort of write them down as one-liners. These would be queries like, "Find the employees who earn more than their managers." [laughter] He just whacked them out and you could sort of read them, and they weren't complicated at all, and I said, "Wow." This was kind of a conversion experience for me, that I understood what the relational thing was about after that.â" Both camps changed their position somewhat - especially with the development of SQL (more friendly to non-mathematicians) and efficient relational systems. INGRES, and System R (at the same time) Pioneered many of the ideas Oracle in 1979 IBM went the way of relational model, and that was it. Vast business power. Essentially resulted in SQL (fast processing --> so the committee used the System R documentation, and didn't do many changes) QUEL was actually better. Also, success of VAX Major DBMS's like IDMS were not portable. Relational systems were. Big reason. IBM tried to put a relational frontend on top of IMS - didn't succeed Lessons: 7. Set-at-a-time languages good --> provide logical data independence 8. Logical data ind. easier with simpler data models 9. Technical debates many times settled by the "elephants" of the marketplace. 10. Query optimizers very very successful. 4. ER Model (late 1970's, 1980's) Peter Chen Entities - Things that exist by themselves Relationships - Associations between entities Graphical representation -- easier to think about than relational model Never gained acceptance as the underlying model. - No query language. - Very easy to convert to relational model. The design model - Relational model couldn't answer the question of how to get the initial set of tables. - Functional dependencies and normal forms hard for users to understand. - Specially MVDs etc. - Relational model can also be thought to be too restrictive in many cases. Lesson: 11. Simplicity usually wins. FDs too hard to understand. 5. R++ Era Motivation: Relational model is not enough. For CAD, text management, time, computer graphics etc etc.. Gem by Zaniolo: 1. set-valued attributes: e.g. colors for a Part 2. Aggregations: Supply (PT, SR, qty, price) PT - is a tuple in Part table. Implemented using pointers. select Supply.SR.sno From Supply Where Supply.PT.pcolor = "red" "cascaded-dot" notation (path expressions) 3. generalization Notion of inheritance - IsA in the E/R model Problems with these models: Better querying interfaces, but little performance improvement In fact, "foreign keys" are same as "tuple pointers" One could argue that these made the model less declarative Lesson: 12. Unless there is a big performance or functionality advantages, new constructs will go nowhere. 6. The semantic data models: Relational is semantically impoverished. SDM Model by Hammer and McLeod: Notion of classes Allowed multiple inheritance etc etc Very complex model, and generally paper proposals. 7. OO Era: Impedance mismatch -- people wanted to write in their favorite programming language. Had to do it by defining the variables in the program, and loading it using SQL. Would be nicer if we had a "persistent programming language" instead. E.g. in Rigel: For P in Part where P.pno = 16 { Code_to_manipulate_part } Problems: - Requires compiler to be extended with DBMS-oriented functionality - Must be done for each PL Many commercial and research systems, based usually on C++. Geared toward engineering data bases. e.g. Engineering CAD. "Swizzling" of pointers required - interesting technology there Performance goals because of CAD: 1. no need for a declarative language; just need to reference large disk-based objects in C++ 2. no need for transaction management; some sort of versioning system would be nice. 3. Run-time system had to be competitive with conventional C++. The last bullet very important: Consider persistent int i; i = i + 1; Shouldn't require a process switch, so must cache objects, lazily write them back etc... The DBMS must run in the same address space as the application. Many innovative architectures for supporting these things Niche Market - some have started reinventing as XML databases (e.g. Object Design) Why ? 1. Absence of leverage - Not providing a major service so customers weren't willing to pay much. 2. No standards. 3. Relink the world - when something changed, everything had to relinked. Low physical/logical data independence. 4. Too many programming languages. What if you don't want to use C++ ? O2: Supported OQL - declarative. So what they had was a "semantic data model" with a declarative language. French company - couldn't get a foothold in USA. Lessons; 13. Packages won't seel unless users are in "major pain" 14. Persistent languages won't go anywhere without support from PL community. 8. Object-Relational: Out of INGRES. Wanted support for GIS applications.: Intersections(I-id, long, lat, other-data) Find all intersections within a bounding rectangle: Select I-id From intersections where X0 < long < X1 and Y0 < lat < Y1 B+-Trees wouldn't have supported this (they are one-dimensional) Moreover, writing queries is painful and not-intuitive So should be able to add new data types. OR proposal added: user-defined data types user-defined operators user-defined functions user-defined access methods Major prototype: Postgres E.g. Intersections(I-id, point, other-data) Must have SQL operators: Select I-id From Intersections Where point !! "X0, X1, Y0, Y1" Essentially the same motivations as ADTs, Classes etc. Postgres figured out mechanisms to add this type of extensibility, be able to use R-Trees etc. We will cover this later. Stored Procedures - Sybase in 1980's Long transactions require too many round trips between the DB and the client. Instead define a stored procedure: Define cash_check(X, Y, Z) Begin transaction ... End transaction Application just says: Execute cash_check($100, 79246, 15) Requires a proprietary small language to handle error messages and perform required control flow etc. Postgres UDTs and UDFs generalized this notion - allowed using any programming language. Later benchmarking efforts show the main contribution to be stored procedures and user-defined access methods. Postgres --> Illustra --> bought by Informix Better transaction support etc. Fairly successful for GIS and other content-rich applications. Not so much for business data processing. UDFs are becoming more useful --> e.g. to implement data mining algorithms. Yet no standard (many support Java, MS doesn't) Lessons: 14. Major benefits: putting code in the database and user-defined access methods. 15. Widespread adoption either requires standards or push by an "elephant" 9. Semi-structured Data Started with LORE Data that is not fully structured. Main ideas: - "schema last": Self-describing data using "tags". Data doesn't need a schema to be understood. Not true in practice. Semantic heterogeneity still exists. (e.g. "salary" in USA vs "wage" in India) Consider four categories of applications: 1. Ones with rigidly structured data Enterprise data. Must conform to schema, or the business process are in trouble. Should be "schema first" 2. Ones with rigidly structured data with some text fields Personnel files with "reviews". Still rigidly structured. Should be "schema first" 3. Ones with semi-structured data "Wanted ads" and "Resumes". Some structure, but the instances vary quite a bit in the exact data they contain. 4. Ones with text "schema not at all" - Can't do anything. Information Retrieval community. Hard to find good examples of Number 3. Even resumes are being very structured these days (e.g. Monster.com) XML Data Model Does have a schema language DTD or XMLSchema Were intended to deal with the structure of formatted documents - Document Markup Languages Issues for use as a data model 1. Can be hierarchical, as in IMS 2. Can have links - like CODASYL, Gem or SDM 3. Can have set-based attributes 4. Can inherit from other records Very hard to optimize these things. E.g. XMLSchema has "union" data types - Hard to build indexes on them. Must use different plans for different union types (if you want to use indexes). Union types were never seriously considered for inclusion in databases for that reason. Languages: XPath, XSLT, XQuery (very complex) Okay to use as the wire format - text data is easier to pass around. But will be converted to and from relational at both ends. Easy to implement a subset of XQuery using UDFs etc. Lessons: 16. Schema-last is probably niche market 17. XQuery pretty much OR SQL with a different syntax 18. XML will not solve semantic heterogeneity