1,721,222 research outputs found
INFORMATICAWETENSCHAPPEN, COMPUTATIONEEL DENKEN EN PROGRAMMEREN
No full textProgrammeren, computationeel denken, coding … we kunnen geen krant
of onderwijsblog meer lezen zonder deze termen tegen te komen. Maar
wat betekenen die termen, en waarom zijn ze vandaag zo belangrijk? In dit
hoofdstuk gaan we dieper in op wat computationeel denken en programmeren
nu juist zijn. Maar vooraleer we dit doen beargumenteren we de
noodzaak om elke jongere een basisopleiding informaticawetenschappen
aan te bieden die toelaat om informaticavaardig te worden.https://onderwijs.vlaanderen.be/nl/onderwijspersoneel/van-basis-tot-volwassenenonderwijs/lespraktijk/ict-in-de-klas/zo-denkt-een-computer-programmeren-en-computationeel-denken-in-het-onderwijs
De publicatie bestaat uit drie grote delen. In een inleidend deel wordt dieper ingegaan op de verschillende componenten van computationeel denken, en wat er op dit vlak van scholen verwacht mag worden. Het tweede deel bevat de uitgewerkte praktijkvoorbeelden, zoals ze ontwikkeld zijn door de scholen uit het lerend netwerk programmeren. In een laatste deel vind je verwijzingen naar extra literatuur en naar organisaties die ondersteuning, materiaal en nascholing bieden. We beperken ons in dit deel tot die organisaties die een concreet aanbod voor scholen aanbieden. We hopen dat de praktijkvoorbeelden en de informatie in deze publicatie scholen in heel Vlaanderen zullen helpen om op een kwaliteitsvolle manier in te zetten op ICT-gebruik, computationeel denken en programmere
INFORMATICAWETENSCHAPPEN, COMPUTATIONEEL DENKEN EN PROGRAMMEREN
No full textProgrammeren, computationeel denken, coding … we kunnen geen krant
of onderwijsblog meer lezen zonder deze termen tegen te komen. Maar
wat betekenen die termen, en waarom zijn ze vandaag zo belangrijk? In dit
hoofdstuk gaan we dieper in op wat computationeel denken en programmeren
nu juist zijn. Maar vooraleer we dit doen beargumenteren we de
noodzaak om elke jongere een basisopleiding informaticawetenschappen
aan te bieden die toelaat om informaticavaardig te worden.https://onderwijs.vlaanderen.be/nl/onderwijspersoneel/van-basis-tot-volwassenenonderwijs/lespraktijk/ict-in-de-klas/zo-denkt-een-computer-programmeren-en-computationeel-denken-in-het-onderwijs
De publicatie bestaat uit drie grote delen. In een inleidend deel wordt dieper ingegaan op de verschillende componenten van computationeel denken, en wat er op dit vlak van scholen verwacht mag worden. Het tweede deel bevat de uitgewerkte praktijkvoorbeelden, zoals ze ontwikkeld zijn door de scholen uit het lerend netwerk programmeren. In een laatste deel vind je verwijzingen naar extra literatuur en naar organisaties die ondersteuning, materiaal en nascholing bieden. We beperken ons in dit deel tot die organisaties die een concreet aanbod voor scholen aanbieden. We hopen dat de praktijkvoorbeelden en de informatie in deze publicatie scholen in heel Vlaanderen zullen helpen om op een kwaliteitsvolle manier in te zetten op ICT-gebruik, computationeel denken en programmere
Succinctness of Pattern-Based Schema Languages for XML
No full textMartens et al. defined a pattern-based specification language equivalent in expressive power to the widely adopted XML Schema definitions (XSDs). This language consists of rules of the form (r,s) where r and s are regular expressions and can be seen as a type-free extension of DTDs with vertical regular expressions. Sets of such rules can be interpreted both in an existential or universal way. In the present paper, we study the succinctness of both semantics w.r.t. each other and w.r.t. the common abstraction of XSDs in terms of single-type extended DTDs. The investigation is carried out relative to three kinds of vertical pattern languages: regular, linear, and strongly linear patterns. We also consider the complexity of the simplification problem for each of the considered pattern-based schema’s
The ACM PODS Alberto O. Mendelzon Test-of-Time Award 2023
No full textIn 2007, the PODS Executive Committee decided to establish a Test-of-Time Award, named after the late Alberto O. Mendelzon, in recognition of his scientific legacy, and his service and dedication to the database community. Mendelzon was an international leader in database theory, whose pioneering and fundamental work has inspired and influenced both database theoreticians and practitioners, and continues to be applied in a variety of advanced settings. He served the database community in many ways; in particular, he served as the General Chair of the PODS conference, and was instrumental in bringing together the PODS and SIGMOD conferences. He also was an outstanding educator, who guided the research of numerous doctoral students and postdoctoral fellows. The Award is to be awarded each year to a paper or a small number of papers published in the PODS proceedings ten years prior, that had the most impact (in terms of research, methodology, or transfer of practice) over the intervening decade. The decision was approved by SIGMOD and ACM. The funds for the Award were contributed by IBM Toronto. The PODS Executive Chair has appointed us to serve as the Award Committee for 2023. After careful consideration, we have decided to select the following two papers as the award winners for 2023: The first paper introduces the Massively Parallel Communication (MPC) model to analyze the tradeoff between the number of rounds and the amount of communication required in a massively parallel computing environment. A decade ago there was a growing interest in the study of data processing on large distributed clusters, which resulted in the introduction of various models focusing on different aspects. The MPC model can be seen as the culmination of these models and was designed as an abstraction for the shared-nothing architecture which remains the architecture used by large data processing systems today. Since then, the MPC model is widely adopted in the literature. In the paper, the authors obtain both lower and upper bounds for computing full conjunctive queries in the one round and multi-round case. In particular, they discover an interesting connection between the number of bits that are required to be sent in the single-round case for computing a conjunctive query and the fractional vertex covering number of the hypergraph associated to that query. The monograph "Algorithmic Aspects of Parallel Data Processing" in Foundations and Trends in Databases (2018) presents a detailed overview of the research on the MPC model since its introduction. Ontology-based data access (OBDA) provides a formalization of the problem of querying a database enhanced with an ontology. This simple formal model provides a unifying view for problems in many different areas, and in particular for the widely studied issue of extracting information from a knowledge graph. As such, OBDA has been extensively studied, mainly following two lines of research: the development of efficient query answering algorithms for some classes of query and ontology languages, and the characterization of combinations of these two elements that lead to intractability. In the second paper, the authors follow a different path to study OBDA, which has brought new tools to the area and, as such, has become a fruitful way to address the fundamental challenges in OBDA. More precisely, the authors consider the expressive power of the settings used in OBDA, whose main parameters are the query and ontology
Typechecking top-down XML transformations: Fixed input or output schemas
No full textAbstractTypechecking consists of statically verifying whether the output of an XML transformation always conforms to an output type for documents satisfying a given input type. In this general setting, both the input and output schema as well as the transformation are part of the input for the problem. However, scenarios where the input or output schema can be considered to be fixed, are quite common in practice. In the present work, we investigate the computational complexity of the typechecking problem in the latter setting
When View- and Conflict-Robustness Coincide for Multiversion Concurrency Control
No full textA DBMS allows trading consistency for efficiency through the allocation of isolation levels that are strictly weaker than serializability. The robustness problem asks whether, for a given set of transactions and a given allocation of isolation levels, every possible interleaved execution of those transactions that is allowed under the provided allocation, is always safe. In the literature, safe is interpreted as conflict-serializable (to which we refer here as conflict-robustness). In this paper, we study the view-robustness problem, interpreting safe as view-serializable. View-serializability is a more permissive notion that allows for a greater number of schedules to be serializable and aligns more closely with the intuitive understanding of what it means for a database to be consistent. However, view-serializability is more complex to analyze (e.g., conflict-serializability can be decided in polynomial time whereas deciding view-serializability is NP-complete). While conflict-robustness implies view-robustness, the converse does not hold in general. In this paper, we provide a sufficient condition for isolation levels guaranteeing that conflict- and view-robustness coincide and show that this condition is satisfied by the isolation levels occurring in Postgres and Oracle: read committed (RC), snapshot isolation (SI) and serializable snapshot isolation (SSI). It hence follows that for these systems, widening from conflict- to view-serializability does not allow for more sets of transactions to become robust. Interestingly, the complexity of deciding serializability within these isolation levels is still quite different. Indeed, deciding conflict-serializability for schedules allowed under RC and SI remains in polynomial time, while we show that deciding view-serializability within these isolation levels remains NP-complete
Allocating Isolation Levels to Transactions in a Multiversion Setting
No full textA serializable concurrency control mechanism ensures consistency for OLTP systems at the expense of a reduced transaction throughput. A DBMS therefore usually offers the possibility to allocate lower isolation levels for some transactions when it is safe to do so. However, such trading of consistency for efficiency does not come with any safety guarantees. In this paper, we study the mixed robustness problem which asks whether, for a given set of transactions and a given allocation of isolation levels, every possible interleaved execution of those transactions that is allowed under the provided allocation is always serializable. That is, whether the given allocation is indeed safe. While robustness has already been studied in the literature for the homogeneous setting where all transactions are allocated the same isolation level, the heterogeneous setting that we consider in this paper, despite its practical relevance, has largely been ignored. We focus on multiversion concurrency control and consider the isolation levels that are available in Postgres and Oracle: read committed (RC), snapshot isolation (SI) and serializable snapshot isolation (SSI). We show that the mixed robustness problem can be decided in polynomial time. In addition, we provide a polynomial time algorithm for computing the optimal robust allocation for a given set of transactions, prioritizing lower over higher isolation levels. The present results therefore establish the groundwork to automate isolation level allocation within existing databases supporting multiversion concurrency control
Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics
No full textSingle-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query. This property is referred to as parallel-correctness. Another key problem is to detect whether the data reshuffle step can be avoided when evaluating subsequent queries. The latter problem is referred to as transfer of parallel-correctness. This paper extends the study of parallel-correctness and transfer of parallel-correctness of conjunctive queries to incorporate bag semantics. We provide semantical characterizations for both problems, obtain complexity bounds and discuss the relationship with their set semantics counterparts. Finally, we revisit both problems under a modified distribution model that takes advantage of a linear order on compute nodes and obtain tight complexity bounds
The ACM PODS Alberto O. Mendelzon Test-of-Time Award 2023
No full textIn 2007, the PODS Executive Committee decided to establish a Test-of-Time Award, named after the late Alberto O. Mendelzon, in recognition of his scientific legacy, and his service and dedication to the database community. Mendelzon was an international leader in database theory, whose pioneering and fundamental work has inspired and influenced both database theoreticians and practitioners, and continues to be applied in a variety of advanced settings. He served the database community in many ways; in particular, he served as the General Chair of the PODS conference, and was instrumental in bringing together the PODS and SIGMOD conferences. He also was an outstanding educator, who guided the research of numerous doctoral students and postdoctoral fellows. The Award is to be awarded each year to a paper or a small number of papers published in the PODS proceedings ten years prior, that had the most impact (in terms of research, methodology, or transfer of practice) over the intervening decade. The decision was approved by SIGMOD and ACM. The funds for the Award were contributed by IBM Toronto. The PODS Executive Chair has appointed us to serve as the Award Committee for 2023. After careful consideration, we have decided to select the following two papers as the award winners for 2023: The first paper introduces the Massively Parallel Communication (MPC) model to analyze the tradeoff between the number of rounds and the amount of communication required in a massively parallel computing environment. A decade ago there was a growing interest in the study of data processing on large distributed clusters, which resulted in the introduction of various models focusing on different aspects. The MPC model can be seen as the culmination of these models and was designed as an abstraction for the shared-nothing architecture which remains the architecture used by large data processing systems today. Since then, the MPC model is widely adopted in the literature. In the paper, the authors obtain both lower and upper bounds for computing full conjunctive queries in the one round and multi-round case. In particular, they discover an interesting connection between the number of bits that are required to be sent in the single-round case for computing a conjunctive query and the fractional vertex covering number of the hypergraph associated to that query. The monograph "Algorithmic Aspects of Parallel Data Processing" in Foundations and Trends in Databases (2018) presents a detailed overview of the research on the MPC model since its introduction. Ontology-based data access (OBDA) provides a formalization of the problem of querying a database enhanced with an ontology. This simple formal model provides a unifying view for problems in many different areas, and in particular for the widely studied issue of extracting information from a knowledge graph. As such, OBDA has been extensively studied, mainly following two lines of research: the development of efficient query answering algorithms for some classes of query and ontology languages, and the characterization of combinations of these two elements that lead to intractability. In the second paper, the authors follow a different path to study OBDA, which has brought new tools to the area and, as such, has become a fruitful way to address the fundamental challenges in OBDA. More precisely, the authors consider the expressive power of the settings used in OBDA, whose main parameters are the query and ontology
Data Ingestion Validation through Stable Conditional Metrics with Ranking and Filtering
No full textWe present a data ingestion quality validation approach using conditional metrics, a novel form of metrics that compute data quality metrics over specific parts of the ingestion data. We propose a method that automatically derives conditional metrics from historical ingestion sequences, using stability as a selection criterion for implementing these metrics as data unit tests. If an ingestion batch fails any unit tests, we show how conditional metrics can be utilized to identify potential errors. We show the effectiveness of our approach through an evaluation on a real world data set under various error scenarios
- …
