The window query model is widely used in data stream management systems where the focus of a continuous query is limited to a set of the most recent tuples. In this dissertation, we show that an interesting and important class of continuous queries can not be answered by the existing sliding-window query models. Thus, we introduce a new model for continuous queries, termed the predicate-window query model that limits the focus of a continuous query to the stream tuples that qualify a certain predicate. Predicate windows are characterized by the following (1) The window predicate can be defined over any attribute in the stream tuple (ordered or unordered). (2) Stream tuples qualify and disqualify the window predicate in an out-of-order manner. The goal of this dissertation is to develop an efficient framework to realize predicate windows inside data stream management systems. The predicate-window query framework enables the system to efficiently support a wide variety of streaming applications through an expressive query language and efficient query evaluation mechanisms (i.e., query execution and query optimization). As a test bed for our research, the predicate-window framework is being developed inside Nile; a prototype data stream management system developed at Purdue Univers