Web Searching and Σ₂ Queries

Abstract

In the terminology of Logic programming, current search engines answer Σ₁ queries (formulas of the form $\exists\overline{x}\varphi(\overline{x})$ where $\varphi(\overline{x})$ is a boolean combination of attributes). Such a query is determined by a particular sequence of keywords input by a user. In order to give more control to users, search engines will have to tackle more expressive queries, namely, Σ₂ queries (formulas of the form $\exists\overline{x}\forall\overline{y}\varphi(\overline{x},\overline{y})$). The purpose of the talk is to examine which directions could be explored in order to move towards more expressive languages, more powerful search engines, and the benefits that users should expect.