Expressions are used in a range of applications like publish/subscribe, website personalization, etc. Integrating support for expressions in a database management system (DBMS) provides an efficient and scalable platform for applications that use expressions. Additionally, in many cases these applications can benefit from support for uncertain data and expressions. Current DBMS lack such support. In this paper, we investigate how expressions with uncertainty can be integrated in a DBMS and processed like other data stored in the DBMS. We describe the underlying theory and implementation of UNXS (UNcertain eXpression System), a system that we have developed to handle uncertainty in expressions and data. We first develop a theoretical model to compare previous efforts in supporting uncertainty in DBMS and publish/subscribe systems. We propose new techniques for matching uncertain expressions to uncertain data. We then describe an implementation that integrates this support in the PostgreSQL DBMS.