Contains fulltext : 333701.pdf (Publisher’s version ) (Open Access)

Computing has become an essential field of study, with programming as its core component. However, pedagogical aspects of teaching programming remain under-explored and poorly understood. The selection of a student's first programming language has sparked considerable debate within the community, often referred to as a “culture war”, and presents curricular challenges that extend to subsequent language choices. This research full paper investigates the transitions between different programming languages and measures students' learning experiences as they progress through a single language. We utilize Mindshift Learning Theory (MLT) to examine the transfer of knowledge across programming languages as students go through courses in a pre-requisite chain in our curriculum. Our study focuses on three aspects: novelty (encountering new, unique concepts), change (differently applying previously exposed topics), and carryover (directly transferring concepts to new contexts). Our methodology includes an online survey of current and past students transitioning through these courses. We aim to understand how perceived transitions impact mastery and confidence in programming languages. We designed the survey questions, identified target classes, and implemented incentive mechanisms to ensure a statistically significant response rate. Our results are partially aligned with earlier findings in the literature, which correlated carryover, changed, and novel concepts with knowledge scores of object oriented (OO) developers, despite a totally different demographic. Namely, our student participants transitioning to C/C++ (procedural programming) and OO C++ mostly have high, moderate, and low knowledge scores on the programming concepts they perceive as carryover, novel, and changed respectively. On the other hand, those transitioning to OO Java have higher scores for the changed concepts.

The stakeholders in the computer science education have been trying to pinpoint the most relevant factors and variables contributing significantly to student recruitment, success, and retention in computing degrees over the last several decades. The goal of these efforts is to intervene using these controllable variables as early as possible and at key transition junctions for the most benefit to the students. Yet, there is still not a general agreement, let alone a consensus, neither on the most important factors nor on the degree of their contributions. While we cannot provide a panacea to this elusive and challenging problem, in this paper, we report our initial study, analyses, and results of what we intend to transform into a longitudinal undertaking to delineate success factors in computing programs in general, and in CS2 (data structures) courses in particular. Our analyses confirm some of the findings from the literature, such as CS1 performance as the most important contributor for CS2 success as well as prior programming experience, and perception of computing. At the same time we diverge from some of the literature on such factors as high school GPA or CSO performance. Our conclusions corroborate one of the rare consensus in the computing education literature that more efforts should still be exerted in this important topic. We also provide a new and novel taxonomy of the factors for success in computing programs as well as a short summary of the ACM Guidelines over time.

Data integration is frequently required to obtain the full value of data from multiple sources. In spite of extensive research on tools to assist users, data integration remains hard, particularly for users with limited technical proficiency. To address this barrier, we study how much we can do with no user guidance. Our vision is that the user should merely specify two input datasets to be joined and get a meaningful integrated result. It turns out that our vision can be realized if the system can correctly determine the join key, for example based on domain knowledge.

In the last several years, big data analytics has found an increasing role in our everyday lives. Data visualization has long been accepted as an integral part of data analytics. However, data visualization systems are not equipped to handle the complexities typically found in big data. Our work examines effective ways of visualizing big data, while also realizing that most visualization processes are interactive. During an interactive visualization session, an analyst issues several visualization requests, each of which builds on prior visualizations. In our approach, we integrate a distributed data processing system that can effectively process big data with a visualization system that can provide effective interactive visualization but for smaller amounts of data. The analyst's current request is used to infer contextual information about the analyst such as their expertise and tolerance for delay. This information is used to carefully determine additional data that can be sent to the visualization system for decreasing the response time for future requests, thus providing a better experience for the analyst and increasing their productivity.

Because of high volumes and unpredictable arrival rates, stream processing systems cannot always keep up with input data streams, resulting in buffer overflow and uncontrolled loss of data. Load shedding and spilling, the two prevalent technologies designed to solve this overflow problem by dropping or flushing data to disk, suffer from serious shortcomings. Dropping data suffers in that partial output is lost forever, while flushing may waste precious resources due to making the strong assumption that flushed data can and will eventually still be processed. In this paper, we propose our solution, INSURE, integrating structure-based drop and flush techniques within one unified framework for XML stream systems. Our INSURE framework provides an optimized fine-grained load reduction solution that achieves high quality result production. First, the fusion candidate lattice models the space of load reduction solutions incorporating both drop and flush decisions, called fusion candidates. Second, our systematic analysis of fusion candidates and their interrelationships in the fusion candidate lattice reveals important relationships, including the monotonicity of their feasibility and profitability properties. Third, based upon this fusion candidate lattice model, a family of optimization strategies for the selection of fusion candidates is designed to successfully maximize the overall result quality. Experimental results demonstrate that INSURE consistently achieves higher quality results compared to the state-of-the-art techniques, yet with negligible overhead.

Active learning refers to instruction where the learners play an active role in learning and has been found to increase student retention, improve acquisition of higher order thinking and reasoning skills, and improve performance in STEM courses. Two main active learning techniques: student response systems (aka. clickers) and flipped classroom assignments, were incorporated in University of Michigan-Flint computer science (CS) courses. This paper describes how clickers have been incorporated in CS courses and their impact on student learning. There are several ways of evaluating student learning, and tests have traditionally been considered an incomplete and limited reflection of the students' knowledge. In our prior work [11], students' metacognitive knowledge has been used as an effective measure of students' learning. Metacognitive knowledge can be considered to include knowledge of the person, the task, and the available strategies. In this work, we want our students to be aware of their level of understanding of the topics in a course. A student can use this knowledge along with knowledge of the task and available strategies to achieve the cognitive goals. This paper studies how clickers participation impacts student learning as measured by metacognitive knowledge.

Metacognition refers to one's knowledge about one's cognitive processes, and is often associated with intelligence. Students who have good metacognition skills typically perform better in their cognitive tasks. For the Fall and Winter semesters in 2011-12, we incorporated metacognition into our computer science courses (both undergraduate and graduate level courses), so that the student becomes more aware of his/her own understanding of the various topics of the course. In this paper, we describe how we incorporated metacognition into our courses, and present results from our analysis of the data that we have gathered over the various courses.

Courses that involve problem solving provide an opportunity to incorporate meta-cognition as an active learning strategy, where students reflect on their confidence levels on their solutions to problems. As compared to other typically used active learning strategies, meta-cognition provides concrete and comprehensive feedback about the students' learning. The data about confidence levels is potentially useful to both the instructor and the student: an instructor can utilize the data about confidence levels as a second measure of student learning (this is in addition to the scores obtained); a student gets valuable feedback with regards to his/her own comprehension of the topics when he/she examines the confidence levels. We have incorporated meta-cognition techniques in four computer science courses over two semesters at University of Michigan, Flint, including CS1, and also graduate level courses. By analyzing the data obtained, we are able to infer conclusions about (a) How correlated are the scores obtained to the confidence levels reported (b) Is meta-cognition assisting in learning, and (c) Are students more satisfied with a course that incorporates meta-cognition.

Provenance that records the derivation history of data is useful for a wide variety of applications, including those where an audit trail needs to be provided, where the sources and the trust-level attributed to the sources contribute to determining the trust-level in results etc. There have been different efforts in the past for representing provenance information, the most notable being the Open Provenance Model (OPM). OPM defines structures for representing the provenance information as a graph with nodes and edges, and also specifies inference queries. Our work builds on these by proposing query language constructs, that the users will find useful for manipulating the provenance information. Rather than specifying a query language, we define two classes of algebraic constructs: content-based operators that operate on the content of nodes and edges, and structure-based operators that operate on the graph structure of the provenance graph. These content-based and the structure-based constructs can be combined to express a wide variety of interesting queries on the provenance data that go much beyond simple inference queries as expressible using Datalog/SQL.

The federated database architecture has been introduced to maintain the autonomy of individual data sources yet accomplish federated task for diverse applications from traditional enterprises to computational sciences. We identify two challenging problems of query optimization in large-scale database federation systems. First, run-time conditions of data sources have a profound effect on the performance of database federations, yet the distributed environment of database federations makes it prohibitively expensive for the optimizer to gather rapidly fluctuating run-time conditions from remote data sources. Second, large-scale database federation systems are often widely distributed and built on heterogeneous networks, thus efficiently utilizing network resources is of ever increasing importance for query scheduling. In this paper, we propose to exploit the clustered hierarchical structure of database federations to solve these two problems. Our Cluster-and-Conquer strategy coordinates hierarchical clusters of data sources to optimize and process queries cooperatively. Within each cluster we employ an I/O-bound cost model with run-time conditions being accessible with relatively little delay. While among clusters a network-bound cost model is instead utilized to capture the network heterogeneity and optimize the query plans for efficient network utilization. The experimental study on the prototype database federation system with real-world network settings shows the effectiveness of our Cluster-and-Conquer strategy for scheduling data-intensive queries, as well as demonstrates the performance benefits of our proposed strategies over existing state-of-art solutions.

Because of high volumes and unpredictable arrival rates, stream processing systems are not always able to keep up with input data - resulting in buffer overflow and uncontrolled loss of data. To produce eventually complete results, load spilling, which pushes some fractions of data to disks temporarily, is commonly employed in relational stream engines. In this work, we now introduce "structure-based spilling", a spilling technique customized for XML streams by considering the partial spillage of possibly complex XML elements. Such structure-based spilling brings new challenges. When a path is spilled, multiple paths may be affected. We analyze possible spilling effects on the query paths and how to execute the "reduced" query to produce partial results. To select the reduced query that maximizes output quality, we develop three optimization strategies, namely, OptR, OptPrune and ToX. We also examine the clean-up stage to guarantee that an entire result set is eventually generated by producing supplementary results. Our experimental study demonstrates that our proposed solutions consistently achieve higher quality results compared to the state-of-the-art techniques.

XML stream applications bring the novel challenge of efficiently processing queries on sequentially accessible token-based input streams. Our Raindrop project is the first to accommodate token-based stream processing using an algebraic framework where both tokens and tuples are modeled in a uniform manner. In this paper, we illustrate how the stream loading model of our system on the fly conducts XML navigation over the input stream via concurrently constructing a minimized light-weight XML tree representation, which is called navigation-free data instance. These captured XML fragments are minimized in terms of buffer consumption. Based on the compact representation of the navigation-free data instances, we propose techniques for subsequent algebraic query evaluation, in particular, effective strategies for supporting multi-mode query operators and alternative data output semantics. The proposed stream loading model requires a much smaller buffer footprint, compared to alternative solutions in the literature such as Y-Filter. And the proposed algebra-based evaluation techniques offer effective ways to handle data recursion over XML streams, i.e., avoiding overhead from the structural join operators. Our stream loading and query evaluation techniques have been implemented as part of the Raindrop system. Experimental results based on the Raindrop system are also reported in this paper.

Because of the high volume and unpredictable arrival rate, stream processing systems may not always be able to keep up with the input data streams - resulting in buffer overflow and uncontrolled loss of data. Load shedding, the prevalent strategy for solving this overflow problem, has so far only been considered for relational stream processing, but not for XML. Shedding applied to XML stream processing brings new opportunities and challenges due to complex nested nature of XML structures. In this paper, we tackle this unsolved XML shedding problem using a three-pronged approach. First, we develop an XQuery preference model that enables users to specify the relative importance of preserving different subpatterns in the XML result structure. This transforms shedding into the problem of rewriting the user query into shed queries that return approximate query answers with utility as measured by the given user preference model. Second, we develop a cost model to compare the performance of alternate shed queries. Third, we develop two shedding algorithms, OptShed and FastShed. OptShed guarantees to find an optimal solution however at the cost of exponential complexity. FastShed, as confirmed by our experiments, achieves a close-to-optimal result in a wide range of test cases. Finally we describe the in-automaton shedding mechanism for XQuery stream engines. The experiments show that our proposed utility-driven shedding solutions consistently achieve higher utility results compared to the existing relational shedding techniques.

Materializing the contents of views has important applications including providing fast access to derived database repositories, optimizing query processing based on cached results, and increasing availability. Maintaining the consistency between materialized views and their base data in the presence of source updates is important to ensure that the materialized views are up-to-date. The straightforward solution for this problem is to recompute the view from scratch over the updated sources.

Both XML-relational systems and native XML systems support creating XML wrapper views and querying against them. However, update operations against such virtual XML views in most cases are not supported yet.

Many applications, like materialized view maintenance and stream query processing, construct views incrementally over data sources. This results in computed pieces of objects that need to be merged by fusing corresponding objects together. This problem is challenging when dealing with XML data for many reasons including the hierarchical and semi-structured nature of XML data. Also XML query languages (e.g., XQuery) are capable of performing complex operations and transformations such as arbitrary nesting and result reconstruction. Moreover, since XML is an ordered data model, XML order has to be taken into consideration when constructing XML results incrementally. In this paper we study the problem of how to fuse XML pieces (fragments) generated by incrementally processing XML data into XML results. We consider an expressive subset of XQuery language transformations and propose an id-based solution for this problem that supports XML order. We prove the correctness of our approach, in particular that using our mechanism we can correctly yet incrementally merge XML result fragments. We have implemented our proposed semantic identifiers solution. Our experimental results show that it comes with a very small overhead to the query execution time.

On the basis of regular tree grammars, we present a formal framework for XML schema languages. This framework helps to describe, compare, and implement such schema languages in a rigorous manner. Our main results are as follows: (1) a simple framework to study three classes of tree languages (local, single-type, and regular); (2) classification and comparison of schema languages (DTD, W3C XML Schema, and RELAX NG) based on these classes; (3) efficient document validation algorithms for these classes; and (4) other grammatical concepts and advanced validation algorithms relevant to an XML model (e.g., binarization, derivative-based validation).

Two algorithms, called NeT and CoT, to translate relational schemas to XML schemas using various semantic constraints are presented. The XML schema representation we use is a language-independent formalism named XSchema, that is both precise and concise. A given XSchema can be mapped to a schema in any of the existing XML schema language proposals. Our proposed algorithms have the following characteristics: (1) NeT derives a nested structure from a flat relational model by repeatedly applying the nest operator on each table so that the resulting XML schema becomes hierarchical, and (2) CoT considers not only the structure of relational schemas, but also semantic constraints such as inclusion dependencies during the translation. It takes as input a relational schema where multiple tables are interconnected through inclusion dependencies and converts it into a good XSchema. To validate our proposals, we present experimental results using both real schemas from the UCI repository and synthetic schemas from TPC-H.

Two conversion algorithms, called NeT and COT, to translate relational schemas to XML schemas using various semantic constraints are presented. We first present a language-independent formalism named XSchema so that our algorithms are able to generate output schema in various XML schema language proposals. The benefits of such a formalism are that it is both precise and concise. Based on the XSchema formalism, our proposed algorithms have the following characteristics: (1) NeT derives a nested structure from a flat relational model by repeatedly applying the nest operator so that the resulting XML schema becomes hierarchical, and (2) COT considers not only the structure of relational schemas, but also inclusion dependencies during the translation so that relational schemas where multiple tables are interconnected through inclusion dependencies can also be handled.