Abstract: Many modem applications require continuous processing of massive data streams, creating difficult research challenges on multiple fronts. Foremost among these there is the design and implementation of Data Stream Management Systems (DSMSs) that optimize the execution of multiple continuous queries, on massive and bursty data streams to produce fast, near-realtime, responses upon tuple arrival. Existing query constructs and query processing techniques of DataBase Management Systems must be greatly extended and revised to support efficiently continuous queries in DSMSs. In this dissertation, we propose novel query scheduling algorithms and query constructs whose effectiveness was demonstrated in the Stream Mill DSMS prototype. Thus, we introduce on-demand timestamp generation and propagation mechanisms based on a flexible query-execution model, to solve the idle-waiting problem, improve query response, and reduce memory consumption. Moreover, we introduce practical scheduling algorithms, which assume uniform cost for tuples on the same operator, to handle query graphs of arbitrary complexity. Finally, we compare the performance of these practical algorithms against the theoretically optimal ones that assume perfect knowledge on the costs of the individual topics being processed. Our experiments show that the performance of the former closely approximate that of the latter. In order to utilize DBMS languages for data stream processing, stream-oriented constructs, such as sliding windows, have to be defined and integrated into the query language. Thus, we introduce novel constructs and techniques for supporting sliding windows on arbitrary User Defined Aggregates, as to achieve their incremental maintenance on logical and physical windows. Finally, we explore some performance optimization issues in advanced applications, including RFID (Radio Frequency IDentification) applications, and load-shedding in multi-source stream classifiers.