Abstract: Turing computability has been the benchmark for computational expressiveness since the beginnings of modern computer science. It is equivalent to many other systems and languages, such as the lambda calculus, partial recursive functions, cellular automata, fixed and stored program models, semi-Thue systems and type-0 grammars. However, data manipulation languages, such as SQL and QBE, along with formalisms such as tuple calculus and relational algebra, lack the full power of a Turing-complete language. This talk explores the benefits of this "simplicity" in terms of system behavior and execution efficiency. We discuss properties that data languages have that are not shared with computationally complete languages. We then turn to extensions to data languages that attempt to regain some of the expressive power while retaining most of the desirable properties.
About the speaker: Dr. Maier is Maseeh Professor of Emerging Technologies at Portland State University. Prior to his current position, he was on the faculty at SUNY-Stony Brook and the Oregon Graduate Institute. He has spent extended visits with INRIA, University of Wisconsin – Madison, Microsoft Research and National University of Singapore. He is the author of books on relational databases, logic programming, and object-oriented databases, as well as papers in database theory, object-oriented technology, scientific databases, and dataspace management. He is a recognized expert on the challenges of large-scale data in the sciences. He received an NSF Young Investigator Award in 1984 and was awarded the 1997 SIGMOD Innovations Award for his contributions in objects and databases. He is also an ACM Fellow and IEEE Senior Member, and serves on the Board on Mathematical Sciences and their Applications of the National Research Council. He holds a dual B.A. in Mathematics and in Computer Science from the University of Oregon (Honors College, 1974) and a PhD in Electrical Engineering and Computer Science from Princeton University (1978).