Cloud data lakes provide a modern solution for managing large volumes of data. The fundamental principle behind these systems is the separation of compute and storage layers. In this architecture, inexpensive cloud storage is utilized for data storage, while compute engines are employed to perform analytics on this data in an “on-demand” mode. However, to execute any calculations on the data, it must be transferred from the storage layer to the compute layer over the network for each query. This transfer can negatively impact calculation performance and requires significant network bandwidth. In our work, we examine various strategies to enhance query performance within a cloud data lake architecture. We begin by formalizing the problem and proposing a straightforward yet robust theoretical framework that clearly outlines the associated trade-offs. Central to our framework is the concept of a “query coverage set,” which is defined as the collection of files that need to be accessed from storage to fulfill a specific query. Our objective is to identify the minimal coverage set for each query and execute the query exclusively on this subset of files. This approach enables us to significantly improve query performance across three different domains: indexing, caching, and genetic data.

The passage of vehicles through road networks is an increasing challenge due to population density and urban centers worldwide. Frequent road crossings and heavy traffic loads often lead to congestion and lengthy travel times. Prioritizing emergency response vehicles in traffic systems is crucial for saving lives and ensuring public safety. Several approaches are suggested for integrating priority systems for ambulances, fire trucks, police vehicles, and the like. Another aspect of prioritizing vehicles is global energy and traffic savings, such as those achieved through public transportation (e.g., buses, taxis) or platoons (e.g., autonomous trucks). The suggested approaches preserve fairness among vehicles, such that vehicles with the same priority class are prioritized based on their travel starting time on a first-come, first-served basis. The results are efficient polynomial algorithms that respect the first-come, firstserved policy within each priority class and update the schedule to prioritize emergency vehicles as needed. Additionally, we introduce a practical method for testing dynamic traffic scheduling algorithms on real-world data, utilizing image processing in conjunction with GPS data within the SUMO traffic simulation software.

Cloud data lakes are a modern approach to handling large volumes of data. They separate the compute and storage layers, making them highly scalable and cost-effective. However, query performance in cloud data lakes could be faster, and various efforts have been made to enhance it in recent years. We introduce our approach to this problem, which is based on a novel caching technique where instead of caching actual data, we cache metadata called a coverage set.

Cloud data lakes emerge as an inexpensive solution for storing very large amounts of data. The main idea is the separation of compute and storage layers. Thus, cheap cloud storage is used for storing the data, while compute engines are used for running analytics on this data in “on-demand” mode. However, to perform any computation on the data in this architecture, the data should be moved from the storage layer to the compute layer over the network for each calculation. Obviously, that hurts calculation performance and requires huge network bandwidth. In this paper, we study different approaches to improve query performance in a data lake architecture. We define an optimization problem that can provably speed up data lake queries. We prove that the problem is NP-hard and suggest heuristic approaches. Then, we demonstrate through the experiments that our approach is feasible and efficient (up to ×30 query execution time improvement based on the TPC-H benchmark).

In recent years there is huge influx of genomic data and a growing need for its analysis, yet existing genomic databases do not allow easy accessibility. We developed a pipeline that continuously pre-processes raw human genetic data. The data is then stored in a cloud data lake and can be accessed via a simple and intuitive web service and API.

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separate databases and, a relative to it, the issue of private data release was intensively investigated. However, despite a considerable progress, computational complexity and consequently, the performance of the computations, due to an increasing size of data, remains a limiting factor in real-world deployments. Especially in the case of privacy-preserving computations. In this paper, we suggest sampling as a method of improving computational performance. Sampling was a topic of extensive research in the past that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on an approximation of intersection set both with and without a privacy-preserving mechanism. An analysis of the bound on the error as a function of the sample size is discussed and a heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

Identifying traffic platoons and managing vehicles on the road effectively is a challenging task that is currently investigated both in academia and industry. The challenges include the need for fast real-time gathering of relevant information, such as vehicle's location, moving direction, and speed, and instructing the vehicles in real-time to respect traffic policies according to the gathered information. In this work we present new algorithms to define platoons that are updated dynamically on the fly, allowing much better control over the traffic to gain efficiency. A platoon representative vehicle is chosen and the set of vehicles in the platoon is identified based on inductive distance criteria, that are continuously checked and considering the road graph topology and, updating the platoon memberships. In this paper, we present the main algorithms to identify and control the platoon and demonstrate this detection using a vehicle simulator.

Cloud data lakes are a modern approach for storing large amounts of data in a convenient and inexpensive way. The main idea is the separation of compute and storage layers. However, to perform analytics on the data in this architecture, the data should be moved from the storage layer to the compute layer over the network for each calculation. Obviously, that hurts calculation performance and requires huge network bandwidth. We are exploring different approaches for adding indexing to the cloud data lakes with the goal of reducing the amounts of data read from the storage, and as a result, improving query execution time.

The amount of data grows rapidly with time and shows no signs of stopping. Ubiquitous computing continues to collect and generate more and more data as both the number of devices grows and the capabilities of devices increase. We suggest processing the data on end devices by building a representative model of the data (“similitude” model). Sharing a smaller model instead of the entire data allows for saving computing power, network time, processing time and also, keeping the collected data private. In the past research, we suggested the use of similitude models, as compact models of data representation instead of the data itself. In this paper, we suggest the use of deep neural networks (DNN) as a data model to answer different types of queries. More specifically, we show that by building two models (generative network and auto-encoder) it is possible to answer approximately both statistical queries and membership queries without exposing the entire dataset.

Hadoop and Spark are widely used distributed processing frameworks for large-scale data processing in an efficient and fault-tolerant manner on private or public clouds. These big-data processing systems are extensively used by many industries, e.g., Google, Facebook, and Amazon, for solving a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and social network analysis. However, all these popular systems have a major drawback in terms of locally distributed computations, which prevent them in implementing geographically distributed data processing. The increasing amount of geographically distributed massive data is pushing industries and academia to rethink the current big-data processing systems. The novel frameworks, which will be beyond state-of-the-art architectures and technologies involved in the current system, are expected to process geographically distributed data at their locations without moving entire raw datasets to a single location. In this paper, we investigate and discuss challenges and requirements in designing geographically distributed data processing frameworks and protocols. We classify and study batch processing (MapReduce-based systems), stream processing (Spark-based systems), and SQL-style processing geo-distributed frameworks, models, and algorithms with their overhead issues.

We study users behavior in online social networks (OSN) as a means to preserve privacy. People widely use OSN for a variety of objectives and fields. Each OSN has different characteristics, requirements, and vulnerabilities of the private data shared. Sharing-habits refers to users’ patterns of sharing information. Sharing-habits are implied by the communication between users and their peers. While social networks allow users to have some control over the dissemination of their information, most users are not aware that the private information they share might leak to users with whom they do not wish to share it. In this paper we address the growing need of social network users to share information with close fiends while hiding it from others. We apply several different well-known strategies from graph-flow theory to an OSN graph with sharing-habits insights, to control the information flow among OSN users. The goal of the method we present is to allow maximum information sharing while enforcing a user’s pre-defined privacy criteria. Our method is evaluated using real data from well known social networks and the results are analyzed in terms of accuracy and run-time.

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separate databases and, a relative to it, the issue of private data release were intensively investigated. However, despite a considerable progress, computational complexity, due to an increasing size of data, remains a limiting factor in real-world deployments, especially in case of privacy-preserving computations. In this paper, we suggest sampling as a method of improving computational performance. Sampling was a topic of extensive research that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on approximation of intersection set both without and with privacy-preserving mechanism. An analysis of the bound on error as a function of the sample size is discussed and heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

Thanks to their high availability, scalability, and usability, cloud databases have become one of the dominant cloud services. However, since cloud users do not physically possess their data, data integrity may be at risk. In this paper, we present a novel protocol that utilizes crowdsourcing paradigm to provide practical data integrity assurance in key-value cloud databases. The main advantage of our protocol over previous work is its high applicability - as opposed to existing approaches, our scheme does not require any system changes on the cloud side and thus can be applied directly to any existing system. We demonstrate the feasibility of our scheme by a prototype implementation and its evaluation.

Summary Machine learning augments today's intrusion detection system (IDS) capability to cope with unknown malware. However, if an attacker gains partial knowledge about the IDS' classifier, he can create a modified version of his malware, which can evade detection. In this article we present an IDS on the basis of various classifiers using system calls, executed by the inspected code as features. We then present a camouflage algorithm that is used to modify malicious code to be classified as benign, while preserving the code's functionality, for decision tree and random forest classifiers. We also present transformations to the classifier's input, to prevent this camouflage ‐ and a modified camouflage algorithm that overcomes those transformations. Our research shows that it is not enough to provide a decision tree based classifier with a large training set to counter malware. One must also be aware of the possibility that the classifier would be fooled by a camouflage algorithm, and try to counter such an attempt with techniques such as input transformation or training set updates.

Controversially, more data is not necessary better than less data. The explosion of the data lead to a number of interesting practical and theoretical problems. Among those problems are the need to filter, process, verify, index, distribute, protect and make redundant copies of the data. This data “massaging” usually take a lot of time and processing power. However, the quantity of the collected data does not necessary mean quality, as a lot of data is repetitive or does not contain any new information. Nevertheless, it still has to be processed, filtered, consumes high communication volume, has to be protected from breaches and from storage failures. In this position paper we propose to perform data reduction techniques on the collected (big) data prior to gathering of the data in a single location. In many cases (exemplified by two use-cases), especially in Internet-of-Things (IoT), those techniques might save tremendous amounts of power, processing time and network traffic.

We present a solution to the problem of content sharing in digital rights management (DRM) systems. Users in DRM systems purchase content from content providers and then wish to distribute it between their own devices or to other users. The goal is to allow the sharing of such content, with the con trol of the content provider, while ensuring that it complies with the content’s usage rules. We also address in this paper the subject of protecting users’ privacy during the content sharing; to the best of our knowledge no study thus far addressed this topic. While most of the previous studies on content sharing in DRM systems assume the existence of authorized domains, ours does not make that assumption. The solutions that we present here are based on Certified Sharing Requests which are used when devices request from the content provider to share content with other devices. Our solutions enhance the usability of DRM, from both the users’ and content provider’s perspective, by supporting on-the-fly sharing, sharing and re-sharing of controlled content, a pay-per-share business model, and privacy preservation.

Trust and Reputation systems have become key enablers of positive interaction experiences on the Web. These systems accumulate information regarding activities of people or peers in general, to infer their reputation in some context or within a virtual community. Reputation information improves the quality of interactions between peers and reduces the effect of fraudulent members. In this tutorial we motivate the use of trust and reputation systems and survey some of the important models introduced in the past decade. Among these models, we present our work on the knot model, which deals with communities of strangers. Special attention is given to the way existing models tackle attempts to attack reputation systems. In a dynamic world, a person or a service may be a member of multiple communities and valuable information can be gained by sharing reputation of members among communities. In the second part of the tutorial, we present the CCR model for sharing reputation across virtual communities and address major privacy concerns related to it. In the third part of our talk, we discuss the use of reputation systems in other contexts, such as domain reputation for fighting malware, and outline our research directions on this subject.

We consider the problem of computing efficient anonymizations of partitioned databases. Given a database that is partitioned between several sites, either horizontally or vertically, we devise secure distributed algorithms that allow the different sites to obtain a k -anonymized and ℓ-diverse view of the union of their databases, without disclosing sensitive information. Our algorithms are based on the sequential algorithm [Goldberger and Tassa 2010] that offers anonymizations with utility that is significantly better than other anonymization algorithms, and in particular those that were implemented so far in the distributed setting. Our algorithms can apply to different generalization techniques and utility measures and to any number of sites. While previous distributed algorithms depend on costly cryptographic primitives, the cryptographic assumptions of our solution are surprisingly minimal.

When a database is accessed via a web application, users usually receive a pooled connection to the database. From a database point of view, such a connection is always established by the same user (i.e. the web application) and specific data on the end user is not available. As a consequence, users' specific transactions cannot be audited and fine-grained access control cannot be enforced at the database level. In this paper we propose a method and a system which provide the ability to track the end users in web databases. The new method can be applied to legacy web applications without requiring any changes in their existing infrastructure. Furthermore, the new users tracking ability provides a basis for native database protection mechanisms, and intrusion detection systems.

The recent advance in cloud computing and distributed web applications has created the need to store large amount of data in distributed databases that provide high avail- ability and scalability. In recent years, a growing number of companies have adopted various types of non-relational databases, commonly referred to as NoSQL databases, and as the applications they serve emerge, they gain extensive market interest. These new database systems are not relational by definition and therefore they do not support full SQL functionality. Moreover, as opposed to relational databases they trade consistency and security for performance and scalability. As increasingly sensitive data is being stored in NoSQL databases, security issues become growing concerns. This paper reviews two of the most popular NoSQL databases (Cassandra and MongoDB) and outlines their main security features and problems.

We present a method for detecting new malicious executables, which comprise the following steps: (a) in an offline training phase, finding a set of (not necessary consecutive) system call sequences that are characteristic only to malicious files, when such malicious files are executed, and storing said sequences in a database; (b) in a real time detection phase, for each running executable, continuously monitoring its issued system calls and comparing with the stored sequences of system calls within the database to determine whether there exists a match between a portion of the sequence of the run-time system calls and one or more of the database sequences, and when such a match is found, declaring said executable as malicious. We have evaluated our method and the preliminary results are promising and justify the use of system calls sequences for the purpose of detection of new malicious executables.

Information sharing is a key objective in the age of Internet and virtual communities. Reputation information is an important part of a user’s identity and is both a sensitive and desired data for communities to share. At the same time, a reputation that a user has gained at some point in time can leverage her state in new communities. Communities use various trust and reputation models to compute the internal reputation of their members and each model may represent and quantify reputation in different manners. This paper introduces the Cross-Community Reputation (CCR) model that enables to bridge the gap between communities. The CCR model identifies the fundamental terms required for a meaningful sharing of reputation information among communities and proposes means to make them feasible. The model describes the actions taken in response to a request for CCR in three major stages – evaluation of reconditions, conversion of reputation values, and the matching of reputation attributes. The CCR model inherently supports policies specified by both communities and users.

Before the Web era, databases were well-protected by using the standard access control techniques such as Views and SQL authorization commands. But with the development of web systems, the number of attacks on databases increased and it has become clear that their access control mechanism is inadequate for web-based systems. In particular, the SQL Injection and other vulnerabilities have received considerable attention in recent years, and satisfactory solutions to these kinds of attacks are still lacking.

In our era knowledge is not "just" information any more, it is an asset. Data mining can be used to extract important knowledge from large databases. These days, it is often the case that such databases are distributed among several organizations who would like to cooperate in order to extract global knowledge, but at the same time, privacy concerns may prevent the parties from directly sharing the data among them. The two current main methods to perform data mining tasks without compromising privacy are: the perturbation method and the secure computation method. Many papers and published algorithms are based on those two methods. Yet, both have some disadvantages, like reduced accuracy for the first and increased overhead for the second. In this article we offer a new paradigm to perform privacy-preserving distributed data mining without using those methods, we present three algorithms for association rule mining which use this paradigm, and discuss their privacy and performance characteristics

Whereas data mining in structured data focuses on frequent data values, in semistructured and graph data mining, the issue is frequent labels and common specific topologies. The structure of the data is just as important as its content. We study the problem of discovering typical patterns of graph data, a task made difficult because of the complexity of required subtasks, especially subgraph isomorphism. In this paper, we propose a new apriori-based algorithm for mining graph data, where the basic building blocks are relatively large, disjoint paths. The algorithm is proven to be sound and complete. Empirical evidence shows practical advantages of our approach for certain categories of graphs

The control of information flow has been used to address problems concerning the privacy and the secrecy of data. A model based on decentralized labels extends traditional multilevel security models by allowing users to declassify information in a distributed way. We extend this decentralized labels model developed by other authors by addressing specific issues that arise in accessing files and databases and in general in I/O operations. While retaining the support for static analysis, we also include run-time checks to allow declassification with “controlled information leakage”.

Whereas data mining in structured data focuses on frequent data values, in semistructured and graph data the emphasis is on frequent labels and common topologies. Here, the structure of the data is just as important as its content. When data contains large amount of different labels, both fully labeled and partially labeled data may be useful. More informative patterns can be found in the database if some of the pattern nodes can be regarded as 'unlabeled'. We study the problem of discovering typical fully and partially labeled patterns of graph data. Discovered patterns are useful in many applications, including: compact representation of source information and a road-map for browsing and querying information sources.

Schema matching is a problem of finding correspondences, particularly equivalence relationships across schemas. The problem has a particular significance in integrating web repositories, as distributed databases over the web becomes increasingly popular. Most of the existing prototypes use schema level lexical information for schema matching. However, most of them perform rather poorly on real-world problems due to the abundance of abbreviations in real-world schemas. For example, none of the lexical matchers we tested would recommend a mapping of 'cnum' to 'cid', while 'customer number' and 'customer ID' are matching entities. In this work we propose a method for abbreviation expansion in schemas that facilitates lexical schema matching.

XML and other semi-structured data may have partially specified or missing schema information, motivating the use of a structural summary which can be automatically computed from the data. These summaries also serve as indices for evaluating the complex path expressions common to XML and semi-structured query languages. However, to answer all path queries accurately, summaries must encode information about long, seldom-queried paths, leading to increased size and complexity with little added value. We introduce the A(k)-indices, a family of approximate structural summaries. They are based on the concept of k-bisimilarity, in which nodes are grouped based on local structure, i.e., the incoming paths of length up to k. The parameter k thus smoothly varies the level of detail (and accuracy) of the A(k)-index. For small values of k, the size of the index is substantially reduced. While smaller, the A(k) index is approximate, and we describe techniques for efficiently extracting exact answers to regular path queries. Our experiments show that, for moderate values of k, path evaluation using the A(k)-index ranges from being very efficient for simple queries to competitive for most complex queries, while using significantly less space than comparable structures.

Whereas data mining in structured data focuses on frequent data values, in semistructured and graph data the emphasis is on frequent labels and common topologies. Here, the structure of the data is just as important as its content. We study the problem of discovering typical patterns of graph data. The discovered patterns can be useful for many applications, including: compact representation of source information and a road-map for browsing and querying information sources. Difficulties arise in the discovery task from the complexity of some of the required sub-tasks, such as sub-graph isomorphism. This paper proposes a new algorithm for mining graph data, based on a novel definition of support. Empirical evidence shows practical, as well as theoretical, advantages of our approach.

Workflow Management (WFM) Systems automate traditional processes where information flows between individuals. WFM systems have two major implications for security. Firstly, since the description of a workflow process explicitly states when which func

The binary version of the school timetabling (STT) problem is a real‐world example of a constraint network that includes only constraints of inequality. A new and useful representation for this real‐world problem, the STT_Grid, leads to a generic decomposition technique. The paper presents proofs of necessary and sufficient conditions for the existence of a solution to decomposed STT_Grids. The decomposition procedure is of low enough complexity to be practical for large problems, such as a real‐world high school. To test the decomposition approach, a typical high school was analyzed and used as a model for generating STT_Grids of various sizes. Experiments were conducted to test the difficulty of large STT networks and their solution by decomposition. The experimental results show that the decomposition procedure enables the solution of large STT_Grids (620 variables for a real school) in reasonable time. The constraint network of a typical STT_Grid is sparse and belongs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJumping and ForwardChecking) do not terminate in reasonable times for STT_Grids that are larger than 300 variables.

Employee Timetabling Problems (ETP) are all around us. One possible approach for solving ETPs is to use constraint processing techniques. Another approach is to model human knowledge which is commonly used for solving such problems into knowledge-based systems for timetabling. It is difficult to represent the complex constraints of timetabling explicitly in constraint networks. On the other hand, knowledge-based representations of constraints are implicit and cannot support most of the heuristics of constraint-based processing that have been developed over the last decade. The present article presents on approach to representing and processing employee timetabling problems by a combination of explicit representations of some constraints and rule-based processing with heuristics for generic ETP constraints. This mixed-mode approach has been implemented in the form of a software package for defining and solving real-word ETPs. A general description of the design and organization of this software tool is given. Results for solving a typical real-world employee timetabling problem are presented and a comparison with the use of standard CSP (Constraint Satisfaction Problems) techniques is made. © 1997 John Wiley & Sons, Inc.

The performance of object oriented databases (OODB) is a critical factor hindering their current use. Several indexing schemes have been proposed in the literature for enhancing OODB performance and they are briefly reviewed here. A new and uniform indexing scheme is proposed. This scheme is based on a single B tree and combines both the hierarchical and nested indexing schemes (E. Bertino and W. Kim, 1989; W. Kim, 1990). The uniformity of this scheme enables compact and optimized code dealing with a large range of queries on the one hand, and flexibility in adding and removing indexed paths on the other hand. The performance of the scheme is about the same as existing schemes for single class, exact match or range queries, and much better for multi class and other complex queries and update.

The integration of object-oriented programming concepts with databases is one of the most significant advances in the evolution of database systems. Many aspects of such a combination have been studied, but there are few models to provide security for this richly structured information. We develop an authorization model for object-oriented databases. This model consists of a set of policies, a structure for authorization rules, and algorithms to evaluate access requests against the authorization rules. User access policies are based on the concept of inherited authorization applied along the class structure hierarchy. We propose also a set of administrative policies that allow the control of user access and its decentralization. Finally, we study the effect of class structuring changes on authorization.>

A general language for specifying resource allocation and time-tabling problems is presented. The language is based on an expert system paradigm that was developed previously by the authors and that enables the solution of resource allocation problems by using experts' knowledge and heuristics. The language enables the specification of a problem in terms of resources, activities, allocation rules, and constraints, and thus provides a convenient knowledge acquisition tool. The language syntax is powerful and allows the specification of rules and constraints that are very difficult to formulate with traditional approaches, and it also supports the specification of various control and backtracking strategies. We constructed a generalized inference engine that runs compiled resource allocation problem specification language (RAPS) programs and provides all necessary control structures. This engine acts as an expert system shell and is called expert system for resource allocation (ESRA). The performance of RAPS combined with ESRA is demonstrated by analyzing its solution of a typical resource allocation problem.>

An authorization model for object-oriented databases is developed. This model consists of a set of policies, a structure for authorization rules, and an algorithm to evaluate access requests against the authorization rules. The model is illustrated by a specific database system intended for CAD/CAM (computer-aided design/manufacturing) applications, and incorporates knowledge rules with a database of objects combined through an object-oriented semantic association model (OSAM). The database is composed of objects that include a collection of facts and a collection of relevant rules. All the knowledge manipulation operations can be used to express the rules. Some of these rules could be integrity or security rule, i.e. they could be the basis for a mechanism to enforce integrity or security.>

Abstract GCI is a Unix‐based tool for developing interactive CAD programs. By separating command/ menu definitions from the progam, GCI makes it easier to change and extend the user interface. The language provided by GCI is used to define the syntax of commands, menus, messages, and help text. Generally, GCI supports a static hierarchical structure of commands and menus. However, through a program interface, an application program has the freedom to change environments, commands and menus. This flexibility of run‐time control of the user interface is essential for developing highly responsive interfaces in a CAD environment. This paper presents the main concepts and definition language of GCI. It then discusses architectural and implementation issues, and finally presents a typical application's view of using the tool.

Database management systems (DBMS's) today are usually built as subsystems on top of an operating system (OS). This design approach can lead to problems of unreliability and inefficient performance as well as forcing a duplication of functions between the DBMS and OS. A new design approach is proposed which eliminates much of this duplication by integrating the duplicated functions into independent subsystems used by both the DBMS and OS. Specifically, an I/O and file support subsystem and a security subsystem are defined. Both subsystems make use of a logical information model which models the stored information in secondary storage. The new database operating system organization and the logical information model are presented in detail. Design of the security subsystem is based on the access control model, and is extended with Boolean predicates to produce an access control model capable of enforcing content-dependent security policies. The access matrix is implemented using a combination of access lists and capabilities. Authorization models and multiple user processes are discussed in relation to the new system organization. The outline of a formal specification and proof of correctness of the security subsystem is also discussed.

B-trees are a commonly used data structure for indexed access to files and databases. Among the desirable properties of B-trees is the fact that they are dynamically rebalanced after each insertion and deletion operation and therefore need not be reorganized as other static access structures e.g., ISAM. Despite the fact that B-trees are dynamically balanced we demonstrate that operational conditions exist under which it pays off to explicitly reorganize B-trees. The rationale being that by explicit reorganization we defer the event of root splitting and hence reduce the cost of subsequent retrieval requests which are the dominant operations. We present a reorganization algorithm that allows control over storage utilization and discuss the circumstances under which it should be applied. We present simulation results that support our contention that reorganization is indeed economically feasible and we conclude with some suggestions for further work in this area.

The design of a secure file system based on user controlled cryptographic (UCC) transformations is investigated. With UCC transformations, cryptography not only complements other protection mechanisms, but can also enforce protection specifications. Files with different access permissions are enciphered by different cryptographic keys supplied by authorized users at access time. Several classes of protection policies such as: compartmentalized, hierarchical, and data dependent are discussed. Several protection implementation schemes are suggested and analyzed according to criteria such as: security, efficiency, and user convenience. These schemes provide a versatile and powerful set of design alternatives.

A system is described which allows the user to define the syntax of a command language. This is done by reading in the syntax in the form of a Transition Network. The result is an improved user oriented language and increased flexibility of the system.

The security problem in data base systems is analysed. A multilevel structured model is proposed which allows the ‘spreading’ of protection specifications and mechanisms throughout the various levels of the data base. The model is shown to be flexible and general and subsumes several data base security models. These data base models are analysed from the security point of view and it is shown that all of these models require excessive centralisation of protection specifications, mechanisms and control. Such centralisation is not required in the proposed model which makes it more adaptable to different applications.

Abstract An evaluation algorithm for Boolean expressions is efficient if it recognizes when particular conditions cannot affect the value of the result. Of special interest are efficient algorithms which do not expect the conditions to be evaluated in the order in which they appear in the expression. This is important for selective retrieval from a large data base, when the evaluation (retrieval) order depends on the data organization and not on the order in which the qualifiers appear in the query. Another aspect of data retrieval is that we may repeatedly change part (but not all) of the values of the variables, and wish to re‐evaluate part of the expression. Algorithms are given for representing and efficiently evaluating Boolean expressions both for the sequential and random cases; for the latter, an algorithm for partial re‐initialization is also given.