Abstract Random minimaxing studies the consequences of using a random number for scoring the leaf nodes of a full width game tree and then computing the best move using the standard minimax procedure. Experiments in Chess showed that the strength of play increases as the depth of the lookahead is increased. Previous research by the authors provided a partial explanation of why random minimaxing can strengthen play by showing that, when one move dominates another move, then the dominating move is more likely to be chosen by minimax. This paper examines a special case of determining the move probability when domination does not occur. Specifically, we show that, under a uniform branching game tree model, whether the probability that one move is chosen rather than another depends not only on the branching factors of the moves involved, but also on whether the number of ply searched is odd or even. This is a new type of game tree pathology, where the minimax procedure will change its mind as to which move is best, independently of the true value of the game, and oscillate between moves as the depth of lookahead alternates between odd and even.

Branching processes are discrete-time stochastic processes which have been largely employed to model and simulate information diffusion processes over large online social networks such as Twitter and Reddit. Here we show that a variant of the branching process model enables the prediction of the popularity of user-generated content and thus can serve as a method for ranking search results or suggestions displayed to users. The proposed branching-process variant is able to evaluate the importance of an agent in a social network and, thus we propose a novel centrality index, called the Stochastic Potential Gain (SPG). The SPG is the first centrality index which combines the knowledge of the network topology with a dynamic process taking place on it which we call a graph-driven branching process. SPG generalises a range of popular network centrality metrics such as Katz' and Subgraph. We formulate a Monte Carlo algorithm (called MCPG) to compute the SPG and prove that it is convergent and correct. Experiments on two real datasets drawn from Facebook and GitHub demonstrate that MCPG traverses only a small fraction of nodes to produce its result, thus making the Stochastic Potential Gain an appealing option to compute node centrality measure for Online social networks.

We propose a new word embedding model, called SPhrase, that incorporates supervised phrase information. Our method modifies traditional word embeddings by ensuring that all target words in a phrase have exactly the same context. We demonstrate that including this information within a context window produces superior embeddings for both intrinsic evaluation tasks and downstream extrinsic tasks.

Centrality metrics are a popular tool in Network Science to identify important nodes within a graph. We introduce the Potential Gain as a centrality measure that unifies many walk-based centrality metrics in graphs and captures the notion of node navigability, interpreted as the property of being reachable from anywhere else (in the graph) through short walks. Two instances of the Potential Gain (called the Geometric and the Exponential Potential Gain) are presented and we describe scalable algorithms for computing them on large graphs. We also give a proof of the relationship between the new measures and established centralities. The geometric potential gain of a node can thus be characterized as the product of its Degree centrality by its Katz centrality scores. At the same time, the exponential potential gain of a node is proved to be the product of Degree centrality by its Communicability index. These formal results connect potential gain to both the “popularity” and “similarity” properties that are captured by the above centralities.

Navigability is a distinctive features of graphs associated with artificial or natural systems whose primary goal is the transportation of information or goods. We say that a graph is navigable when an agent is able to efficiently reach any target node in by means of local routing decisions. In a social network navigability translates to the ability of reaching an individual through personal contacts. Graph navigability is well-studied, but a fundamental question is still open: why are some individuals more likely than others to be reached via short, friend-of-a-friend, communication chains? In this article we answer the question above by proposing a novel centrality metric called the potential gain, which, in an informal sense, quantifies the easiness at which a target node can be reached. We define two variants of the potential gain, called the geometric and the exponential potential gain, and present fast algorithms to compute them. The geometric and the potential gain are the first instances of a novel class of composite centrality metrics, i.e., centrality metrics which combine the popularity of a node in G with its similarity to all other nodes. As shown in previous studies, popularity and similarity are two main criteria which regulate the way humans seek for information in large networks such as Wikipedia. We give a formal proof that the potential gain of a node is always equivalent to the product of its degree centrality (which captures popularity) and its Katz centrality (which captures similarity).

The various activities that take place within an observed environment such as a university campus, determine to a large extent, the kind of social interactions exhibited by the users in such environments. Using a big data set of wifi-traces, we attempt to understand the rules that governs these social interactions. We discovered that there are at least two types of social interactions within a university campus: formal such as attending a class and informal such as meeting friends at the cafeteria for coffee. Each of these two types of social interactions is tightly associated with a specific set of locations within the university campus. We also discovered that users tend to restrict their social interactions to a small set of geographical locations, where users revisited the same location to socialise with the same social group. Also, irrespective of the type of the social interactions, users tend to restrict their revisits to geographically nearby locations and only revisit locations that are further afield when they are in the company of their social group. These findings are based on the social groups detected by a new scalable density-based clustering method applied to a large data set of mobile users wifi traces. The results of the large experiments carried out in this research demonstrate how the proposed algorithm can noninvasively detect social groups on the basis of the activity performed at the selected location.

In this study we aim to explore users' behavior when assessing search results relevance based on the hypothesis of categorical thinking. To investigate how users categories search engine results, we perform several experiments where users are asked to group a list of 20 search results into several categories, while attaching a relevance judgment to each formed category. Moreover, to determine how users change their minds over time, each experiment was repeated three times under the same conditions, with a gap of one month between rounds. The results show that on average users form 4–5 categories. Within each round the size of a category decreases with the relevance of a category. To measure the agreement between the search engine's ranking and the users’ relevance judgments, we defined two novel similarity measures, the average concordance and the MinMax swap ratio. Similarity is shown to be the highest for the third round as the users' opinion stabilizes. Qualitative analysis uncovered some interesting points that users tended to categories results by type and reliability of their source, and particularly, found commercial sites less trustworthy, and attached high relevance to Wikipedia when their prior domain knowledge was limited.

There is often the need to perform sentiment classification in a particular domain where no labeled document is available. Although we could make use of a general-purpose off-the-shelf sentiment classifier or a pre-built one for a different domain, the effectiveness would be inferior. In this paper, we explore the possibility of building domain-specific sentiment classifiers with unlabeled documents only. Our investigation indicates that in the word embeddings learned from the unlabeled corpus of a given domain, the distributed word representations (vectors) for opposite sentiments form distinct clusters, though those clusters are not transferable across domains. Exploiting such a clustering structure, we are able to utilize machine learning algorithms to induce a quality domain-specific sentiment lexicon from just a few typical sentiment words (“seeds”). An important finding is that simple linear model based supervised learning algorithms (such as linear SVM) can actually work better than more sophisticated semi-supervised/transductive learning algorithms which represent the state-of-the-art technique for sentiment lexicon induction. The induced lexicon could be applied directly in a lexicon-based method for sentiment classification, but a higher performance could be achieved through a two-phase bootstrapping method which uses the induced lexicon to assign positive/negative sentiment scores to unlabeled documents first, a nd t hen u ses those documents found to have clear sentiment signals as pseudo-labeled examples to train a document sentiment classifier v ia supervised learning algorithms (such as LSTM). On several benchmark datasets for document sentiment classification, our end-to-end pipelined approach which is overall unsupervised (except for a tiny set of seed words) outperforms existing unsupervised approaches and achieves an accuracy comparable to that of fully supervised approaches.

We present the first systematic study of the influence of time on user judgements for rankings and relevance grades of web search engine results. The goal of this study is to evaluate the change in user assessment of search results and explore how users' judgements change. To this end, we conducted a large‐scale user study with 86 participants who evaluated 2 different queries and 4 diverse result sets twice with an interval of 2 months. To analyze the results we investigate whether 2 types of patterns of user behavior from the theory of categorical thinking hold for the case of evaluation of search results: (a) coarseness and (b) locality. To quantify these patterns we devised 2 new measures of change in user judgements and distinguish between local (when users swap between close ranks and relevance values) and nonlocal changes. Two types of judgements were considered in this study: (a) relevance on a 4‐point scale, and (b) ranking on a 10‐point scale without ties. We found that users tend to change their judgements of the results over time in about 50% of cases for relevance and in 85% of cases for ranking. However, the majority of these changes were local.

No abstract available.

We present a seed expansion based approach to classify named entities in web search queries. Previous approaches to this classification problem relied on contextual clues in the form of keywords surrounding a named entity in the query. Here we propose an alternative approach in the form of a Bag-of-Context-Words (BoCW) that is used to represent the context words as they appear in the snippets of the top search results for the query. This is particularly useful in the case where the query consists of only the named entity without any context words, since in the previous approaches no context is discovered. In order to construct the BoCW, we employ a novel algorithm, which iteratively expands a Class Vector that is created through expansion by gradually aggregating the BoCWs of similar named entities appearing in other queries. We provide comprehensive experimental evidence using a commercial query log showing that our approach is competitive with existing approaches.

Community Question Answering (CQA) services, such as Yahoo! Answers and WikiAnswers, have become popular with users as one of the central paradigms for satisfying users' information needs. The task of question retrieval in CQA aims to resolve one's query directly by finding the most relevant questions (together with their answers) from an archive of past questions. However, as users can ask any question that they like, a large number of questions in CQA are not about objective (factual) knowledge, but about subjective (sentiment-based) opinions or social interactions. The inhomogeneous nature of CQA leads to reduced performance of standard retrieval models. To address this problem, we present a hybrid approach that blends several language modelling techniques for question retrieval, namely, the classic (query-likelihood) language model, the state-of-the-art translation-based language model, and our proposed intent-based language model. The user intent of each candidate question (objective/subjective/social) is given by a probabilistic classifier which makes use of both textual features and metadata features. Our experiments on two real-world datasets show that our approach can significantly outperform existing ones.

The information extraction task of Named Entities Recognition (NER) has been recently applied to search engine queries, in order to better understand their semantics. Here we concentrate on the task prior to the classification of the named entities (NEs) into a set of categories, which is the problem of detecting candidate NEs via the subtask of query segmentation.We present a novel method for detecting candidate NEs using grammar annotation and query segmentation with the aid of top-n snippets from search engine results and a web n-gram model, to accurately identify NE boundaries. The proposed method addresses the problem of accurately setting boundaries of NEs and the detection of multiple NEs in queries.

The Elo system for rating chess players, also used in other games and sports, was adopted by the World Chess Federation over four decades ago. Although not without controversy, it is accepted as generally reliable and provides a method for assessing players' strengths and ranking them in official tournaments. It is generally accepted that the distribution of players' rating data is approximately normal but, to date, no stochastic model of how the distribution might have arisen has been proposed. We propose such an evolutionary stochastic model, which models the arrival of players into the rating pool, the games they play against each other, and how the results of these games affect their ratings, in a similar manner to the Elo system. Using a continuous approximation to the discrete model, we derive the distribution for players' ratings at timetas a normal distribution, where the variance increases in time as a logarithmic function oft. We validate the model using published rating data from 2007-2010, showing that the parameters obtained from the data can be recovered through simulations of the stochastic model. The distribution of players' ratings is only approximately normal and has been shown to have a small negative skew. We show how to modify our evolutionary stochastic model to take this skewness into account, and we validate the modified model using the published official rating data.

Journal Article Search Engines: Information Retrieval in Practice Get access Mark Levene Mark Levene School of Computer Science and Information SystemsBirkbeck University of London, UK E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar The Computer Journal, Volume 54, Issue 5, May 2011, Pages 831–832, https://doi.org/10.1093/comjnl/bxq039 Published: 13 April 2010

Mark Levene; Chess Metaphors, Artificial Intelligence and the Human Mind, The Computer Journal, Volume 54, Issue 9, 1 September 2011, Pages 1560, https://doi.or

Mark Levene; Rokach Liorand Maimon OdedData Mining with Decision Trees: Theory and Applications.World Scientific (2008). ISBN-13: 978-981-277-171-1. 244 pp. Har

Abstract We describe the results of an experiment designed to study user preferences for different orderings of search results from three major search engines. In the experiment, 65 users were asked to choose the best ordering from two different orderings of the same set of search results: Each pair consisted of the search engine's original top‐10 ordering and a synthetic ordering created from the same top‐10 results retrieved by the search engine. This process was repeated for 12 queries and nine different synthetic orderings. The results show that there is a slight overall preference for the search engines' original orderings, but the preference is rarely significant. Users' choice of the “best” result from each of the different orderings indicates that placement on the page (i.e., whether the result appears near the top) is the most important factor used in determining the quality of the result, not the actual content displayed in the top‐10 snippets. In addition to the placement bias, we detected a small bias due to the reputation of the sites appearing in the search results.

When an emergency occurs within a building, it may be initially safer to send autonomous mobile nodes, instead of human responders, to explore the area and identify hazards and victims. Exploring all the area in the minimum amount of time and reporting back interesting findings to the human personnel outside the building is an essential part of rescue operations. Our assumptions are that the area map is unknown, there is no existing network infrastructure, long-range wireless communication is unreliable and nodes are not location-aware. We take into account these limitations, and propose a novel algorithm, HybridExploration, that makes use of both mobile nodes (robots, called agents) and stationary nodes (inexpensive smart devices, called tags). As agents enter the emergency area, they sprinkle tags within the space to label the environment with states. By reading and updating the state of the local tags, agents are able to coordinate indirectly with each other, without relying on direct agent-to-agent communication. In addition, tags wirelessly exchange local information with nearby tags to further assist agents in their exploration task. Our simulation results show that the proposed algorithm, which exploits both tag-to-tag and agent-to-tag communication, outperforms previous algorithms that rely only on agent-to-tag communication.

When an emergency occurs within a building, it is critical to explore the area as fast as possible in order to find victims and identify hazards. We propose Brick&Mortar, an algorithm for the autonomous exploration of unknown terrains by a team of mobile nodes, referred to as agents. Because of the unreliability and short range of wireless communications in an indoor environment we suggest that agents communicate indirectly with each other by tagging the environment. Agents have no prior knowledge of the terrain map, but are able to coordinate in order to explore a variety of terrains with different topological features. In our experimental evaluation, we show that Brick&Mortar significantly outperforms the competing algorithms, namely ants and multiple depth first search, in terms of exploration time. The observed performance benefits suggest that our algorithm is suitable for safety-critical applications that require rapid area coverage for real-time event detection and response.

The rapid advances in computer technology have, on the one hand, freed up game computing resources traditionally tied up in graphics, and, on the other, put extra demands on the computer games industry as the expectation of users for more realistic and believable non-player characters (NPCs) has been steadily rising. This and the stiff competition within the computer games industry have resulted in larger integration of artificial intelligence (AI) techniques within game engines to the degree that many games are now marketed with AI being one of their main components. In the introduction, the author states that ‘Artificial intelligence is about making computers able to perform the thinking tasks that humans and animals are capable of’. He makes it clear that the book is about the engineering side of AI, i.e. the algorithms and heuristics that produce apparent intelligent behaviour in NPCs, rather than the philosophical and psychological sides of...

The opening book is an important component of a chess engine, and thus computer chess programmers have been developing automated methods to improve the quality of their books. For chess, which has a very rich opening theory, large databases of high-quality games can be used as the basis of an opening book, from which statistics relating to move choices from given positions can be collected. In order to find out whether the opening books used by modern chess engines in machine versus machine competitions are ``comparable'' to those used by chess players in human versus human competitions, we carried out analysis on 26 test positions using statistics from two opening books one compiled from humans' games and the other from machines' games. Our analysis using several nonparametric measures, shows that, overall, there is a strong association between humans' and machines' choices of opening moves when using a book to guide their choices.

Abstract In this study, we investigate the similarities and differences between rankings of search results by users and search engines. Sixty‐seven students took part in a 3‐week‐long experiment, during which they were asked to identify and rank the top 10 documents from the set of URLs that were retrieved by three major search engines (Google, MSN Search, and Yahoo!) for 12 selected queries. The URLs and accompanying snippets were displayed in random order, without disclosing which search engine(s) retrieved any specific URL for the query. We computed the similarity of the rankings of the users and search engines using four nonparametric correlation measures in [0,1] that complement each other. The findings show that the similarities between the users' choices and the rankings of the search engines are low. We examined the effects of the presentation order of the results, and of the thinking styles of the participants. Presentation order influences the rankings, but overall the results indicate that there is no “average user,” and even if the users have the same basic knowledge of a topic, they evaluate information in their own context, which is influenced by cognitive, affective, and physical factors. This is the first large‐scale experiment in which users were asked to rank the results of identical queries. The analysis of the experimental results demonstrates the potential for personalized search.

Markov models have been widely used to represent and analyze user Web navigation data. In previous work, we have proposed a method to dynamically extend the order of a Markov chain model and a complimentary method for assessing the predictive power of such a variable-length Markov chain. Herein, we review these two methods and propose a novel method for measuring the ability of a variable-length Markov model to summarize user Web navigation sessions up to a given length. Although the summarization ability of a model is important to enable the identification of user navigation patterns, the ability to make predictions is important in order to foresee the next link choice of a user after following a given trail so as, for example, to personalize a Web site. We present an extensive experimental evaluation providing strong evidence that prediction accuracy increases linearly with summarization ability

Recently several authors have proposed stochastic evolutionary models for the growth of the Web graph and other networks that give rise to power-law distributions. These models are based on the notion of preferential attachment, leading to the “rich get richer” phenomenon. We present a generalization of the basic model by allowing deletion of individual links and show that it also gives rise to a power-law distribution. We derive the mean-field equations for this stochastic model and show that, by examining a snapshot of the distribution at the steady state of the model, we are able to determine the extent to which link deletion has taken place and estimate the probability of deleting a link. Applying our model to actual Web graph data provides evidence of the extent to which link deletion has occurred. We also discuss a problem that frequently arises in estimating the power-law exponent from empirical data and a few possible methods for dealing with this, indicating our preferred approach. Using this approach our analysis of the data suggests a power-law exponent of approximately 2.15 for the distribution of inlinks in the Web graph, rather than the widely published value of 2.1.

Abstract We report on a study that was undertaken to better understand search and navigation behavior by exploiting the close association between the process underlying users' query submission and the navigational trails emanating from query clickthroughs. To our knowledge, there has been little research towards bridging the gap between these two important processes pertaining to users' online information searching activity. Based on log data obtained from a search and navigation documentation system called AutoDoc, we propose a model of user search sessions and provide analysis on users' link or clickthrough selection behavior, reformulation activities, and search strategy patterns. We also conducted a simple user study to gauge users' perceptions of their information seeking activity when interacting with the system. The results obtained show that analyzing both the query submissions and navigation starting from query clickthrough, reveals much more interesting patterns than analyzing these two processes independently. On average, AutoDoc users submitted only one query per search session and entered approximately two query terms. Specifically, our results show how AutoDoc users are more inclined to submit new queries or resubmit modified queries than to navigate by link‐following. We also show that users' behavior within this search system can be approximated by Zipf's Law distribution.

Data warehousing is a corporate strategy that needs to integrate information from several sources of separately developed Database Management Systems (DBMSs). A future DBMS of a data warehouse should provide adequate facilities to manage a wide range of information arising from such integration. We propose that the capabilities of database languages should be enhanced to manipulate user-defined data orderings, since business queries in an enterprise usually involve order. We extend the relational model to incorporate partial orderings into data domains and describe the ordered relational model. We have already defined and implemented a minimal extension of SQL, called OSQL, which allows querying over ordered relational databases. One of the important facilities provided by OSQL is that it allows users to capture the underlying semantics of the ordering of the data for a given application. Herein we demonstrate that OSQL aided with a package discipline can be an effective means to manage the inter-related operations and the underlying data domains of a wide range of advanced applications that are vital in data warehousing, such as temporal, incomplete and fuzzy information. We present the details of the generic operations arising from these applications in the form of three OSQL packages called: OSQL_TIME, OSQL_INCOMP and OSQL_FUZZY.

Nested relations in partitioned normal form (PNF) are an important subclass of nested relations that are useful in many applications. In this paper we address the question of determining when every PNF relation stored under one nested relation scheme can be transformed into another PNF relation stored under a different nested relation scheme without loss of information, referred to as the two schemes being data equivalent. This issue is important in many database application areas such as view processing, schema integration, and schema evolution. The main result of the paper provides two characterizations of data equivalence for nested schemes. The first is that two schemes are data equivalent if and only if the two sets of multivalued dependencies induced by the two corresponding scheme trees are equivalent. The second is that the schemes are equivalent if and only if the corresponding scheme trees can be transformed into the other by a sequence of applications of a local restructuring operator and its inverse.

Functional dependencies (FDs) and inclusion dependencies (INDs) are the most fundamental integrity constraints that arise in practice in relational databases. In this paper, we address the issue of normalization in the presence of FDs and INDs and, in particular, the semantic justification for an inclusion dependency normal form (IDNF), which combines the Boyce-Codd normal form with the restriction on the INDs that they be noncircular and key-based. We motivate and formalize three goals of database design in the presence of FDs and INDs: noninteraction between FDs and INDs, elimination of redundancy and update anomalies, and preservation of entity integrity. We show that (as for FDs), in the presence of INDs, being free of redundancy is equivalent to being free of update anomalies. Then, for each of these properties, we derive equivalent syntactic conditions on the database design. Individually, each of these syntactic conditions is weaker than IDNF and the restriction that an FD is not embedded in the right-hand side of an IND is common to three of the conditions. However, we also show that, for these three goals of database design to be satisfied simultaneously, IDNF is both a necessary and a sufficient condition.

One of the main unsolved problems confronting Hypertext is the navigation problem, namely, the problem of having to know where you are in the database graph representing the structure of a Hypertext database, and knowing how to get to some other place you are searching for in the database graph. In order to tackle this problem we introduce a formal model for Hypertext. In this model a Hypertext database consists of an information repository, which stores the contents of the database in the form of pages, and a reachability relation, which is a directed graph describing the structure of the database. The notion of a trail, which is a path in the database graph describing some logical association amongst the pages in the trail, is central to our model. We define a Hypertext query language for our model based on a subset of propositional linear temporal logic, which we claim to be a natural formalism as a basis for establishing navigation semantics for Hypertext. The output of a trail query in this language is the set (which may be infinite) of all trails that satisfy the query. We show that there is a strong connection between the output of a trail query and finite automata in the sense that, given a Hypertext database and a trail query, we can construct a finite automaton representing the output of the query, which accepts a star-free regular language. We show that the construction of the finite automaton can be done in time exponential in the number of conjunctions, between the subformulas of the trail query, plus one. Given a Hypertext database and a trail query, the problem of deciding whether there exists a trail in the database that satisfies the trail query is referred to as the model checking problem. We show that, although this problem is NP-complete for different subsets of our query language, it can be solved in polynomial time for some significant special cases. Thus the navigation problem can only be efficiently solved in some special cases, and therefore in practice Hypertext systems could include algorithms which return randomized and/or fuzzy solutions.

Although there has been a vast amount of research in the area of relational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satifies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If F only satisfies the intersection property then this problem is NP-complete, as in the general case. Moreover, we show that when F either satisfies the intersection property or the split-freeness property then deciding whether an attribute is prime can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. Assume that a relation schema R is an appropriate normal form with respect to a set of FDs F. We show that when F satisfies the intersection property then the notions of second normal form and third normal form are equivalent. We also show that when R is in Boyce-Codd Normal Form (BCNF), then F is monodependent if and only if either there is a unique key for R, or for all keys X for R, the cardinality of X is one less than the number of attributes associated with R. Finally, we tackle a long-standing problem in relational database theory by showing that when a set of FDs F over R satisfies the intersection property, it also satisfies the split-freeness property (i.e., is monodependent), if and only if every lossless join decomposition of R with respect to F is also dependecy preserving. As a corollary of this result we are able to show that when F satisfies the intersection property, it also satisfies the intersection property, it also satisfies the split-freeness property(i.e., is monodependent), if and only if every lossless join decomposition of R, which is in BCNF, is also dependency preserving. Our final result is that when F is monodependent, then there exists a unique optimum lossless join decomposition of R, which is in BCNF, and is also dependency preserving. Furthermore, this ultimate decomposition can be attained in polynomial time in the size of F.

The ordered relational model is an extension of the relational model which incorporates partial orderings into data domains. We demonstrate that the ordered relational model is suitable for modelling advanced applications involving tree-structured information, incomplete information and temporal information. We describe OSQL, which is an extension of SQL for the ordered relational model, and show that OSQL combines the capabilities of standard SQL with the power of user-defined semantic orderings. The syntax of OSQL is a minimal extension of SQL and thus it should be easy for current SQL users to adapt to OSQL. Although it is a minimal extension, OSQL allows the users to formulate a wide range of queries, such as fuzzy or temporal, which are either very awkward or impossible to formulate in standard SQL. We also discuss the experimental implementation of OSQL and the further development of the capabilities of OSQL via the notion of an OSQL package in databases, which utilises semantic orderings to define the set of core operations associated with a specific application.

We extend functional dependencies (FDs), which are the most fundamental integrity constraints that arise in practice in relational databases, to be satisfied in an imprecise relation. The problem we tackle is the following: given an imprecise relation r over a relation schema R and a set of FDs F over R, what is the most precise approximation of r, which is also consistent with respect to F. We formalize the notion of an imprecise relation by defining tuple values to be sets of values rather than just single values as is the case when the information is precise. We interpret each value in such a set as being equally likely to be the true value. This gives rise to equivalence classes of equally likely values thus allowing us to define the merge of an imprecise relation r which replaces values in r by their equivalence class. We also define a partial order on merged imprecise relations leading to the notion of an imprecise relation being less precise than another imprecise relation. This partial order induces a lattice on the set of merged imprecise relations. An imprecise relation is consistent with respect is consistent with respect to a set of FDs F if it satisfies F. Satisfaction of an FD in an imprecise relation is defined in terms of values being equally likely rather than equal. We show that Armstrong's axiom system is sound and complete for FDs being satisfied in imprecise relations. We redefine the chase procedure for an imprecise relation r over R as a means of maintaining consistency of r with respect to F. Our main results is that the output chase (r,F) of the chase procedure is the most precise approximation of r with respect to F in the following sense. It is shown to be the join of all consistent imprecise relations s with respect to F in the following sense. It is shown to be the join of all consistent imprecise relations s such that s is a merged imprecise relation that is less precise than r. It is also shown that chase (r,F) can be computed in polynomial time in the sizes of r and F.

We present an alternative approach to that of Chandra and Harel [5] and Abiteboul and Vianu [1] in considering computable database queries, which are mappings from sets of records to sets of records. In particular, we view a computable database query as being realised via a Turing-computable mapping from strings to strings and an encoding, which encodes the input set of records into an appropriate string. An encoding of a set of records consists of two components: an ordering function, which orders the records in a set as well as the values of each record in the set, and an isomorphism, which maps the values in the records of the set to strings. An important class of encodings, called free encodings, whose isomorphism has the same semantics as the identity mapping on record values, is also defined. Our analysis of computable database queries elucidates the notion of a computable database query by dealing with the problem of how a database language can be implemented on a standard Turing machine that does not cater directly for mappings from sets of records to sets of records. We carry out our analysis by categorising computable database queries into subclasses and by establishing the relationships that exist amongst these subclasses. We also investigate an equivalence relation on computable database queries; two computable database queries are related if they are realised via the same Turing-computable mapping, say δ. We prove the following interesting result regarding the cardinality of the equivalence class of a computable query with respect to the said equivalence relation: either δ does not realise any computable query, or δ realises exactly one computable query, or δ realises a countably infinite set of computable queries. Our final result shows that, by adding membership queries to the class of encoding-independent computable queries, the closure of the resulting extended class under composition of mappings is the set of all isomorphism-independent computable queries.

Currently, database researchers are investigating new data models in order to remedy the deficiencies of the flat relational model when applied to nonbusiness applications. Herein we concentrate on a recent graph based data model called the hypernode model. The single underlying data structure of this model is the hypernode which is a digraph with a unique defining label. We present in detail the three components of the model, namely its data structure, the hypernode, its query and update language, called HNQL, and its provision for enforcing integrity constraints. We first demonstrate that the said data model is a natural candidate for formalising hypertext. We then compare it with other graph based data models and with set based data models. We also investigate the expressive power of HNQL. Finally, using the hypernode model as a paradigm for graph based data modelling, we show how to bridge the gap between graph based and set based data models, and at what computational cost this can be done.>

Three recent trends in database research are object-oriented and deductive databases and graph-based user interfaces. We draw these trends together in a data model we call the Hypernode Model. The single data structure of this model is the hypernode , a graph whose nodes can themselves be graphs. Hypernodes are typed, and types, too, are nested graphs. We give the theoretical foundations of hypernodes and types, and we show that type checking is tractable. We show also how conventional type-forming operators can be simulated by our graph types, including cyclic types. The Hypernode Model comes equipped with a rule-based query language called Hyperlog, which is complete with respect to computation and update. We define the operational semantics of Hyperlog and show that the evaluation can be performed efficiently. We discuss also the use of Hyperlog for supporting database browsing, an essential feature of Hypertext databases. We compare our work with other graph-based data models—unlike previous graph-based models, the Hypernode Model provides inherent support for data abstraction via its nesting of graphs. Finally, we briefly discuss the implementation of a DBMS based on the Hypernode Model.

The nested relational model extends the flat relational model by relaxing the first normal form assumption in order to allow the modeling of complex objects. Much of the previous work on the nested relational model has concentrated on defining the data structures and query language for the model. The work done on integrity constraints in nested relations has mainly focused on characterizing subclasses of nested relations and defining normal forms for nested relations with certain desirable properties. In this paper we define the semantics of nested relations, which may contain null values, in terms of integrity constraints, called null extended data dependencies , which extend functional dependencies and join dependencies encountered in flat relational database theory. We formalize incomplete information in nested relations by allowing only one unmarked generic null value , whose semantics we do not further specify. The motivation for the choice of a generic null is our desire to investigate only fundamental semantics which are common to all unmarked null types. This lead us to define a preorder on nested relations, which allows us to measure the relative information content of nested relations. We also define a procedure, called the extended chase procedure , for testing satisfaction of null extended data dependencies and for making inferences by using these null extended data dependencies. The extended chase procedure is shown to generalize the classical chase procedure, which is of major importance in flat relational database theory. As a consequence of our approach we are able to capture the novel notion of losslessness in nested relations, called herein null extended lossless decomposition . Finally, we show that the semantics of nested relations are a natural extension of the semantics of flat relations.

To date most previous approaches to incomplete information within the relational model depend on the specific semantics of the null types incorporated into this model. Herein we propose a model for incomplete information in nested relational databases which is independent of the semantics of the null types pertaining to incomplete information. Thus, the proposed model, called the nested relation type (NRT) model, allows, in addition to system-defined null types, user-defined null types. The NRT model extends the nested relational model by incorporating a form of built-in inheritance. This allows us to define a partial order between nester-relations types and a partial order between the data values of these types. By utilizing these partial orders, we define an instance, over a NRT, to be incomplete when its information content may increase. In addition, we define an algebra for the NRT model, called the NRT algebra, which is shown to supersede known algebras for relations with nulls and for nested relations by showing faithfulness to these algebras. We then investigate the monotonicity of the operators of the NRT algebra, which allows us to predict how increasing or decreasing the information content of the instances in the database affects the information content of the user's view, which is constructed from an algebraic expression over the instances in the database. Finally, we enhance the expressive power of the NRT-algebra with a least fixpoint operator in order to allow users to pose recursive queries.