CS 534B Topics in Databases -- Information Integration

Fall 2005

Projects

Keep visiting this page often as more project suggestions and related material are added.

• Containment, Equivalence, Answering Queries Using Views, and Information Integration: The goal of this line of work is static analysis of query expressions. In many cases, using static analyses, logical query expressions (whatever be the query language) can be dramtically simplified to yield equivalent expressions that are often much more efficient to compute. At the heart of this analysis is the task of recognizing when a query is contained in another query. Query containment (and hence equivalence) has been extensively studied for various query languages, both for relational and non-relational data. Answering queries using views is a methodology by which we can integrate many different autonomous data sources that deal with similar data, but sport different schema. Surprisingly, containment reasoning plays a pivotal role in query answering using views.

  Here is a selected list of papers which will be helpful in carrying out a project in this area. For papers without links, go to DBLP or citeseer or Google and grab them.

  • Sihem Amer-Yahia, SungRan Cho, Laks V. S. Lakshmanan, Divesh Srivastava: Tree pattern query minimization. VLDB J. 11(4): 315-331 (2002).
  • G. Miklau and D. Suciu. Containment and equivalence for an XPath fragment. PODS 2002.
  • A. Deutsche and V. Tannen. Containment and Integrity constraints for XPath fragment. KRDB 2000.
  • A. Deutsche and V. Tannen. XML queries and constraints, containment and reformulation. Theoretical Computer Science May 2005. Preliminary version appears in ICDT 2003.
  • S. Tang and S. Zhou. A theoretic framework for answering XPath queries using views. XSym Workshop 2005: 18-33.
  • W. Xu and Z. Meral Ozsoyoglu. Rewriting Xpath queries using materialized views. VLDB 2005.
• Integrating DB and IR: Data systems, particularly, those that were designed like database systems and thus have sophisticated querying and transction management capabilities have numerous advantages compared to unstructured and ill-structured systems. On the other hand, sophisticated query languages are not everyone's cup of tea (read, your favotite beverage). Naive users often prefer far simpler interfaces such as a set of keywords for ``querying" a data system. There has been significant recent research effort into investigating ways of integrating database systems and information retireval systems, both for relational and XML data. Here is a selected list of articles on this timely topic.
  • Chengkai Li, Kevin Chen-Chuan Chang, Ihab F. Ilyas, Sumin Song: RankSQL: Query Algebra and Optimization for Relational Top-k Queries. 131-142. SIGMOD 2005.
  • Raghav Kaushik, Rajasekar Krishnamurthy, Jeffrey F. Naughton, Raghu Ramakrishnan: On the Integration of Structure Indexes and Inverted Lists. 779-790. SIGMOD 2004.
  • Sihem Amer-Yahia, Laks V. S. Lakshmanan, Shashank Pandit: FleXPath: Flexible Structure and Full-Text Querying for XML. SIGMOD Conference 2004: 83-94
  • Sihem Amer-Yahia, Jayavel Shanmugasundaram: XML Full-Text Search: Challenges and Opportunities. VLDB 2005: 1368. (Tutorial slides available from Sihem's home page at http://www.research.att.com/~sihem or at http://www.cs.cornell.edu/people/jai/presentations/Tutorial_VLDB_2005.ppt .)
  • Sihem Amer-Yahia, Nick Koudas, Amélie Marian, Divesh Srivastava, David Toman: Structure and Content Scoring for XML. VLDB 2005: 361-372
  • Sihem Amer-Yahia, Chavdar Botev, Jayavel Shanmugasundaram: Texquery: a full-text search extension to xquery. WWW 2004: 583-594
  • Sihem Amer-Yahia, Mary F. Fernández, Divesh Srivastava, Yu Xu: PIX: A System for Phrase Matching in XML Documents. ICDE 2003: 768-776
  • Lin Guo, Jayavel Shanmugasundaram, Kevin S. Beyer, Eugene J. Shekita: Efficient Inverted Lists and Query Algorithms for Structured Value Ranking in Update-Intensive Relational Databases. ICDE 2005: 298-309
  • Chavdar Botev, Jayavel Shanmugasundaram: Context-Sensitive Keyword Search and Ranking for XML. WebDB 2005: 115-120
  • Lin Guo, Feng Shao, Chavdar Botev, Jayavel Shanmugasundaram: XRANK: Ranked Keyword Search over XML Documents. SIGMOD Conference 2003: 16-27
  • Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, S. Sudarshan: Keyword Searching and Browsing in Databases using BANKS. ICDE 2002: 431-440
  • Surajit Chaudhuri, Raghu Ramakrishnan, Gerhard Weikum: Integrating DB and IR Technologies: What is the Sound of One Hand Clapping? CIDR 2005: 1-12
  • Surajit Chaudhuri, Gautam Das, Vagelis Hristidis, Gerhard Weikum: Probabilistic Ranking of Database Query Results. VLDB 2004: 888-899
  • Sanjay Agrawal, Surajit Chaudhuri, Gautam Das, Aristides Gionis: Automated Ranking of Database Query Results. CIDR 2003
  • Sanjay Agrawal, Surajit Chaudhuri, Gautam Das: DBXplorer: A System for Keyword-Based Search over Relational Databases. ICDE 2002: 5-16
  • Vagelis Hristidis, Yannis Papakonstantinou: Algorithms and applications for answering ranked queries using ranked views. VLDB J. 13(1): 49-70 (2004)
  • Vagelis Hristidis, Luis Gravano, Yannis Papakonstantinou: Efficient IR-Style Keyword Search over Relational Databases. VLDB 2003: 850-861
  • Vagelis Hristidis, Yannis Papakonstantinou: DISCOVER: Keyword Search in Relational Databases. VLDB 2002: 670-681
  • Vagelis Hristidis, Yannis Papakonstantinou, Andrey Balmin: Keyword Proximity Search on XML Graphs. ICDE 2003: 367-378
  • Andrey Balmin, Vagelis Hristidis, Yannis Papakonstantinou: ObjectRank: Authority-Based Keyword Search in Databases. VLDB 2004: 564-575
  • Soumen Chakrabarti: Searching and Mining Fine-Grained Semi-Structured Data. Tutorial, VLDB 2002. (Slides available from Soumen's home page: http://http.cs.berkeley.edu/~soumen .)
  • Shurug Al-Khalifa, Cong Yu, H. V. Jagadish: Querying Structured Text in an XML Database. 4-15. SIGMOD 2003.
  • Ihab F. Ilyas, Rahul Shah, Walid G. Aref, Jeffrey Scott Vitter, Ahmed K. Elmagarmid: Rank-aware Query Optimization. 203-214. SIGMOD 2004.
• Peer-to-Peer Data Management/Sharing Systems: When you get and think outside the box (that is, your usual DBMS box!), there are different ways to spread out. At one extreme is regarding the web as one gigantic database and developing abstractions, models, languages, and algorithms for querying it. This will be explored in a separate topic. At another extreme is the possibility of using the network as an enabler of interesting data exchange applications. One such model is that of peer-to-peer data exchange/management systems (or P2P DMS). Here are some relevant papers on this topic.
  • Lucian Popa, Yannis Velegrakis, Renée J. Miller, Mauricio A. Hernández, Ronald Fagin: Translating Web Data. VLDB 2002: 598-609
  • Marcelo Arenas, Vasiliki Kantere, Anastasios Kementsietsidis, Iluju Kiringa, Renée J. Miller, John Mylopoulos: The hyperion project: from data integration to data coordination. SIGMOD Record 32(3): 53-58 (2003)
  • Yannis Velegrakis, Renée J. Miller, Lucian Popa: Mapping Adaptation under Evolving Schemas. VLDB 2003: 584-595
  • Anastasios Kementsietsidis, Marcelo Arenas, Renée J. Miller: Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues. SIGMOD Conference 2003: 325-336
  • Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, Lucian Popa: Data Exchange: Semantics and Query Answering. ICDT 2003: 207-224
  • Ariel Fuxman, Phokion G. Kolaitis, Renée J. Miller, Wang Chiew Tan: Peer Data Exchange. PODS 2005
  • Piazza papers (Alon Halevy et al. Available from http://www.cs.washinton.edu/homes/alon and http://www.cs.washington.edu/suciu).
  • Ling-Ling Yan, Renée J. Miller, Laura M. Haas, Ronald Fagin: Data-Driven Understanding and Refinement of Schema Mappings. SIGMOD 2001.
  • AnHai Doan, Pedro Domingos, Alon Y. Halevy: Reconciling Schemas of Disparate Data Sources: A Machine-Learning Approach. SIGMOD 2001.
  • Panos Kalnis, Wee Siong Ng, Beng Chin Ooi, Dimitris Papadias, Kian-Lee Tan: An adaptive peer-to-peer network for distributed caching of OLAP results. SIGMOD 2002.
  • Anastasios Kementsietsidis, Marcelo Arenas, Renée J. Miller: Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues. 325-336. SIGMOD 2003.
  • Robin Dhamankar, Yoonkyong Lee, AnHai Doan, Alon Y. Halevy, Pedro Domingos: iMAP: Discovering Complex Mappings between Database Schemas. 383-394. SIGMOD 2004.
  • Zachary G. Ives, Alon Y. Halevy, Daniel S. Weld: Adapting to Source Properties in Processing Data Integration Queries. 395-406. SIGMOD 2004.
  • Igor Tatarinov, Alon Y. Halevy: Efficient Query Reformulation in Peer-Data Management Systems. 539-550. SIGMOD 2004.
• Handling Unclean Data: When integrating data from multiple sources, there might be discrepancies and mismatches between the information in the different sources. E.g., different sources may associate different addresses or ages with ``John Smith". Contrariwise, they may associate the same set of properties (age, address, etc.) with "J. Smith" and "John Smith". How do we detect duplicates and how do we resolve inconsistencies? This is the topic of research in an area called data cleaning. Data cleaning is so critical to any industry that cares about data (which is pretty much every one of them) that many industries spend a huge amount of money and effort in having their own corporate data cleaned. In this project, you will study and develop techniques and algorithms for various taskes identified as important in data cleaning. Below are some suggested references.
  • Philip Bohannon, Michael Flaster, Wenfei Fan, Rajeev Rastogi: A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification. 143-154. SIGMOD 2005.
  • Ariel Fuxman, Elham Fazli, Renée J. Miller: ConQuer: Efficient Management of Inconsistent Databases. 155-166. SIGMOD 2005.
  • Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk: Mining database structure; or, how to build a data quality browser. SIGMOD Conference 2002: 240-251. SIGMOD 2002.
  • Tamraparni Dasu, Theodore Johnson: Exploratory Data Mining and Data Cleaning John Wiley 2003.
  • T. Dasu and T. Johnson. Tutorial on Data Cleaning. KDD 2004. Slides.
• Text Mining: There are large corpora of text available online in various forms, spanning the range of locally owned text corpora, online manuals, free text distributed across the web, etc. How can we effectively and efficiently mine hidden patterns in such text collections? This is an exciting area of research. Some suggested references follow.
  • Vinayak R. Borkar, Kaustubh Deshmukh, Sunita Sarawagi: Automatic Segmentation of Text into Structured Records.
  • Clement T. Yu, Weiyi Meng, Wensheng Wu, King-Lup Liu: Efficient and Effective Metasearch for Text Databases Incorporating Linkages among Documents.
  • Arvind Arasu, Hector Garcia-Molina: Extracting Structured Data from Web Pages. 337-348. SIGMOD 2003.
  • Kristina Lerman, Lise Getoor, Steven Minton, Craig A. Knoblock: Using the Structure of Web Sites for Automatic Segmentation of Tables. 119-130. SIGMOD 2004.
• Uncertainty in Data Systems:
  • Reynold Cheng, Dmitri V. Kalashnikov, Sunil Prabhakar: Evaluating Probabilistic Queries over Imprecise Data. 551-562. SIGMOD 2003.
  • Sunita Sarawagi, Alok Kirpal: Efficient set joins on similarity predicates. 743-754. SIGMOD 2004.
  • Kaushik Chakrabarti, Surajit Chaudhuri, Seung-won Hwang: Automatic Categorization of Query Results. 755-766. SIGMOD 2004.
• Managing Data at Large: Think how you'd like to query online help systems or manuals, e.g. Think how you'd like to query a spreadsheet. Or your desktop. (Check out what google and microsoft already have to offer on this last task.)
• Security/Access Control/Privacy in Data Systems:
  • Shariq Rizvi, Alberto O. Mendelzon, S. Sudarshan, Prasan Roy: Extending Query Rewriting Techniques for Fine-Grained Access Control. 551-562. SIGMOD 2004.
  • Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, Yirong Xu: Order-Preserving Encryption for Numeric Data. 563-574. SIGMOD 2004.
  • Gerome Miklau, Dan Suciu: A Formal Analysis of Information Disclosure in Data Exchange. 575-586. SIGMOD 2004.
  • Wenfei Fan, Chee Yong Chan, Minos N. Garofalakis: Secure XML Querying with Security Views. 587-598. SIGMOD 2004.
  • Saul Schleimer, Daniel Shawcross Wilkerson, Alexander Aiken: Winnowing: Local Algorithms for Document Fingerprinting. 76-85. SIGMOD 2003.
  • Rakesh Agrawal, Alexandre V. Evfimievski, Ramakrishnan Srikant: Information Sharing Across Private Databases. 86-97. SIGMOD 2003.
  • Radu Sion, Mikhail J. Atallah, Sunil Prabhakar: Rights Protection for Relational Data. 98-109. SIGMOD 2003.
  • Zhengli Huang, Wenliang Du, Biao Chen: Deriving Private Information from Randomized Data. 37-48. SIGMOD 2005.
  • Kristen LeFevre, David J. DeWitt, Raghu Ramakrishnan: Incognito: Efficient Full-Domain K-Anonymity. 49-60. SIGMOD 2005.
  • Laks V. S. Lakshmanan, Raymond T. Ng, Ganesh Ramesh: To Do or Not To Do: The Dilemma of Disclosing Anonymized Data. 61-72. SIGMOD 2005.