Tanja Blascheck

Lindsay Macdonald Vermeulen

Jo Vermeulen

Charles Perin

Wesley Willett

Thomas Ertl

Sheelagh Carpendale

Exploration Strategies for Discovery of Interactivity in Visualizations

Keywords: Discovery, Visualization, Open Data, Evaluation, Eye Tracking, Interaction Logs, Think-Aloud, F

published or not. The documents may come

INTRODUCTION

Many governments worldwide strive to make their data available online in open formats. This open data movement has been pursued as a political priority in countries such as Canada [1], the United Kingdom [START_REF]Data gov uk -opening up government[END_REF], Germany [START_REF] Finanzbeh Örde | Govdata -Das Datenportal f ür Deutschland[END_REF], and the European Union as a whole [START_REF]Creating impact for an eunion 2015 -the visby declaration[END_REF]. This data is typically only available in raw formats like spreadsheets and CSV files [START_REF] Barbosa | Structured open urban data: Understanding the landscape[END_REF], making it hard for the general public to access and explore. Moreover, citizens often lack the means or skills to process, visualize, and understand the data [START_REF] Boy | Suggested interactivity: Seeking perceived affordances for information visualization[END_REF].

A popular way of making open data more accessible is via web-based interactive visualizations. Some examples include the OECD Better Life Index [START_REF]Better life index[END_REF], the NCDRisc Height Map [START_REF] Ncd Risc | Height -evolution of adult height over time[END_REF], the Crime Maps of UK cities [START_REF]Crime map[END_REF], or the Live London Underground Map [START_REF] Somerville | London underground network[END_REF]. However, it remains unclear how the general public makes use of these visualizations, and whether citizens are able to discover how to interact with them. In particular, recent work by Boy et al. [START_REF] Boy | Suggested interactivity: Seeking perceived affordances for information visualization[END_REF] suggests that viewers often not notice the functionality in interactive visualizations. To date, visualization research has not deeply explored how viewers discover interactive functionality. This knowledge gap makes it difficult to develop data visualizations that are accessible for the general public.

• T. Blascheck is with the University of Stuttgart, Germany and University of Calgary, Canada, E-mail: tanja.blascheck@vis.uni-stuttgart.de • L. MacDonald Vermeulen is with the Alexandra Institute, Denmark and the University of Calgary, Canada • J. Vermeulen We contribute a detailed mixed-methods study from which we identify a variety of exploration strategies that people use when discovering how to interact with a visualization. We report the results from our observations of 24 participants as they used their own methods to discover the functionality of an open data visualization on a government website dedicated to providing information on energy data.

We collected and integrated eye movement data and interaction logs as well as video and audio recordings to extract exploration strategies that participants employed to discover the visualizations' functionality. These exploration strategies are: eyes only, reading text, opportunistic interactions, entry points, structural interactions, permutation interactions, and leveraging the familiar. Some of these exploration strategies have been documented previously, including eyes only [START_REF] Spence | Information visualization[END_REF], reading text, opportunistic interactions [START_REF] De Bruijn | Serendipity within a ubiquitous computing environment: A case for opportunistic browsing[END_REF], permutation interactions [START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF], and choosing personally relevant entry points [START_REF] Bates | The design of browsing and berrypicking techniques for the online search interface[END_REF]. However, additional exploration strategies we observed shed new light on how people explore interactive visualizations. These include using the structure of available controls for sequential search and leveraging the familiar by comparing a familiar view and a new view to discover functionality.

Interactivity can be a powerful tool to enable visual exploration and insight generation [START_REF] Heer | Interactive dynamics for visual analysis[END_REF]. Despite the ubiquity of interactive visualizations, it remains a challenge for people who create visualizations to determine when interaction is appropriate, and how people discover functionality when it exists. We investigate strategies people use to discover the functionality of a specific set of visualizations of energy data. While these are only a subset of the broad and diverse space of interactive visualization techniques, our study presents a first step towards a better understanding of how people discover a visualization's functionality. Based on our exploration strategies, we contribute suggestions on how to design for discovery by inviting interaction, pro-viding entry points, using spatial organization, combating oscillation, supporting transitions, and scaffolding complex interactions.

RELATED WORK

Our work is related to existing research in two main areas: proliferation of open data visualization and research examining the discovery of functionality in visual interfaces.

Proliferation of Open Data Visualizations

Many countries and institutions are increasingly interested in making government data open and accessible to citizens. However, for most non-experts, making sense of huge and often technical public datasets can be difficult. For example, most institutions only make open data available to the general public as raw tabular data files [START_REF] Barbosa | Structured open urban data: Understanding the landscape[END_REF], for which few citizens have the tools or expertise to examine. Creating interactive visualizations that enable analysis by the general public poses an important challenge [START_REF] Hendler | Data integration for heterogenous datasets[END_REF]. Research systems such as ManyEyes [START_REF] Viégas | ManyEyes: a site for visualization at internet scale[END_REF] and commercial tools like Tableau Public [START_REF] Tableau | Tableau public[END_REF] have provided generic mechanisms for visualizing public data online. While these represent a great step forward as general purpose tools, they offer little specific help for introducing novices to either the data, the visualizations, or their interactive functionality. An increasingly popular alternative is to produce tailored interactive visualizations that present specific types of public data in ways that require less expertise. Interactive visualizations like Wattenberg's NameVoyager and BookVoyager [START_REF] Wattenberg | Designing for social data analysis[END_REF] and Heer et al.'s sense.us [START_REF] Heer | Voyagers and voyeurs: Supporting asynchronous collaborative information visualization[END_REF], along with more recent examples like the OECD Better Life Index [START_REF]Better life index[END_REF] feature tailored interactive visualizations of individual datasets intended for consumption by non-experts. However, the visualization community still knows little about how to craft these kinds of interactive visualizations for the general public in ways that can reliably enable novices to discover the functionality.

Discovery of Functionality in Visual Interfaces

Interactive visualizations face concerns about discovery and accessibility of functionality, especially when intended for novices. Although prior work has investigated graphical literacy and comprehension [START_REF] Friel | Making sense of graphs: Critical factors influencing comprehension and instructional implications[END_REF] for static charts, little is known about how novices approach more complex interactive visualizations. As a result, interactive open data visualizations, like Slingsby et al.'s Place Survey [START_REF] Slingsby | Designing an exploratory visual interface to the results of citizen surveys[END_REF], have put considerable emphasis on designing for public accessibility. However, the results of these efforts have been mixed. In their own analyses, Slingsby et al. found that novices often failed to understand and use the more advanced functionality, even when they were explicitly introduced to it via tutorials. Perin et al.'s interactive ranking tables for soccer [START_REF] Perin | À Table! Improving Temporal Navigation in Soccer Ranking Tables[END_REF] -also designed with novices in mind -suffered from similar issues. While an introduction to the soccer visualizations explained the novel interaction techniques, novices often still failed to discover their functionality or use them when examining the data.

Recent work by Boy et al. [START_REF] Boy | Suggested interactivity: Seeking perceived affordances for information visualization[END_REF] suggested a number of potential exploration strategies for revealing interactive functionality to novices. In a study of visualizations from the OECD's Better Life Index [START_REF]Better life index[END_REF], Boy et al. tested three different suggested interactivity techniques, including overt animations that used feedforward [START_REF] Vermeulen | Crossing the bridge over Norman's gulf of execution: Revealing feedforward's true identity[END_REF] to highlight interactive functionality. Their findings indicate that strong visual emphasis can encourage novice awareness of specific functionality in interactive visualization tools. However, the overall process by which novices discover functionality of new interactive visualizations still remains largely unstudied. This makes it difficult for designers to know which interaction techniques to include for a given visualization and how to best highlight them. With this in mind, our work explicitly examines how the general public uncovers novel visualizations and describes exploration strategies they use to make sense of unfamiliar interfaces.

As interactive visualizations are essentially interfaces, related work in the field of human-computer interaction on the discovery of functionality is relevant as well. Discovery of functionality is one of the most important characteristics of good interface design. Norman stresses that designers must always be cognizant of whether it is possible for a person "to even figure out which actions are possible and where and how to invoke them" [25, pg. 3]. In fact, usability guidelines often suggest that all functionality and possible actions should be immediately visible in an interface [START_REF] Norman | The Design of Everyday Things: Revised and Expanded Edition[END_REF]. As a result, interfaces for novices tend to be heavily reliant on visual search [START_REF] Cockburn | Supporting novice to expert transitions in user interfaces[END_REF]. Supporting visual search often involves removing features and suppressing more advanced functionality, with the goal of reducing search time and improving novice performance. However, this can lead to tools that fail to accommodate experts, and give novices little room to grow or to investigate more deeply. Ideally, an interactive system should support discovery of functionality for both novices and experts, encouraging awareness and understanding of its functionality [START_REF] Grossman | A survey of software learnability: metrics, methodologies and guidelines[END_REF] while also facilitating novice-to-expert transitions [START_REF] Cockburn | Supporting novice to expert transitions in user interfaces[END_REF].

In contrast to prior research, which has primarily used interaction logs to evaluate discovery of functionality in online interactive visualizations (e.g., [START_REF] Boy | Suggested interactivity: Seeking perceived affordances for information visualization[END_REF], [START_REF] Perin | À Table! Improving Temporal Navigation in Soccer Ranking Tables[END_REF], [START_REF] Vuillemot | Sports Tournament Predictions Using Direct Manipulation[END_REF]), our study combines log data with eye movement data, video and audio recordings to produce detailed records of the discovery process.

STUDY: DISCOVERING VIS INTERACTIONS

To improve our understanding of how the general public discovers the interactions available in a visualization, we conducted a study of an interactive open data visualization on a government website dedicated to energy data.

We used a controlled environment and collected eye movement data and interaction logs as well as video and audio recordings. While eye tracking has been used to evaluate visualizations in general [START_REF] Burch | Evaluation of traditional, orthogonal, and radial tree diagrams by an eye tracking study[END_REF]- [START_REF] Netzel | Comparative eye tracking study on node-link visualizations of trajectories[END_REF] and to specifically evaluate how novices remember visualizations [START_REF] Bateman | Useful junk?: The effects of visual embellishment on comprehension and memorability of charts[END_REF], [START_REF] Borkin | Beyond memorability: Visualization recognition and recall[END_REF], it has not previously been used to tease out the discovery of functionality in a novel visualization. Using eye movement data makes it possible to examine which areas of the visualization viewers attend to and how their attention switches during a task. By contrast, usability studies tend to rely heavily on interaction logs, often supplemented by think-aloud protocols [START_REF] Dou | Recovering reasoning processes from user interactions[END_REF]- [START_REF] Pohl | How to Investigate Interaction with Information Visualisation: An Overview of Methodologies[END_REF] which can provide insight into participants' thought processes [START_REF] Ericsson | Protocol Analysis: Verbal Reports as Data[END_REF], [START_REF] North | Toward measuring visualization insight[END_REF]. Combining these methods and collecting a more diverse set of data allowed us to analyze participants' actions both in terms of attention and more explicit actions. This rich data provides a better understanding of the barriers participants faced and made it possible to identify specific exploration strategies that participants employed to discover the visualizations' interactive functionality.

While there are trade-offs associated with conducting a controlled lab study, triangulating data from a range of different sources allowed us to extract strategies participants used and examine them in detail. In Section 8, we reflect further on the limitations of our approach.

The Interactive Visualization Website

We asked participants to explore a set of interactive visualizations: "Exploring Canada's Energy Future" created by Canada's National Energy Board (NEB) [START_REF]Exploring canada's energy future[END_REF]. Like some of the other open data efforts mentioned previously, the NEB created these interactive visualizations to help both the general public and data experts examine data that was previously published in a less accessible format. The visualization website consists of a START PAGE shown in Figure 2, as well as four interactive views shown in Figure 1, each highlighting a different kind of energy data. The STACKED BAR CHART (Figure 1 A) shows energy demand, electricity generation, oil, or gas production by region. The STACKED AREA CHART (Figure 1 B) depicts the energy demand All four views use a similar layout with groups of controls on the left, a chart representing the energy data on the right, and one or two axes. Viewers can switch between views using the menu bar at the top. The menu bar also includes help ( ) and description ( ) buttons, which provide more information about each view and how to use it. Question marks ( ) next to each group provide more

REGION REGION REGION A B C
Fig. 3. The sliding rail supports reordering of elements in the views, here represented by two-letter codes of regions from Canada. A region is selected (A) and dragged to a new position (B), which causes other regions on the rail to make space for the region that is being dragged. When the region is dropped, the reordering is shown in the chart (C).

information specific to the associated interactive controls.

In addition to standard buttons and check boxes, the interface also includes two unconventional interface widgets. Both the STACKED BAR CHART (Figure 1 A) and STACKED AREA CHART (Figure 1 B) include a sliding rail control (Figure 3). By clicking the boxes on the sliding rail, viewers can hide and show related information in the chart. Viewers can also drag and drop boxes along the sliding rail to reorder the series as shown in Figure 3. The BUBBLE CHART (Figure 1 C) includes an interactive timeline that can be used to play back changes in the data over time.

Participants

In order to examine a diverse cross-section of the general public, we recruited three different types of participants: novice, savvy, and experts. The novice group consisted of i) students who were not studying a computer science-related discipline and ii) non-students who had never worked in the energy sector. The group of savvy participants consisted of computer science students. We recruited this group of participants because their technical background makes them experts in using interfaces despite being novices in the field of energy data. Finally, the expert group consisted of participants with experience in the energy sector (average 8.38 years experience; min 8 months, max 35 years). We recruited 8 participants for each group via posters, mailing lists, and word-of-mouth. Due to a variety of technical issues including poor English skills and hardware malfunctions that made the data unusable, we dropped and replaced 6 of the initial participants to obtain the final set of 24 participants (8 per group), which we report in this paper. Fourteen of the 24 participants were female and 10 were male. Fifteen participants were students. Six participants were 18-24 years old, 13 were 25-34 years old, 3 were 35-44 years old, and 2 were 55-64 years old. All participants had normal or corrected-to-normal vision. We also asked participants about their knowledge of energy issues -21 stated they had some knowledge. Fourteen also noted that they were familiar with infographics -6 on the web, 13 in the media (multiple answers were possible).

Equipment and Set Up

To record eye movement and interaction data, we used a Tobii X2-60 compact eye tracker (accuracy 0.4 degrees, precision 0.34 degrees) on a Dell XPS 27 all-in-one machine (27" screen with a resolution of 2560 ⇥ 1440 px) running Windows 8.1. We recorded the eye movement data at 60 Hz. We aggregated gaze points using the IV-T classifier with a velocity threshold of 30 degrees/second, and a window length of 20 ms. We merged adjacent fixations up to a maximum time between fixations of 75 ms and a maximum angle between fixations of 0.5 degrees and discarded fixations with a duration below 60 ms. We used an additional video camera placed behind the participant to capture the participant and the screen.

We ran our study using an Internet Explorer 11.0.33 window with a size of 1235 ⇥ 910 px positioned 520 px from the left of the screen and 210 px from the top. The size of the browser window was constrained to maintain a consistent view size. We conducted the study in a room isolated from outside distraction. To ensure constant illumination, we closed the blinds and switched on the room light.

Study Procedure

We asked participants to investigate the Canada's Energy Future website and the four views associated with it. The experimenter did not provide participants with any explanation of the views. Participants could only use the information available on the website. The experimenter instructed the participants to freely explore the views and to talk about their thought process as they did so. We removed the header and footer of the website to eliminate distractions, to focus participants' attention on the views, to maintain consistency in view size, and to avoid scrolling that could disrupt the eye tracker.

At the beginning of each trial, an experimenter asked the participants to sign a consent form and fill out a demographic questionnaire. Participants then had to pass a visual acuity test utilizing a Snellen chart and a color vision test. We checked for color blindness and red-green blindness using nine of the 24 Ishihara test plates [START_REF] Ishihara | Test for colour-blindness[END_REF]. Next, we used a nine-point calibration procedure to calibrate the eye tracker. When the study was completed, participants filled out a NASA TLX questionnaire and a questionnaire for rating the views. At the end of the session, participants could make final remarks and received $20 for their participation.

Data Collection

We collected eye movement data, interaction logs, and the time participants took to explore the interactive views. We also recorded the screen and audio using the eye tracker's integrated camera, and utilized a second camera to capture audio and video of participants. In addition, we collected demographic information, NASA TLX, and viewrating questionnaires. During the study, the experimenter also had a checklist to record each interactive function the participants used. We provide the complete data collected during the study on a supplemental website 1 .

PROCESSING OUR STUDY DATA

To analyze our collected data, we first define areas of interest. Then, we describe three eye tracking visualizations we used for our analysis -attention maps, scanpaths, and AOI timelines. Last, we summarize the numerical data collected in the study.

1. http://innovis.cpsc.ucalgary.ca/supplemental/ Exploration-Strategies/

Defining Areas of Interest

We analyzed the eye movement data using areas of interest (AOIs) for each view. We define AOIs based on the visual structure of the website (i.e., the control groups, chart, axes, and menus). Figure 4 shows the AOIs we defined for each view. We used one AOI for the chart (chart AOI), one AOI for each group of interactive controls including a menu AOI, main selection AOI, scenario AOI, unit AOI, region AOI, and source AOI. Since the controls vary according to the view and the data, the main selection AOI is different in each view. It contains the controls for choosing the energy type in the STACKED BAR CHART and LINE CHART, for choosing the sector for the STACKED AREA CHART, and for switching between a region and source option for the BUBBLE CHART. We used AOIs for the numerical parts of the views: the horizontal (time axis AOI) and the vertical axis (value axis AOI). We also refer to the horizontal time slider in the BUBBLE CHART as a time axis AOI.

As part of our analysis, we grouped these AOIs into three high-level groups which are shown in Figure 4: the controls group (shown in orange), the chart (shown in purple), and the numbers group (shown in blue). Although the individual AOIs are specific to the views in our study, the AOI groups reflect classes of elements common to most visualizations. The majority of interactive visualizations have one or more chart elements as well as a set of interactive controls. Furthermore, most visualizations feature numbers, either as axes or as temporal interaction controls.

Eye Movement Visualizations

We used three types of eye movement visualizations: attention maps, scanpaths, and AOI timelines.

Attention maps, like the one in Figure 5, represent the distribution of a participant's attention on top of a stimulus. Our attention maps use a heat map metaphor where darker red indicates a higher amount of sustained attention while lighter red shows less attention. Areas without attention are not color coded. Attention maps are useful for identifying which parts of a view received participants' attention and which ones did not.

Scanpaths, like those in Figure 6, depict the sequence of fixations on top of a view. Each circle represents one fixation and lines connect consecutive fixations. The circle radius encodes fixation duration. Scanpaths are useful for revealing the order in which participants focus on each element.

AOI timelines [START_REF] Blascheck | VA 2 : A visual analytics approach for evaluating visual analytics applications[END_REF], like the one in Figure 7, show fixations and saccades -rapid eye movements between fixations -for an individual participant in a single timebased view. We created five AOI timelines per participant: one for the START PAGE and one for each of the four views. In each AOI timeline, individual AOIs are indicated by horizontal lines. The background of the AOI timeline is colored according to AOI group: purple for the chart (at the top), orange for the controls (in the middle), and blue for the numbers (at the bottom). The gray path represents the sequence of fixations of a participant. The longer the path stays in the same AOI (horizontal segments), the longer the fixation. Dotted segments of the path represent fixations that are not assigned to any AOI. These are times when, for instance, the participant may have looked away from the screen. White circles indicate an interaction such as a mouse click, while black circles mean that a participant opened or closed the help menu. Vertical gaps indicate the times at which a participant temporarily switched to another view and later returned to work with the current one. AOI timelines are particularly useful for examining detailed temporal information for individual participants.

Coding Process

In our coding process, we drew upon the eye tracking visualizations as well as the video and audio recordings to identify exploration strategies that participants applied when exploring the views. First, one author developed an open coding scheme based on observations of eye movement visualizations and videos from several participants. A second author then verified this pass. Next, a group of four authors (including the initial two) discussed, refined, and presented the coding scheme to the rest of the research team. The team then refined these through a series of iterations until they reached consensus on a set of 10 exploration strategies. Then, using poster-sized printouts of the AOI timeline visualizations, one author coded the data from all 24 participants to identify all instances of these strategies. The larger group then discussed the results of this process and used axial coding to regroup, consolidate, and rename the strategies to arrive at a final set of seven. We provide the AOI timelines for all five views and all 24 participants on a supplemental website 1 .

Times, Fixations, and Interactions

We now summarize the data we collected in our study before explaining the exploration strategies that we identified. On average our participants took approximately 15 minutes to finish their initial exploration of the interface (M = 920s, SD = 478s). During this time, every participant examined all four views. Figure 8 shows all participants' fixations across the four views. Although we recruited a variety of participants from different backgrounds and assigned them to three groups (novice, savvy, and expert), we observed no clear difference between these groups in terms of total time, fixation duration, or total number of interactions (see Figure 9 for details). For example, participants from the expert group had both the longest and the shortest times.

In general, for the timings shown in Figure 8, participants from all three groups were quite evenly spread across the time variations. We therefore collapse the groups for the rest of the analysis in this paper. Overall, 19 of 24 participants started with the STACKED BAR CHART, 4 participants (P04, P08, P09, P14) started with the BUBBLE CHART, and P24 jumped quickly between several views before returning to the STACKED BAR CHART. Eleven participants (P06, P07, P08, P12, P13, P15, P16, P17, P18, P19, P20) visited all four views in sequence, without returning to any previous view for more than a few seconds.

Figure 10 shows participants' total fixation time for the four views. Each vertical bar represents one participant's total fixation time for that view. Participants generally spent the most total time on the BUBBLE CHART, followed by the STACKED BAR CHART, the STACKED AREA CHART, the LINE CHART, and the START PAGE. Figure 11 breaks down the percentage of the total fixation time spent on the three AOI groups. When examining the STACKED BAR CHART and the STACKED AREA CHART participants spent the most time focusing on the controls. For the BUBBLE CHART, participants spent the most time on the chart. For the LINE CHART, participants spent a similar amount of time on the chart and on the controls. Participants spent less time looking at the numbers than the chart or controls in all four views. The largest difference between chart and controls occurred in the STACKED AREA CHART, where participants spent more time looking at the controls, and the BUBBLE CHART, where participants spent more time looking at the chart.

Across all views, we observed a noticeable pause before participants started interacting. Figure 12 shows the time to first interaction, the time it took participants to start interacting with each view. This delay to interact is interesting because during this gap the participants spent their time scanning visually (cf. Section 5.1). The average time to first interaction was longest for the STACKED BAR CHART, followed by the BUBBLE CHART, then the STACKED AREA CHART, and the LINE CHART. Time to first interaction varied considerably for the BUBBLE CHART.

EXPLORATION STRATEGIES

We identified seven exploration strategies (ES) that participants employed to discover functionality in the views: eyes only (ES eyes only ), reading text (ES text ), opportunistic interactions (ES opportunitistic ), entry points (ES ), structural interactions (ES structure ), permutation interactions (ES permutations ), and leveraging the familiar (ES leverage ). Our findings both highlight the use of novel strategies and confirm the use of relatively well-known exploration strategies. Additionally, the presented exploration strategies, their prevalence, and the ways in which they were combined, are contributions in themselves and shed new light on how people discover interactive visualizations. Icons next to each exploration strategy indicate the combination of data sources that we used to identify it: eye movement data ( ), interaction data ( ), and think-aloud data ( ).

ES eyes only : Eyes Only ( , )

When using ES eyes only , participants visually examined a view, but did not interact with it. By scrutinizing a view while preserving its current state, participants engaged in what Spence [11, p. 141] calls passive interaction -interactions that have no physical component, but constitute a complex visual and cognitive performance during which a viewer's mental model changes. In our study, participants usually employed this exploration strategy when they were first exposed to a view or immediately after completing a sequence of interactions that altered the view.

To extract occurrences of ES eyes only we examined the eye movement data and interaction logs to identify all time spans longer than five seconds that did not include any interaction. Within each time span, we calculated the total dwell time for each AOI group, using the AOIs defined in Section 3.5. The dwell time is the sum of all durations of fixations assigned to any AOI in a group. This resulted in three sub-strategies of ES eyes only differentiated by the AOI group the participants focused most of their attention on. We observed 1102 total occurrences of this pattern across the chart (691 instances), controls (385 instances), and numbers AOI groups. All 24 participants used ES eyes only at least once while focusing on the chart (showing scan patterns similar to Figure 6 A) and on the controls (showing scan patterns similar to Figure 6 B). Thirteen participants also used ES eyes only when examining the numbers (showing scan patterns similar to Figure 6 C).

ES text : Reading Text ( , )

Most participants also read the documentation provided by the visualization designers to help them understand a new view. The attention map in Figure 5 shows a participant reading the entry text. ES text is slightly more interactive than ES eyes only , because aside from the entry text on the START PAGE, reading the available documentation required the participants to select a help button.

Most participants used the help functions by accessing the website description ( ), the main help button from the menu bar across the top of the page ( ), and the contextual help available for each control group ( ). Nineteen participants used ES text a total of 170 times.

ES opportunitistic : Opportunistic Interactions ( , )

In our study, when participants interacted opportunistically, they typically selected an arbitrary option from any group of controls, examined the chart to assess what changes their action caused, and then relatively rapidly moved on to a different control to repeat this process. Participants appeared to lack a clear rationale for the decision of which controls to interact with. Opportunistic interactions are characterized by being free-ranging, relatively effortless, and usually not carefully planned [START_REF] De Bruijn | Serendipity within a ubiquitous computing environment: A case for opportunistic browsing[END_REF].

Figure 13 shows part of an AOI timeline for a participant interacting opportunistically. In this example, the participant first changed the year on the time axis, then selected a scenario, before selecting two different sources. To assess the frequency of opportunistic interactions we coded all instances in which a participant interacted with controls from multiple different groups in sequence. All 24 participants used this strategy at least once, for a total of 351 occurrences.

ES entry : Entry Points ( , )

When using ES entry , participants started their investigation with a view by gravitating towards familiar factors in the controls, the charts, or the content. These familiar factors served as entry points into the view. Several participants noted looking at the geographic region they grew up in or currently live in. Some examples include: "[...] I guess but maybe that's just because we live in Alberta interested in my region, that is why I clicked this [...]" (P07). This selection of factors of personal interest corresponds strongly to Bates' description of berrypicking -conducting exploration "by a series of selections of individual references and bits of information at each stage of the ever-modifying search" [START_REF] Bates | The design of browsing and berrypicking techniques for the online search interface[END_REF]. To count the occurrences of participants using entry points, we listened to the audio recordings for any indication of a statement referring to personal information. We also coded all selections of "Alberta" as an entry point, because the study took place in Alberta, Canada. Thirteen participants explored views by selecting familiar entry points, for a total of 36 occurrences.

ES structure : Structural Interactions ( , )

When using structural interactions, participants leveraged the structure that is visually apparent in the interface. For example, a participant would choose one control group and then iterate over all of the available options in that group. Participants often followed the spatial organization of the controls -for example, moving from top to bottom through the control group. Although they vary from view to view, the control panels contain groups of controls that are related by icon style as well as by spatial proximity. Figure 14 shows a section of an AOI timeline from a participant who used this approach. Here, the participant iteratively tested all options in the main selection control group, always oscillating between the chart and the controls to observe changes. After finishing with the main selection control group, the participant then explored the options in the scenarios group. All 24 participants used structural interactions at least once, for a total of 644 occurrences.

ES permutations : Permutation Interactions ( , )

Permutation interactions are a careful, methodical approach that reveals some understanding of the relationship between control groups. Similar to a comparative measure or dimension walk [START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF], participants would select one control item in a given control group (A) and then take a different control group (B) and iterate through all the options in B. Then, they would return to A, select a new item, and iterate through all the options in B again. We call this permutation interaction because in this manner participants could ensure that they had seen all permutations and combinations of the two groups. Figure 15 depicts a part of an AOI timeline for a participant using this method. After selecting an option in the main selection group, the participant selected all options from the scenarios. After seeing how the scenarios had changed for the first main selection option, the participant selected the next main selection item and again investigated each of the scenarios. Permutation interactions were the least used exploration strategy: 6 participants used it at least once, for a total of 7 occurrences. Participants used the strategy the most with the BUBBLE CHART, investigating how different options changed over time using the interactive time axis. Participants also used permutation interactions to try different combinations of regions and sources.

ES leverage : Leveraging the Familiar ( , , )

When using the ES leverage , participants used their understanding of one view to learn about another view. We saw two variations of ES leverage in our study. Sometimes participants would switch to a new view, then quickly revisit the previous view in order to understand the differences between the two views. In other cases, participants would realize that something in their current view was different from what they had seen in a prior view and would return to that view to compare it with the current view. Figure 16 shows how a participant moved back and forth between the STACKED BAR CHART and STACKED AREA CHART in order to compare them. Using ES leverage , participants were able to begin to understand the functionality of a new view by leveraging what they knew about the views they had already visited. Overall, 10 participants used ES leverage at least once for a total of 60 occurrences.

EXPLORATION STRATEGIES IN CONTEXT

Throughout our study, we found that the exploration strategies participants preferred differed from view to view. Figure 17 shows the number of participants who used a given exploration strategy for each view. This suggests that the design of a view can evoke certain exploration strategies.

Exploration Strategies by Views

On three of the four views (STACKED BAR CHART, STACKED AREA CHART, LINE CHART), participants focused more on the controls than on the chart (see also Section 4 and Figure 11). Although the chart takes up most of the space in each view and communicates the most information, the controls serve as interactive legends and participants frequently returned to them to verify the current selection and compare color encodings. The sole exception to this was the BUBBLE CHART, in which more participants focused on the chart than on the controls. This is almost certainly due to the fact that the BUBBLE CHART was the only view in which the chart itself was interactive. In this view, it was possible to access data values for different regions or sources by mousing over the corresponding bubbles in the chart. Participants also focused more on numbers when using the BUBBLE CHART than they did on the other three views. This may be due to the fact that the timeline for this view was interactive and participants often focused on it when triggering those interactions. Overall, however, focusing on the numbers remained the least-used of the three ES eyes only sub-strategies.

ES text was also used frequently, with 20 of our participants employing it at some point. Participants used this strategy across all views, with the most use on the BUBBLE CHART. Heavy use of the help may be a sign that some functionality was not easily discoverable. However, participants seemed to benefit from the localized help available for each control group, as it allowed them to quickly obtain explanations and information about those particular controls. Participants also used ES text extensively on the START PAGE. While we expected participants to only briefly look at this page and quickly select a view, 22 participants read the entire introductory paragraph before proceeding. The attention map in Figure 5 highlights this common behavior pattern, in which participants focused more on the text than on the images on the START PAGE. However, this may be an effect of the social pressure implicit in a controlled lab study.

Participants used ES opportunitistic and ES structure frequently across all views, as Figure 17 relationships and dependencies between multiple groups of controls. Participants in our study used this advanced interaction approach the least.

Oscillating Behavior

From our eye movement data and from comments participants made directly, we could observe that they spent much of their time oscillating between the controls and the chart to understand what the effect of their interaction with the controls had on the chart. For example, one participant (P05) observed that "[...] having to go back and forth between the icons and the circles would kind of drive you nuts after a while [...]". The oscillating behavior can also be seen in the scanpath visualizations (Figure 6) and is shown in the AOI timelines (Figure 7), where it is characterized by nearvertical lines connecting small horizontal fixation points.

Discovering Unusual Functionality

Even though both the STACKED BAR CHART and STACKED AREA CHART included a sliding rail control (Figure 3), only 4 participants (P01, P09, P10, P21) successfully discovered how to use these sliding rails. From the video and audio recordings, we observed that all four of these participants discovered this functionality by using ES opportunitistic . For example, P10 exclaimed "[...] just looking at Alberta. I can reorder these, oh thats cool, that's really cool [...]". It is likely that the presence of a rail between the items in the control group did not clearly suggest that the sliding interaction was possible, and neither simple visual scanning nor most of the common exploration strategies supported its discovery.

DESIGNING FOR DISCOVERY

Based on our observations and the exploration strategies we identified, we now review how our exploration strategies reveal design opportunities that may lead to the creation of more discoverable interactive visualizations. In this discussion, we connect our empirical findings to previous work in visualization and human-computer interaction.

Inviting Interaction

Participants all took their time before starting to interact with any of the views (see also Section 4 and Figure 12). This initial pause might reflect a lack of obvious available interactions. One approach for increasing the discoverability of possible interactions is to hint at their existence using feedforward. Feedforward [START_REF] Vermeulen | Crossing the bridge over Norman's gulf of execution: Revealing feedforward's true identity[END_REF] can suggest potential interactions by using animation or emphasis to preview the change that would happen if those interactions were carried out. Recent work by Boy et al. [START_REF] Boy | Suggested interactivity: Seeking perceived affordances for information visualization[END_REF] suggests that feedforward can be used to suggest possible interactions in a manner that entices people to interact more with a visualization. Another possible explanation for the delay before participants' initial interactions may be that they were passively interacting [START_REF] Spence | Information visualization[END_REF] with the view. This behaviour remains difficult to confirm based on the eye movement and interaction data alone and would require retrospectively asking participants what they were doing or thinking, which would have interrupted their exploration process.

Providing Entry Points

There are several examples of visualizations where the use of entry points (ES entry ) has successfully been applied to engage people and encourage them to interact. For example, the NameVoyager [START_REF] Wattenberg | Designing for social data analysis[END_REF] visualization has a direct personal entry point -a person's own name. In the NC-DRisc Height Map [START_REF] Ncd Risc | Height -evolution of adult height over time[END_REF], people typically start investigating the visualization by selecting their home country or the country they live in. The Bohemian Bookshelf offers multiple entry points to the same system in order to encourage playful exploration and serendipitous discovery [START_REF] Thudt | The bohemian bookshelf: Supporting serendipitous book discoveries through information visualization[END_REF].

Using Spatial Organization

In addition to known exploration methods like opportunistic interaction [START_REF] De Bruijn | Serendipity within a ubiquitous computing environment: A case for opportunistic browsing[END_REF] and entry points [START_REF] Bates | The design of browsing and berrypicking techniques for the online search interface[END_REF], our participants also used two exploration approaches, ES structure and ES permutations , that each made use of the spatial organization of the controls. ES structure used the spatial organization to step through grouped sets of interactive controls. ES permutations used the spatial organization of at least two sets of grouped controls to explore the possible permutations. This suggests that designers need to think deeply about the organization of controls. For instance, graphic design guidelines such as Kidd's [START_REF] Kidd | The cheese monkeys: A novel in two semesters[END_REF] are simple but effective: 1) left to right; 2) top to bottom; 3) front to back; and 4) dark to light. The attention that participants paid to the spatial organization of controls also suggests that careful placement can be used to guide a person through a specific sequence.

Combating Oscillation

We observed that participants spent much of their time oscillating back and forth between controls and the chart. They also explicitly told us that they found this irritating (see Section 6.2). This is evidence for the importance of embedded interactions. Research in both InfoVis [START_REF] Baur | Touchwave: Kinetic multitouch manipulation for hierarchical stacked graphs[END_REF]- [START_REF] Perin | Direct manipulation for information visualization[END_REF] and human-computer interaction [START_REF] Beaudouin-Lafon | Instrumental interaction: An interaction model for designing post-wimp user interfaces[END_REF]- [START_REF] Shneiderman | Direct manipulation: A step beyond programming languages[END_REF] has called for greater use of direct interaction. Interaction can be direct in terms of temporal immediacy, when there is no lag between an interaction and the data update. An interaction can also be direct in terms of spatial immediacy, when the interaction is co-located with the data. Temporal immediacy is now common and the visualizations we studied did not exhibit time lag between interactions and data updates. However, spatial immediacy remains challenging. The tendency in the visualization community is to place the controls adjacent to a visualization to minimize possible visual interference caused by having the controls too near or on-top of a visualization. Our study provides additional evidence that this spatial separation is problematic and can cause oscillation which participants found irritating. Integrating interactions into the data representation could limit attention switching, but may make them more difficult to discover.

Consequently, there is a trade-off between interaction familiarity and spatial immediacy. Despite the fact that more direct interaction is a recognized design goal [START_REF] Beaudouin-Lafon | Instrumental interaction: An interaction model for designing post-wimp user interfaces[END_REF], most interactive visualizations, including those we studied, are still commonly implemented using the WIMP paradigm [START_REF] Perin | Direct manipulation for information visualization[END_REF], [START_REF] Beaudouin-Lafon | Instrumental interaction: An interaction model for designing post-wimp user interfaces[END_REF]. Similarly, The visualizations we studied exhibited a clear separation between control panels and the visualization. This preference for familiar layouts may be due in part to the fact that the general public lacks visualization literacy [START_REF] Boy | A principled way of assessing visualization literacy[END_REF] and that people have difficulty discovering embedded interactions, because these interactions lack established metaphors and clear signifiers [START_REF] Norman | The way I see it: Signifiers, not affordances[END_REF]. For example, in comparison to familiar controls like buttons and sliders, the bars or marks in a chart provide little information to suggest that they might be interactive [START_REF] Boy | Suggested interactivity: Seeking perceived affordances for information visualization[END_REF].

Supporting Transitions

During our study, we observed that participants often compared different views in order to find out what had changed or see how the data was represented differently in another view (ES leverage ). These comparisons happened mostly at the interface level, with participants comparing differences between interface elements (visualization-tovisualization [START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF]) rather than changes in the data. To allow people to compare views at both the interface and data level, interactive visualizations could provide support for smoother transitions between views and between datasets, for example, through seamless transitions. Seamless transitions between views, paired with techniques for emphasizing changes, could make the process of switching views less disorienting. Transitions between pairs of interactive visualizations could be designed to help mitigate change blindness [START_REF] Simons | Change blindness[END_REF] and preserve participants' mental map of both views [START_REF] Eades | Preserving the mental map of a diagram[END_REF], [START_REF] Misue | Layout adjustment and the mental map[END_REF]. Using consistent layouts for multiple views may make this process easier by reducing the number of changes that need to be included in a transition, thereby reducing the transition cost [START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF]. Supporting crossfiltering between views [START_REF] Weaver | Cross-filtered views for multidimensional visual analysis[END_REF] or adding phosphor traces and afterglow effects to transitions [START_REF] Baudisch | Phosphor: Explaining transitions in the user interface using afterglow effects[END_REF] may also help limit cumbersome transitions between views.

Another way to address this problem is to use multiplecoordinated views [START_REF] Roberts | State of the art: Coordinated & multiple views in exploratory visualization[END_REF], in which changes in one view can cause updates in others. Such views are common in visual analytics and many systems use techniques like brushing and linking [START_REF] Becker | Brushing scatterplots[END_REF] or graphical overlay methods [START_REF] Kong | Graphical overlays: Using layered elements to aid chart reading[END_REF] to connect many different interactive visualizations together.

Scaffolding Complex Interactions

When using the STACKED BAR CHART and the LINE CHART, only four participants discovered the sliding rail functionality and used it to reorder regions or sources. Given that the use of more advanced interactions can lead to more efficient investigation, helping people learn how to use more complex interactions is important. Here, task-based tutorials and information scent cues may be useful tools to help people transition to more complex interactions. This important challenge has been discussed both in the InfoVis [START_REF] Loorak | Timespan: Using visualization to explore temporal multi-dimensional data of stroke patients[END_REF] and human-computer interaction [START_REF] Cockburn | Supporting novice to expert transitions in user interfaces[END_REF], [START_REF] Grossman | A survey of software learnability: metrics, methodologies and guidelines[END_REF] literature.

One possible approach is to highlight new functionality directly when a viewer first visits a visualization, using techniques such as stencil-based tutorials [START_REF] Kelleher | Stencils-based tutorials: Design and evaluation[END_REF]. Humancomputer interaction researchers have also explored more game-like approaches, including using integrated and engaging tacit tutorials [START_REF] Andersen | The impact of tutorials on games of varying complexity[END_REF]- [START_REF] Segel | Narrative visualization: Telling stories with data[END_REF].

The use of information scent cues -providing embedded navigation hints that encourage people to navigate to nearby views that may contain relevant content -were first introduced by Pirolli and Card [START_REF] Pirolli | Information foraging[END_REF] as part of a broader model of information foraging. This principle has since been applied to a variety of visual search and browsing tasks [START_REF] Pirolli | The effect of information scent on searching information: Visualizations of large tree structures[END_REF]- [START_REF] Olston | ScentTrails: Integrating browsing and searching on the web[END_REF]. Related techniques like scented widgets [START_REF] Willett | Scented widgets: Improving navigation cues with embedded visualizations[END_REF] embed social and data-driven scent cues directly into existing interface controls. These kinds of embedded visual hints could be used to encourage novices to investigate new views or examine areas of an interface they have previously ignored, explicitly encouraging them to discover new functionality.

LIMITATIONS AND SCOPE

While providing less realism and potentially lower ecological validity, a controlled lab study has the benefit of providing more precision [START_REF] Mcgrath | Human-computer interaction[END_REF]. In a lab setting we were able to collect data from a range of sources, triangulating eye movement data, interactions, and observations from video and audio to isolate and pinpoint specific strategies that participants applied. Although our methodology allowed us to utilize a variety of data sources, we still cannot infer whether participants applied the exploration strategies purposefully or unintentionally. Given our initial set of strategies, future studies could use Freeman's [START_REF] Freeman | Triggered think-aloud protocol: Using eye tracking to improve usability test moderation[END_REF] triggered think-aloud method (in which moderators can intervene in participants' exploration to ask for clarification) to try to assess participants' intent. We did not use this process for this initial study because such interruptions would disrupt participants' process of discovery and risk corrupting the eye movement data and interaction logs.

Our study does not intend to provide an exhaustive list of strategies people use when interacting with visualizations in general. We focused specifically on visualizations designed for public use and public engagement with open data, therefore guidelines such as scaffolding complex interactions and providing entry points may not apply to visualizations used in professional data analysis contexts, where explicit training is more common. We studied discovery in the context of one set of web-based visualizations of open energy data. While the set of exploration strategies we identified is broad, other strategies likely remain. We hope that the research community will build on this work by further exploring how people interact with new visualizations, thereby helping to build a more holistic understanding of the discovery of interactivity in visualizations.

Fig. 1 .

 1 Fig. 1. The four views available on the NEB website: (A) STACKED BAR CHART showing total energy demand by regions, (B) STACKED AREA CHART depicting energy demand according to the energy source and sector, (C) BUBBLE CHART presenting electricity generation by region or source, and (D) LINE CHART showing different possible energy production scenarios.

Fig. 2 .

 2 Fig. 2. The START PAGE of the website evaluated in the study showing across the bottom the option to select one of four views.

Fig. 4 .

 4 Fig. 4. The AOIs for each view. Each AOI is indicated by a color overlay based on the AOI group. The controls AOIs are shown with orange rectangles, indicating how the controls are grouped. The numbers AOIs for the axes are depicted with blue rectangles and the chart AOI is shown with a purple rectangle.

Fig. 5 .

 5 Fig. 5. The START PAGE of the website overlaid with an attention map for one participant showing high attention on the text snippet and some on the STACKED BAR CHART. The thumbnail in the top right corner shows the data mapping of the transparent to red color ramp.

Fig. 6 .

 6 Fig.6. Three different scanpaths showing the participants focus: (A) largely on the chart (P16), with some attention on the lower controls; (B) largely on the controls (P20), with some attention on the chart and on the numbers; and (C) largely on the numbers (P14), with some attention on the chart.

Fig. 7 .

 7 Fig. 7. A part of an AOI timeline for one participant for the LINE CHART. All AOIs for one view are represented by a horizontal light gray line. The background color of each AOI encodes its AOI group. The white circles show interactions in AOIs. Black circles mean that a participant opened the help menu. The dark gray line depicts the eye movements over time. If the eye movement line is dotted, it means that fixations are not assigned to any AOI. A vertical gap (white) indicates that a participant switched to another view and later came back to this view again.

Fig. 8 .Fig. 9 .Fig. 10 .

 8910 Fig. 8. All fixations recorded for each participant, colored by view, and sorted by total completion time in seconds. The white spaces indicate no eye movement data for that moment, for instance, when a participant looked away from the screen.

Fig. 11 .

 11 Fig. 11. Percentage of the total fixation time of AOI groups for each view with averages and 95% confidence intervals indicated by the gray areas. The colors refer to the different AOI groups.

Fig. 12 .

 12 Fig. 12. Time to first interaction for each view with averages and 95% confidence intervals indicated by the gray areas. The colors refer to the different views.

Fig. 13 .

 13 Fig. 13. This part of a participant's AOI timeline shows ES opportunitistic on the BUBBLE CHART. The white interaction circles show different types of controls being selected and between each selection the chart is viewed.

Fig. 14 .

 14 Fig. 14. This part of a participant's AOI timeline shows ES structure on the STACKED BAR CHART, where the participant sequentially selected all options in the main selection and then switched to the options in the scenarios controls.

Fig. 15 .Fig. 16 .

 1516 Fig. 15. This part of a participant's AOI timeline shows ES permutations on the STACKED AREA CHART. The interactions with the main selection control are separated by a series of interactions with the scenario control.

FFig. 17 .

 17 Fig.[START_REF] Viégas | ManyEyes: a site for visualization at internet scale[END_REF]. Number of participants who used each exploration strategy, per view and overall. The all counts reflect the number of unique participants who applied the given strategy at least once regardless of which view.

  is with Aarhus University, Denmark and the University of Calgary, Canada • C. Perin is with City, University of London, United Kingdom and University of Calgary, Canada • T. Ertl is with the University of Stuttgart, Germany

• W. Willett and S. Carpendale are with the University of Calgary, Canada Manuscript received XXX XX, 2017; revised XXX XX, 2017.

  shows. ES opportunitistic is the simplest exploration strategy and helps participants start to assess what an option or a group of options does. ES structure is more organized and suggests that participants are trying to understand what the different options in one control group represent and how they compare to each other. The ES permutations strategy is more advanced and participants who apply it are most likely trying to understand the

	STACKED BAR CHART	21	23	2	13	21	3	23	2	8
	STACKED AREA CHART	20	23	2	13	21	5	23	1	4
	BUBBLE CHART	24 23 10 16 20	7	20	3	8
	LINE CHART	20	24	4	13	19	9	23	0	3
	ALL	24 24 13 19 24 13 24	6	10

ACKNOWLEDGMENTS

Supported in part by: the National Energy Board (NEB) of Canada; Alberta Innovates -Technology Futures (AITF); the Natural Sciences and Engineering Research Council of Canada (NSERC); SMART Technologies; and the German Research Foundation (DFG) within SFB/Transregio 161.

CONCLUSIONS

In this paper, we investigated how people discover functionality of an interactive visualization designed for public consumption. Unlike prior studies of interactive visualization use, our analysis incorporates not only interaction logs and audio/video recordings, but also includes detailed analyses of eye movement data. Combining Understanding these exploration strategies led to several promising suggestions that may make functionality more discoverable in interactive visualizations. These include:


Paola Gómez

Claudia Roncancio
email: claudia.roncancio@univ-grenoble-alpes.fr

Rubby Casallas
email: rcasalla@uniandes.edu.co

Towards quality analysis for document oriented bases

Keywords: NoSQL, structural metrics, document-oriented systems, MongoDB

published or not. The documents may come

Towards quality analysis for document oriented bases

Introduction

Nowadays, applications and information systems need to manage a large amount of heterogeneous data while meeting various requirements such as performance or scalability. NoSQL systems provide efficient data management solutions while offering flexibility in structuring data. Our work focuses on document-oriented systems, specifically those storing JSON documents, including MongoDB 3 . These systems are "schema-free". They support semi-structured data without a previous creation of a schema (unlike relational DBMS) [START_REF] Nayak | Article: Type of nosql databases and its comparison with relational databases[END_REF]. Data can be stored in collections of document with atomic and complex attributes. This flexibility enables rapid initial development and permits many data structure possibilities for the same information. The choice is quite crucial for its potential impact on several aspects of application quality [START_REF] Gómez | Data schema does matter, even in nosql systems![END_REF]. Indeed, each structure may have advantages and disadvantages regarding several aspects, such as the memory footprint of the document base, data redundancy, navigation cost, data access or program readability and maintainability. It becomes interesting to consider several data structure candidates to retain a single choice, a temporal choice or several parallel alternatives. The analysis and comparison of several data structures is not easy because of the absence of common criteria for analysis purposes 4 and because there are potentially too many structuring possibilities.

Our research in the SCORUS project is a contribution in this direction. Even if document-oriented systems do not support a database schema, we propose to use a "schema" abstraction. The goal is to assist users in a data modeling process using a recommendation approach. We seek to abstract and to work with a "schema" to facilitate comprehension, assessment and comparison of document oriented data structures. The purpose is to clarify the possibilities and characteristics of each "schema" and to provide objective criteria for evaluating and assessing its advantages and disadvantages. The main contribution of this paper is the proposal of a structural metrics set for JSON compatible scheme abstraction. These metrics reflect the complexity of the data structures and can be used to establish quality criteria such as readability and maintainability. The definition of these metrics is based on experiments with MongoDB, XML-related work and metrics used in Software Engineering for code quality.

In Section 2, we provide background on MongoDB and the motivation of our proposal. Section 3 presents a brief overview of SCORUS and introduces the schema abstraction AJSchema. In Section 4, we propose structural metrics to measure AJSchemes. Section 5 is devoted to the validation. It presents a scenario for schema comparison using our metrics. Related work is discussed in Section 6. Conclusions and research perspectives are presented in Section 7.

Background and motivation

We are interested in quality issues of document-oriented databases. We focus on JSON documents managed by systems like MongoDB [START_REF] Copeland | MongoDB Applied Design Patterns[END_REF]. Here, data is managed as collections of documents (see Figure 1) where a document is a set of attribute:value pairs. The value type can be atomic or complex. Complex data type means either an array of values of any type or another nesting document. An attribute value can be the identifier of a document in another collection. This allows referencing one or more documents. This simple type system provides a lot of flexibility in creating complex structures. Collections can be structured and connected in various forms considering or not data Fig. 2: SCORUS overview replication. e.g. completely nested collections or combination of nesting and referencing. Figure 1 depicts two ways of structuring information about tweets and twerson.

Figure 1a shows a Tweets collection and a Twerson collection. Documents in Tweets reference documents in Twerson. The choice in Figure 1b is different, there is a single collection Tweets with nested documents for their "twerson". In this example, there is no duplication of data.

There is not a definitive best structure because it depends on the current needs and priorities. However, the characteristics of the data structure have a strong impact on several aspects such as the size of the database, query performance and code readability of queries. The experiments presented in [START_REF] Gómez | Data schema does matter, even in nosql systems![END_REF] confirm that influence. Our work is motivated by the analysis of how such aspects influence the maintainability and usability of the database as well as applications. In particular, it appears that collections with nested documents are favorable to queries following the nesting order. However, access to data in another order and queries requiring data embedded at different levels in the same collection will be penalized. The reason is that the complexity of manipulations required in such cases is similar to joining several collections. In addition, collections with nested documents have a larger footprint than the equivalent representation with references. When structuring data, priorities may lead to diverging choices, as replicating documents in multiple collections while reducing memory requirement and storage cost.

SCORUS Overview and Schema Abstraction

Our research focuses on helping users to understand, evaluate and make evolve semistructured data in a more conscious way. The main contribution of this paper are the structural metrics presented in Section 4. Hereafter, we provide a brief overview of our larger project, SCORUS; we introduce the schema abstraction (Sections 3.2 and 3.3) and tree representation (Section 3.4) we have defined to ease the evaluation of the metrics.

SCORUS Overview

The SCORUS project aims at facilitating the study of data structuring possibilities and providing objective metrics to better reveal the advantages and disadvantages of each solution with respect to the user needs. Figure 2 shows the general strategy of SCORUS which involves three steps: (1) from a UML data model, generating a set of schemes alternatives; (2) evaluating such schemes by using the metrics proposed in this paper; and (3) providing a top k of the most suitable schemes according to user preferences and application priorities. The sequence of the three steps can take place in a design process, but each step can be carried out independently for analysis and tuning purposes 5 . Fig. 3: AJSchemes for examples presented in Figure 1 3

.2 Schema abstraction for structural analysis

To facilitate reasoning about the data structuring choices in document oriented systems, we define a schema abstraction, called here AJSchema. It is based on JSON schema approach [4] and on the data types supported by MongoDB.

AJSchema allows us to provide a concise representation of the collections and types of the documents to be stored in the base. Figure 3 shows the abstracted AJSchema for the examples in Figure 1. For each collection the schema describes the type of its documents. A document type is a set of attribute:type pairs enclosed by { }. Types are those of MongoDB. Arrays are symbolized by [ ] and inside them, the type of its elements (atomic or document). In this paper, we use indistinctly the terms AJSchema or schema to refer to this abstraction. For schema-free systems like MongoDB, such abstractions can be considered as a data structure specification for construction and/or maintainability process.

An AJSchema from UML Model

Based on a UML model, SCORUS provides several AJSchemes that are then compared to each other to improve the selection. Hereafter we illustrate the correspondence between the classes and relationships of the UML model and an AJSchema (Figures 4 and5) 5 .

Considering a UML model, E = {e 1 , ..., e n } are the classes. The attributes of a class e i are designated in the following by the type te i and its relationships with the set R(e i ) = {r 1 , ..., r n }. Roles of relationships are known and noted by r irol . Figure 4 shows a UML model with classes Agency, BusinessLines, Owner, Creative and Publicity. The properties of the class Agency are designated by the type tAgency 6 .

An AJSchema describes the types of the collections that will be used. A collection type includes the attributes of a UML class (te i ) and extra attributes representing the relationships of this class (R(e i )). The latter are named by the target role of r i from the class e i . Figure 5 Relationships can be materialized by referencing or by embedding of documents. This choice, so as the cardinality, determine the type of the attribute. By referencing, the type is Integer, for the id of the referenced document. By embedding, the type is a document of type te j . A cardinality "many" (in 1-many or many-many relationships) implies an In our example, the attribute bLines represents the 1-to-many relationship r1 by embedding of documents. Its type is therefore an array of documents of type tBusinessLines. Attribute ows corresponds to the role of relationship r3. The 1-to-many cardinality and a representation by referencing lead to an attribute of type array of Integers. Referencing forces the existence of a collection of Owners.

Tree representation

To facilitate metrics evaluation, we use a tree representation of the AJSchema. The tree contains information about data types, nested levels, and embedded/referenced elements. The tree semantics is illustrated in Figure 6 representing the AJSchema of Figure 5.

The root node has a child per collection in the AJSchema. Agencies, Owners and Creatives in our example. The collection type is represented by the child sub-tree. Nodes of the form typename@li indicate that attributes of the typename appear in the documents at level li (starting with level 0) . Attributes representing the relationships R(e i ) appear as follows. A node with the name (and role used) of each relationship is created (e.g. r1 bline ) with a child node, either REF, either EMB according to the choice of referencing or embedding documents. Arrays, denoted [ ], can be used for 1-to-many relationships. For example, the subtree on the left of Figure 6, shows relationship r1 bline materialized as an attribute (added to agency) of type array of business, tAgencyEM B[]tBusiness. Relation r2 of tBusiness causes the embedding of an array of tCreative. The nodes indicating a level (e.g. tBusiness@l 1 ) allow to easily identify the depth of a type and its extra attributes associated with the relationships. In this section, we propose a set of metrics that reflects key aspects of the semi-structured schema complexity. The purpose is to facilitate schema analysis and comparison. We have defined a set of metrics grouped into 5 categories presented in the Sections 4.1 to 4.5. A summary is presented in Section 4.6. In the following, ϕ denotes a collection, t a document type and x a schema.

Existence of types and collections

Having a collection can be mainly motivated by the access improvement to its document type at first level or its nested types. On the other hand, nesting a document into another one can be motivated by the fact that information is often accessed together. It may also be interesting to realize if a document type is nested in many places to help reducing the collection complexity.

In this section, we have defined metrics that allows us to identify the existence of a document type t in a schema. We consider two cases: (1) the existence of a collection whose type t is at the first level (l o ), and (2) the presence of such documents nested within other documents. These cases are covered, respectively, by metrics colExistence and docExistence. Existence of a collection of documents of type t:

colExistence(t) = 1 : node t@l 0 exists in schema x 0 (1)
Existence of embedded documents of type t: this is materialized in the graph by a node * EM B t.

docExistence(ϕ, t) = 1 t ∈ ϕ node * EM B t exists in the paths child of node ϕ in x 0 t / ∈ ϕ (2)
Figure 6 shows collections for the types tAgency, towners and tCreative (nodes @l 0 ) but not for tPublicity. Documents of type tPublicity exist exclusively embedded in tCreative documents. Note that documents of type tBusiness are embedded in two collections, Agencies and Creatives.

Nesting depth

In general, the deeper the information is embedded, the higher is the cost to access it. This is true unless the intermediary information is also required. Knowing the nesting level of a document type facilitates the estimation of the cost of going down and back through the structure to access the data or to restructure the extracted data with the most suitable format. We propose a set of metrics to evaluate the complexity induced by embedded data. The following two metrics allow us to know the maximum depth levels of collections and schema. Collection depth: the colDepth (3) metric indicates the level of the more deeply embedded document in a collection. Embedded documents are represented by the EMB nodes in the graph.

colDepth(ϕ) = max(depth(p i )) : p i is a valid child path of node ϕ (3) depth(p) = n number of nodes EM B in path p (4)
Schema Depth: the globalDepth (5) metric indicates the deepest nesting level of a schema by considering all collections.

globalDepth(x) = max(colDepth(ϕ i )) : ∀ collection ϕ i ∈ x (5)
Having recurring nested relations increases the schema complexity without necessarily improving query performance. A very nested collection can be advantageous if frequent queries require the joined information. Besides, having such a schema can be ideal if the access pattern matches with the schema. Otherwise, projections and other structuring operations will probably be required, introducing complexity in the data manipulation (see following metrics). This affects code readability and maintainability.

In Figure 6, the depth of collection Owners is 0 and the depth of collections Agencies and Creatives is 2. The maximum depth of the schema is 2. Note that in the Creatives collection, the type tAgency adds no nesting level as it uses an array with references to Owners. Depth of a type of document: the metric docDepthInCol (6) indicates the embedding level of a document of type t in a collection ϕ. If the items of the collection are of type t (node t@l 0 ), then the depth is zero. Otherwise, the metric is the level of the deepest embedded document of this type (EM B t node) according to the root-leaf paths.

docDepthInCol(ϕ, t) = 0 : t corresponds to node t@l 0 son of node ϕ max(docDepth(p i , t) : p i is a valid root-leaf child path of node ϕ

docDepth(p, t) = n number of nodes EM B between root and * EM B t

In the Creatives collection of the example, the nesting level of tPublicity is 2, that of tCreative is 0. tCreative is also nested at level 2 in the Agencies collection.

We also introduce the maxDocDepth (8) and minDocDepth (9) metrics to measure the most and shallowest levels where a document type appears in a schema.

maxDocDepth(t) = max(DocDepthInCol(ϕ i , t)) : ϕ i ∈ x ∧ t ∈ ϕ i (8) minDocDepth(t) = min(DocDepthInCol(ϕ i ), t) : ϕ i ∈ x ∧ t ∈ ϕ i (9)
Knowing the minimum and maximum levels eases to estimate how many intermediate levels should be treated for the more direct or the less direct access to a document of a certain type. In the example, minDocDepth(tBusiness) = 1 as there is no collection of documents of that type.

Width of the documents

Now we can look at the complexity of a document type in terms of its number of attributes and the complexity of their types. These metrics are motivated by the fact that documents with more complex attributes are more likely to require more complex access operations and projections. The reason is that to extract the attributes required by a query, it is necessary to "remove" the other attributes and data stored together. This operation is more expensive for documents with a larger number of attributes, i.e., with a high width. It may be interesting to choose a scheme by analyzing its "wide" and its nesting level.

The docWidth7 (10) metric of a document type is based on the number of atomic attributes (coefficient a = 1), the number of attributes embedding a document (coefficient b = 2), the number of attributes of type array of atomic values (coefficient c = 1) and array of documents ( coefficient d = 3). Arrays of documents have the highest weight as the experiments revealed them as the more complex to manage.

docW idth(t, ϕ) = a * nbrAtomicAttributes(t, ϕ) + b * nbrDocAttributes(t, ϕ) + c * nbrArrayAtomicAttributes(t, ϕ) + d * nbrArrayDocAttributes(t, ϕ) (10)
The metrics for each type of attributes can also be used separately. The size of the arrays is not considered here because it is not necessarily available in a design phase. If the size is available, it seems interesting to differentiate the orders of magnitude of the arrays, i.e. small ones vs very large ones (less than ten elements, around thousands elements, etc).

In Figure 4, Agencies and Creatives collections use documents of type tBusiness but do not have the same attributes. In Creatives, the type includes arrays of agencies and publicity, docWidth (tBusiness,Creatives) = 8, unlike Agencies where docWidth(tBusiness,Agencies) = 4.

Referencing rate

Referential integrity becomes difficult to maintain for collections which documents are referenced by many other collections. For a collection with documents of a certain type t, the metric refLoad [START_REF] Ruiz | Inferring versioned schemas from nosql databases and its applications[END_REF]

Redundancy

We are interested in estimating potential data redundancy during the schema design because it impacts several aspects. Data redundancy can speed-up access and avoid certain expensive operations (i.e. joins). However, it impacts negatively the memory footprint of the base and makes coherency enforcement more difficult. There is a cost and writing program complexity is increased and impacts the maintainability. As we are working on a structural basis, we do not use data replication information for the metric definition.

The metric docCopiesInCol (12) is calculated by using the cardinality information of the relationships together with the representation choices in the semi-structured schema.

Redundancy occurs for some cases of representation of the relationship by embedding documents.

docCopiesInCol(t, ϕ) =        0 : t / ∈ ϕ docExistence(ϕ, t) = 0 1
: t corresponds to node t@l 0 of ϕ card(r rol , t) : r rol a valid node r rol father of a node EM B of the path ϕ and * EM Bt (12) card(r, ε) = n ncardinality of r on the ε side in the UML model [START_REF] Sadalage | NoSQL distilled: a brief guide to the emerging world of polyglot persistence[END_REF] In the Creatives collection of Figure 2, the attribute for business, named bline , introduces redundancy for agencies. The relationship r1 may associate an agency A to n1 business instances. This leads to n1 copies of the document A. In the case where a business is referenced by n2 creatives (relationship r2), there will be n1 x n2 copies of the document A.

Moreover, we propose the metric docTypeCopies(t) indicating the number of times a document type is used in the schema. It reflects the number of structures that can potentially store documents of type t. This metric uses the metric of existence already introduced.

Summary

The proposed metrics are summarized in Table 1. These metrics are evaluated in the scope of the collections, types, or the whole schema, to reveal the data structure complexity.

Validation Scenario

As mentioned, our work aims at assisting users in the choice of document-oriented schema. The proposed metrics, together with application priorities, will be used to establish criteria for choosing and comparing schemes. This is primarily to bring out the most suitable schema according to certain criteria but also to exclude unsuitable choices or to consider alternative schemes that were not necessarily considered initially.

In the following we present a usage scenario for the proposed metrics. In Figure 7, we introduce an example with nine structuring alternatives. This case study was already used in the work with MongoDB databases presented in [START_REF] Gómez | Data schema does matter, even in nosql systems![END_REF], where we discussed the impact of the data-structures on the query evaluation. Here we are considering a similar application to analyze schema alternatives using the metrics. We evaluate the metrics for the nine schemes. Table 2 reports a subset of them. Schema analysis will be based on user priorities such as efficient access, data consistency requirements and other user preferences. A criterion corresponds to a preference (maximization or minimization) over one or several metrics to privilege a set of schemes 8 .

In our case study, the priorities of the application concern efficient access to companies information, including the names of their departments (high priority), and getting the employee with the highest salary in the company from its identifier or its name. Considering these priorities, the collection Companies plays an important role (criterion 1) 9as well as the manipulation of its instances (criterion 5). The departments are accessed via the companies (criterion 6). Furthermore, it is known that the consistency of business data is important. It is therefore preferable to limit the copies to these data (criterion 2). Moreover, access to all employees (criterion 4) is not a priority.

Metrics \ Schema S1 S2 S3 S4 S5 S6 S7 S8 S9 colExistence(tCompany) 1 1 1 1 0 1 0 1 1 docCopies(tCompany) 1 1 1 1 1 3 1 1 1 refLoad(Employees) 0 1 0 0 0 0 colExistence(tEmployee) 1 0 0 1 1 1 0 0 1 docWidth(Companies,l1) 1 1 3 1 1 3 docExistence(tDepartment,Companies) 0 0 1 0 0 1
Table 2: Case study: sub-set of metrics of schema S1 to S9

In Table 3, each line represents one of the six criteria already mentioned. Each criteria has been evaluated for the nine alternative schemes. The values of the criteria evaluation were normalized (between 0 and 1). These values introduce a relative order between the schemes. For example, considering criteria 4, the schema S1, S4, S5, S6 and S9 are preferred over the others.

The analysis of schemes is multi-criteria (6 criteria in our case). Each criterion can have the same weight, or it can be some more important than others. The evaluation function of a schema, noted schemaEvaluation is the weighted sum of criteria.

schemaEvaluation(s) = |Criteria| i=1 weightcriterion i * fcriterion i (s) (14)
We evaluated three different weights: same weight for all criteria (case 1), priority criteria focused on companies (case 2), and priority addition on employees motivated by a new access pattern to its information (case 3). Figure 8 shows the result of the evaluation of 9 schemes for the three cases.

The estimates place schemes S5, S7 and S8 as the worst in the three cases. S5 and S7 are based on a single collection that is not a priority in the current criteria. On the other hand, S3 stands out in case 2 due to the high priority of its unique collection Companies. In addition, this collection embeds data in an appropriate order regarding the criterion 6. Some scheme, as S9 and S6, are stable in their scores for all three cases. S9 is the best because it matches all criteria; its good results in the three cases denotes a form of "versatility" of the schema that can withstand changes in priorities. S6 introduces redundancy which is penalized by criterion 2. Meanwhile, criterion 6 penalizes it by not having embedded documents in collection Companies.

The criteria to be considered and their associated weight depends on the applications and the user. They may reflect good practices advocated for development or general priorities. For example, a very "compact" schema limiting memory footprint can be

Criteria \ Schema S1 S2 S3 S4 S5 S6 S7 S8 S9
Criteria 1 fc 1 (s) = colExistenceCompanies(s) 1.00 1.00 1.00 1.00 0.00 1.00 0.00 0.00 1.00 Criteria 2 fc 2 (s) = docCopiestCompany min (s) 1.00 1.00 1.00 1.00 1.00 0.33 1.00 1.00 1.00 Criteria 3 fc 3 (s) = ref LoadEmployees max (s) 1.00 1.00 1.00 0.00 1.00 1.00 1.00 1.00 1.00

Criteria 4 fc 4 (s) = colExistenceEmployees(s) 1.00 0.00 0.00 1.00 1.00 1.00 0.00 1.00 1.00 Criteria 5 fc 5 (s) = levelW idthCompaniesL1 min (s) 1.00 1.00 0.33 1.00 0.00 1.00 0.00 0.00 0.33 Criteria 6 fc 6 (s) = docDptInCompanies min (s) 0.00 0.00 1.00 0.00 0.00 0.00 0.00 0.00 1.00

Table 3: Criteria evaluation on schema S1 until S9 Fig. 8: Schema evaluation preferred for rarely used data. Knowing that the criteria may evolve and lead to divergent choices, the use of metrics and criteria for a scheme analysis can help in a continuous process of "tuning" of the base. This can lead to schema evolution and data replication with heterogeneous structures. For a while, a document base may have, a copy (or partial copy) of the data with schema Sx and another copy with scheme Sy.

Related work

We studied works concerning NoSQL systems [START_REF] Mior | Nose: Schema design for nosql applications[END_REF][START_REF] Lombardo | Issues in handling complex data structures with nosql databases[END_REF][START_REF] Zhao | Schema conversion model of sql database to nosql[END_REF][START_REF]MongoDBCompass[END_REF] [9-12] [3, 13, 14] , complex data [START_REF] Abiteboul | Querying semi-structured data[END_REF][START_REF] Herden | Measuring quality of database schemas by reviewing-concept, criteria and tool[END_REF] [4, 17], XML documents [START_REF] Klettke | Metrics for xml document collections[END_REF][START_REF] Pušnik | Xml schema metrics for quality evaluation[END_REF] and software metrics [START_REF] Li | Object-oriented metrics that predict maintainability[END_REF][START_REF] Chidamber | Towards a metrics suite for object oriented design[END_REF][START_REF] Mccabe | A complexity measure[END_REF][START_REF] Fenton | Software metrics: roadmap[END_REF][START_REF] Fenton | Software metrics: a rigorous and practical approach[END_REF][START_REF] Timóteo | Software metrics: A survey[END_REF].

Concerning XML, Klettke et al. [START_REF] Klettke | Metrics for xml document collections[END_REF] propose 5 structural metrics based on the software quality model ISO 9126. They work on a graph representation of the DTD and metrics consider the number of references, nodes and make a link with the cyclomatic complexity [START_REF] Mccabe | A complexity measure[END_REF]. In [START_REF] Pušnik | Xml schema metrics for quality evaluation[END_REF], Pušnik et al. propose six metrics each one associated with a quality issue such as the structure, clarity, optimality, minimalism, reuse and flexibility. These metrics use 25 variables that measure the number of elements, annotations, references and types, among others. We extended and adapted these proposals to take into account particularities of JSON as embedded documents and complex attribute types.

Our metrics are also influenced by software metrics [START_REF] Li | Object-oriented metrics that predict maintainability[END_REF][START_REF] Chidamber | Towards a metrics suite for object oriented design[END_REF][START_REF] Mccabe | A complexity measure[END_REF][START_REF] Fenton | Software metrics: roadmap[END_REF][START_REF] Fenton | Software metrics: a rigorous and practical approach[END_REF][START_REF] Timóteo | Software metrics: A survey[END_REF]. Metrics proposed in [START_REF] Li | Object-oriented metrics that predict maintainability[END_REF][START_REF] Chidamber | Towards a metrics suite for object oriented design[END_REF][START_REF] Mccabe | A complexity measure[END_REF][START_REF] Fenton | Software metrics: roadmap[END_REF] reflect, for example, the coupling levels between components, the size of the class hierarchies, the size of objects and the number of methods. [START_REF] Timóteo | Software metrics: A survey[END_REF] is an excellent survey of software metrics considering those based on the complexity of code and object oriented concepts.

Concerning NoSQL approaches, some works investigate about data modelling alternatives [START_REF] Mior | Nose: Schema design for nosql applications[END_REF][START_REF] Lombardo | Issues in handling complex data structures with nosql databases[END_REF][START_REF] Abdelhedi | Mda-based approach for nosql databases modelling[END_REF]. In [START_REF] Abdelhedi | Mda-based approach for nosql databases modelling[END_REF], Abdelhedi et al. propose to translate an UML model into several alternatives of "schema" for Cassandra, Neo4J and MongoDB. For Cassandra in [START_REF] Mior | Nose: Schema design for nosql applications[END_REF][START_REF] Lombardo | Issues in handling complex data structures with nosql databases[END_REF] the main concerns are the storage requirements and query performance. Queries are implemented with SET and GET primitives. Lombardo et al. [START_REF] Lombardo | Issues in handling complex data structures with nosql databases[END_REF] propose the creation of several versions of the data with different structures. Each version is best suited for a different query in the style of pre-calculated queries. Zhao et al. [START_REF] Zhao | Schema conversion model of sql database to nosql[END_REF] propose a systematic schema conversion model of a relational database to NoSQL database. It creates a collection per entity type and the documents embed recursively the entities they reference. The structure is in the style of schema S6 in our validation scenario. Using the vocabulary of the relational model, this choice corresponds to a de-normalized structure with pre-calculation of natural joins (represented with embedded documents).

The authors propose a metric for the data redundancy generated which uses the data volume. Among the existing tools working on operational bases, MongoDBCompass [START_REF]MongoDBCompass[END_REF] allows to monitor the query execution time and data volume of a collection of documents. JSON schema [4] is the result of efforts to facilitate the validation of JSON documents. Tools as json-schema [17] analyze JSON documents in order to abstract a "scheme" with explicit collection and type definitions. Other researchers, as [START_REF] Klettke | Schema extraction and structural outlier detection for json-based nosql data stores[END_REF][START_REF] Wang | Schema management for document stores[END_REF][START_REF] Ruiz | Inferring versioned schemas from nosql databases and its applications[END_REF][START_REF] Gallinucci | Schema profiling of document-oriented databases[END_REF], work on schemes deduction for existing schema-free document-oriented bases. Their motivation is helping to understand data structuring and explaining its variants.

Guidelines to consider in modelling semi-structured data are discussed in [START_REF] Copeland | MongoDB Applied Design Patterns[END_REF][START_REF] Sadalage | NoSQL distilled: a brief guide to the emerging world of polyglot persistence[END_REF][14][START_REF] Abiteboul | Querying semi-structured data[END_REF][START_REF] Herden | Measuring quality of database schemas by reviewing-concept, criteria and tool[END_REF]. Sadalage et al. [START_REF] Sadalage | NoSQL distilled: a brief guide to the emerging world of polyglot persistence[END_REF] analyze various data models and NoSQL systems including MongoDB, Cassandra and Neo4j. Their main concerns are the issues in the migration of a relational database towards BigTables, documents and graphs. [START_REF] Copeland | MongoDB Applied Design Patterns[END_REF]14] propose guidelines for creating Mongo databases based on several use cases. These "best practices" can be formalized in our work as criteria to be taken into account in the schema analysis. To the best of our knowledge, no structural metrics are currently defined in the literature.

Conclusion and perspectives

This work is motivated by quality issues in document-oriented bases. We focus on data structuring in JSON documents, supported by MongoDB. The flexibility offered by such systems is appreciated by developers as it is easy to represent semi-structured data. However, this flexibility comes at a cost in the performance, storage, readability and maintainability of the base and it's applications. Data structuring is a very important design decision and should not be overlooked. In this work, we briefly described SCORUS, our larger project, which aims at helping user to clarify the possibilities of data structuring and to provide metrics allowing to take decisions in a more conscious way. We defined a schema abstraction called AJSchema to reason about semi-structured data. We proposed a set of 11 structural metrics covering aspects as existential, nesting depth, nesting width, referencing, and redundancy. These metrics are evaluated automatically on a tree representation of the schema. The proposed metrics reflect the complexity of schema elements that play a role on quality aspects.

We presented a usage scenario of the metrics to analyze several schema variations and certain application criteria and priorities. The criteria analysis can rule out certain schema and highlight others. These findings on structural aspects were compared, and are well in line, with the results of performance evaluation experiments we conducted with databases containing data. It is interesting to note that when working on the structures, it is possible to consider more schema variants than when experimenting with the databases. This brought an unexpected result, that is the identification of a different schema with very good characteristics.

The proposed metrics form a set that is likely to evolve. Further work includes validation on a larger scale and the development of the SCORUS system to complete the automatic schema generation.We will also work in formalizing a recommendation system to facilitate the definition of criteria by using the metrics, important queries and other functional or non-functional preferences of potential users.

Fig. 1 :

 1 Fig. 1: Example of data in MongoDB using referencing and embedding documents

  presents a possible schema for the UML data model of Figure4. It has three collections Agencies, Owners and Creatives. The type of Agencies is formed by the attributes agencyName and id, corresponding to type tAgency, and attributes bLines and ows, corresponding to relationships r1 and r3 respectively.

Fig. 4 :

 4 Fig. 4: From UML to several options of schemes

Fig. 6 :

 6 Fig. 6: Tree structure representing AJSchema of Figure 4

Fig. 7 :

 7 Fig. 7: Case study: UML data and AJSchema alternatives

Table 1 :

 1 indicates the number of attributes (of other types) that are potential references to documents of type t. Structural metrics

	ref Load(ϕ) = n	n -number of nodes * REF t where t=t@l0of nodeϕ	(11)
	For the Owners collection in Figure 4, ref Load(tOwner) = 2: collection Agencies
	references towner at level 0 while collection Creatives references it in a document
	embedded at level 2.

For document oriented data there are no design criteria analogous to normalization theory in the relational model

Schemes generation and recommendation are beyond the scope of this article.

type tei has by default the attribute id corresponding to the MongoDB document identifier.

this metric is close to the fan-in metric for graphs

A criterion is represented by a function in terms of maximization or minimization of metrics

The criterion number facilitates the presentation. It doesn't correspond to a priority.

Acknowledgements: many thanks to G. Vega, J. Chavarriaga, M. Cortés, C. Labbé, E. Perrier, P. Lago and the anonymous referees for their comments on this work.

NoSQL database (https://www.mongodb.com , https://db-engines.serialization of JSON-like documents (http://bsonspec.org)