1CMU SCS15-826: Multimedia Databasesand Data MiningChristos FaloutsosCMUwww.cs.cmu.edu/~christos15-826 Copyright: C. Faloutsos (2005) 2CMU SCSOutlineGoal: ‘Find similar / interesting things’• Intro to DB• Indexing - similarity search• Data Mining15-826 Copyright: C. Faloutsos (2005) 3CMU SCSProblemGiven a large collection of (multimedia)records, find similar/interesting things, ie:• Allow fast, approximate queries, and• Find rules/patterns15-826 Copyright: C. Faloutsos (2005) 4CMU SCSSample queries• Similarity search– Find pairs of branches with similar salespatterns– find medical cases similar to Smith's– Find pairs of sensor series that move in sync– Find shapes like a spark-plug– (nn: ‘case based reasoning’)15-826 Copyright: C. Faloutsos (2005) 5CMU SCSSample queries –cont’d• Rule discovery– Clusters (of branches; of sensor data; ...)– Forecasting (total sales for next year?)– Outliers (eg., unexpected part failures; frauddetection)15-826 Copyright: C. Faloutsos (2005) 6CMU SCSOutlineGoal: ‘Find similar / interesting things’• Intro to DB• Indexing - similarity search• Data Mining215-826 Copyright: C. Faloutsos (2005) 7CMU SCSDetailed OutlineIntro to DB• Relational DBMS - what and why?– inserting, retrieving and summarizing data– views; security/privacy– (concurrency control and recovery)• Object-Relational DBMS - what and why?15-826 Copyright: C. Faloutsos (2005) 8CMU SCSWhat is the goal of rel. DBMSsElectronic record-keeping:Fast and convenient access to information.Eg.: students, taking classes, obtaining grades;• find my gpa• <and other ad-hoc queries>15-826 Copyright: C. Faloutsos (2005) 9CMU SCSWhy Databases?15-826 Copyright: C. Faloutsos (2005) 10CMU SCSWhy Databases?• Flexibility• data independence (can add new tables; newattributes)• data sharing/concurrency control• recovery15-826 Copyright: C. Faloutsos (2005) 11CMU SCSWhy NOT Databases?• Price• additional expertise (SQL/DBA)• over-kill for small data sets15-826 Copyright: C. Faloutsos (2005) 12CMU SCSMain vendors/productsCommercial• Oracle• IBM/DB2• MS SQL-server• Sybase• (MS Access,• ...)Open sourcePostgres (UCB)mySQL, mSQLminiBase (Wisc)Predator (Cornell)(www.acm.org/sigmod)315-826 Copyright: C. Faloutsos (2005) 13CMU SCSDetailed OutlineIntro to DB• Relational DBMS - what and why?– inserting, retrieving and summarizing data– views; security/privacy– (concurrency control and recovery)• Object-Relational DBMS - what and why?15-826 Copyright: C. Faloutsos (2005) 14CMU SCSHow do DBs work?%isql mydbsql>create table student ( ssn fixed; name char(20) );/mydbstudentssn name15-826 Copyright: C. Faloutsos (2005) 15CMU SCSHow do DBs work?sql>insert into studentvalues (123, “Smith”);sql>select * from student;studentssn name123 Smith15-826 Copyright: C. Faloutsos (2005) 16CMU SCSHow do DBs work?sql>create table takes ( ssn fixed, c-id char(5), grade fixed));takesssn c-id grade15-826 Copyright: C. Faloutsos (2005) 17CMU SCSHow do DBs work - cont’dMore than one tables - joinsEg., roster (names only) for 15-826studentssn nametakesssn c-id grade15-826 Copyright: C. Faloutsos (2005) 18CMU SCSHow do DBs work - cont’dsql> select name from student, takes where student.ssn = takes.ssn and takes.c-id = 15-826415-826 Copyright: C. Faloutsos (2005) 19CMU SCSSQL-DMLGeneral form:select a1, a2, … anfrom r1, r2, … rmwhere P[order by ….][group by …][having …]15-826 Copyright: C. Faloutsos (2005) 20CMU SCSAggregationFind ssn and GPA for each studentstudentssn nametakesssn c-id grade123 603 4123 412 3234 603 315-826 Copyright: C. Faloutsos (2005) 21CMU SCSAggregationsql> select ssn, grade from takes;takesssn c-id grade123 603 4123 412 3234 603 315-826 Copyright: C. Faloutsos (2005) 22CMU SCSAggregationsql> select ssn, avg(grade) from takes;WRONG15-826 Copyright: C. Faloutsos (2005) 23CMU SCSAggregationsql> select ssn, avg(grade) from takes group by ssn;takesssn c-id grade123 603 4123 412 3234 603 3ssnavg(grade)123 3.5234 315-826 Copyright: C. Faloutsos (2005) 24CMU SCSDetailed OutlineIntro to DB• Relational DBMS - what and why?– inserting, retrieving and summarizing data– views; security/privacy– (concurrency control and recovery)• Object-Relational DBMS - what and why?515-826 Copyright: C. Faloutsos (2005) 25CMU SCSViews - what and why?• suppose you ONLY want to see ssn andGPA (eg., in your data-warehouse)• suppose secy is only allowed to see GPAs,but not individual grades• -> VIEWS!15-826 Copyright: C. Faloutsos (2005) 26CMU SCSViewssql> create view fellowship as ( select ssn, avg(grade) from takes group by ssn);takesssn c-id grade123 603 4123 412 3234 603 3ssnavg(grade)123 3.5234 315-826 Copyright: C. Faloutsos (2005) 27CMU SCSViewsViews = ‘virtual tables’15-826 Copyright: C. Faloutsos (2005) 28CMU SCSViewssql> select * from fellowship;takesssn c-id grade123 603 4123 412 3234 603 3ssnavg(grade)123 3.5234 315-826 Copyright: C. Faloutsos (2005) 29CMU SCSViewssql> grant select on fellowship to secy;takesssn c-id grade123 603 4123 412 3234 603 3ssnavg(grade)123 3.5234 315-826 Copyright: C. Faloutsos (2005) 30CMU SCSDetailed OutlineIntro to DB• Relational DBMS - what and why?– inserting, retrieving and summarizing data– views; security/privacy– (concurrency control and recovery)• Object-Relational DBMS - what and why?615-826 Copyright: C. Faloutsos (2005) 31CMU SCSDetailed OutlineIntro to DB• Relational DBMS - what and why?– inserting, retrieving and summarizing data– views; security/privacy– (concurrency control and recovery)• Object-Relational DBMS - what and why?15-826 Copyright: C. Faloutsos (2005) 32CMU SCSWhy more than RDBMSs?• RDBMS: tuples, of numbers + strings• What apps need only those?15-826 Copyright: C. Faloutsos (2005) 33CMU SCSWhy more than RDBMSs?• RDBMS: tuples, of numbers + strings• What apps need only those?– Banks– Airlines– Retailer stores– ...• Q: Other apps, with more req’s?15-826 Copyright: C. Faloutsos (2005) 34CMU SCSWhy more than RDBMS’s• Q: Other apps, with more req’s?• A:– text– multimedia; financial apps/forecasting– Geographic Inf. Sys.– CAD/CAM– Network management15-826 Copyright: C. Faloutsos (2005) 35CMU SCSIdeally, we’d like to:• create a new data type (eg., ‘image’, ‘time-sequence’)• define functions on it (like