Introduction to IR Systems: Supporting Boolean Text SearchInformation RetrievalIR vs. DBMSIR’s “Bag of Words” ModelBoolean Text SearchText “Indexes”A Simple Relational Text IndexAn Inverted FileHandling Boolean LogicBoolean Search in SQLSlide 11Computing RelevanceFancier: Phrases and “Near”Updates and Text SearchDBMS vs. Search Engine ArchitectureIR vs. DBMS RevisitedIR vs. DBMS, Contd.Lots More in IR …Database Management Systems, R. Ramakrishnan 1Introduction to IR Systems: Supporting Boolean Text SearchChapter 27, Part ADatabase Management Systems, R. Ramakrishnan 2Information RetrievalA research field traditionally separate from Databases•Goes back to IBM, Rand and Lockheed in the 50’s•G. Salton at Cornell in the 60’s•Lots of research since thenProducts traditionally separate•Originally, document management systems for libraries, government, law, etc.•Gained prominence in recent years due to web searchDatabase Management Systems, R. Ramakrishnan 3IR vs. DBMSSeem like very different beasts:Both support queries over large datasets, use indexing. •In practice, you currently have to choose between the two.IR DBMSImprecise Semantics Precise SemanticsKeyword search SQLUnstructured data format Structured dataRead-Mostly. Add docs occasionallyExpect reasonable number of updatesPage through top k resultsGenerate full answerDatabase Management Systems, R. Ramakrishnan 4IR’s “Bag of Words” ModelTypical IR data model:•Each document is just a bag (multiset) of words (“terms”)Detail 1: “Stop Words”•Certain words are considered irrelevant and not placed in the bag•e.g., “the” •e.g., HTML tags like <H1>Detail 2: “Stemming” and other content analysis•Using English-specific rules, convert words to their basic form •e.g., “surfing”, “surfed” --> “surf”Database Management Systems, R. Ramakrishnan 5Boolean Text SearchFind all documents that match a Boolean containment expression: “Windows” AND (“Glass” OR “Door”) AND NOT “Microsoft”Note: Query terms are also filtered via stemming and stop words.When web search engines say “10,000 documents found”, that’s the Boolean search result size (subject to a common “max # returned’ cutoff).Database Management Systems, R. Ramakrishnan 6Text “Indexes”When IR folks say “text index”…•Usually mean more than what DB people meanIn our terms, both “tables” and indexes•Really a logical schema (i.e., tables)•With a physical schema (i.e., indexes)•Usually not stored in a DBMS•Tables implemented as files in a file system•We’ll talk more about this decision soonDatabase Management Systems, R. Ramakrishnan 7A Simple Relational Text IndexCreate and populate a tableInvertedFile(term string, docURL string)Build a B+-tree or Hash index on InvertedFile.term•Alternative 3 (<Key, list of URLs> as entries in index) critical here for efficient storage!! •Fancy list compression possible, too•Note: URL instead of RID, the web is your “heap file”!•Can also cache pages and use RIDsThis is often called an “inverted file” or “inverted index”•Maps from words -> docs Can now do single-word text search queries!Database Management Systems, R. Ramakrishnan 8An Inverted FileSearch for•“databases”•“microsoft”term docURLdata http://www-inst.eecs.berkeley.edu/~cs186database http://www-inst.eecs.berkeley.edu/~cs186date http://www-inst.eecs.berkeley.edu/~cs186day http://www-inst.eecs.berkeley.edu/~cs186dbms http://www-inst.eecs.berkeley.edu/~cs186decision http://www-inst.eecs.berkeley.edu/~cs186demonstrate http://www-inst.eecs.berkeley.edu/~cs186description http://www-inst.eecs.berkeley.edu/~cs186design http://www-inst.eecs.berkeley.edu/~cs186desire http://www-inst.eecs.berkeley.edu/~cs186developer http://www.microsoft.comdiffer http://www-inst.eecs.berkeley.edu/~cs186disability http://www.microsoft.comdiscussion http://www-inst.eecs.berkeley.edu/~cs186division http://www-inst.eecs.berkeley.edu/~cs186do http://www-inst.eecs.berkeley.edu/~cs186document http://www-inst.eecs.berkeley.edu/~cs186Database Management Systems, R. Ramakrishnan 9Handling Boolean LogicHow to do “term1” OR “term2”?•Union of two DocURL sets!How to do “term1” AND “term2”?•Intersection of two DocURL sets!•Can be done by sorting both lists alphabetically and merging the listsHow to do “term1” AND NOT “term2”?•Set subtraction, also done via sortingHow to do “term1” OR NOT “term2”•Union of “term1” and “NOT term2”.•“Not term2” = all docs not containing term2. Large set!!•Usually not allowed!Refinement: What order to handle terms if you have many ANDs/NOTs?Database Management Systems, R. Ramakrishnan 10Boolean Search in SQL(SELECT docURL FROM InvertedFile WHERE word = “windows” INTERSECT SELECT docURL FROM InvertedFile WHERE word = “glass” OR word = “door”)EXCEPTSELECT docURL FROM InvertedFile WHERE word=“Microsoft”ORDER BY relevance()“Windows” AND (“Glass” OR “Door”) AND NOT “Microsoft”Database Management Systems, R. Ramakrishnan 11Boolean Search in SQLReally only one SQL query in Boolean Search IR:•Single-table selects, UNION, INTERSECT, EXCEPTrelevance () is the “secret sauce” in the search engines:•Combos of statistics, linguistics, and graph theory tricks! •Unfortunately, not easy to compute this efficiently using typical DBMS implementation.Database Management Systems, R. Ramakrishnan 12Computing RelevanceRelevance calculation involves how often search terms appear in doc, and how often they appear in collection:•More search terms found in doc  doc is more relevant•Greater importance attached to finding rare termsDoing this efficiently in current SQL engines is not easy:•“Relevance of a doc wrt a search term” is a function that is called once per doc the term appears in (docs found via inv. index):•For efficient fn computation, for each term, we can store the # times it appears in each doc, as well as the # docs it appears in.•Must also sort retrieved docs by their relevance value.•Also, think about Boolean operators (if the search has multiple terms) and how they affect the relevance computation!•An object-relational or object-oriented DBMS with good support for function calls is better, but you still have long execution path-lengths compared to